Adjazenzmatrix ist eine Möglichkeit, einen Graphen G = {V, E} als boolesche Matrix darzustellen.
Darstellung der Adjazenzmatrix
Die Größe der Matrix ist VxV, wobei V die Anzahl der Knoten im Graphen ist und der Wert des Eintrags Aij 1 oder 0 ist, je nachdem, ob es eine Kante von Knoten i zu Knoten j gibt.
Beispiel einer Adjazenzmatrix
Das Bild unten zeigt den Graphen und seine äquivalente Adjazenzmatrix.
Bei einem ungerichteten Graphen ist die Matrix diagonalsymmetrisch, weil jede Kante (i, j) auch eine Kante (j, i) hat.
Vorteile der Adjazenzmatrix
Grundoperationen wie das Hinzufügen einer Kante, das Entfernen einer Kante und das Prüfen auf eine Kante von Scheitelpunkt i zu Scheitelpunkt j sind äußerst zeiteffiziente Operationen. Operationen mit konstanter Zeit.
Wenn der Graph dicht ist und die Anzahl der Kanten groß ist, sollte die Adjazenzmatrix die erste Wahl sein. Selbst wenn der Graph und die Adjazenzmatrix spärlich sind, können wir sie mit spärlichen Matrixdatenstrukturen darstellen.
Der größte Vorteil ergibt sich jedoch aus der Verwendung von Matrizen. Jüngste Fortschritte in der Hardware ermöglichen es uns, sogar teure Matrixoperationen auf der Grafikverarbeitungseinheit (GPU) durchzuführen.
Indem wir Operationen an einer angrenzenden Matrix durchführen, können wir wichtige Informationen über die Natur des Graphen und die Beziehung zwischen seinen Scheitelpunkten erhalten.
Nachteile der Adjazenzmatrix
Aufgrund des Platzbedarfs der VxV-Adjazenzmatrix ist möglicherweise nicht genügend Speicher vorhanden. Aber normalerweise haben Graphen nicht allzu viele Verbindungen, und das ist der Hauptgrund, warum Adjazenzlisten für die meisten Probleme die beste Wahl sind.
Obwohl die Grundoperationen einfach sind, sind Operationen wie InEdges und OutEdges teuer, wenn Adjazenzmatrixdarstellung verwendet wird.
Adjazenzmatrixcode
Wenn Sie wissen, wie man zweidimensionale Arrays erstellt, wissen Sie auch, wie man eine Adjazenzmatrix erstellt.
Adjazenzmatrix in C++
#include <iostream>
using namespace std;
class Graph {
private:
bool** adjMatrix;
int numVertices;
public:
Graph(int numVertices) {
this->numVertices = numVertices;
adjMatrix = new bool*[numVertices];
for (int i = 0; i < numVertices; i++) {
adjMatrix[i] = new bool[numVertices];
for (int j = 0; j < numVertices; j++)
adjMatrix[i][j] = false;
}
}
void addEdge(int i, int j) {
adjMatrix[i][j] = true;
adjMatrix[j][i] = true;
}
void removeEdge(int i, int j) {
adjMatrix[i][j] = false;
adjMatrix[j][i] = false;
}
bool isEdge(int i, int j) {
return adjMatrix[i][j];
}
void toString() {
for (int i = 0; i < numVertices; i++) {
cout << i << " : ";
for (int j = 0; j < numVertices; j++)
cout << adjMatrix[i][j] << " ";
cout << "\n";
}
}
~Graph() {
for (int i = 0; i < numVertices; i++)
delete[] adjMatrix[i];
delete[] adjMatrix;
}
};
int main(){
Graph g(4);
g.addEdge(0, 1);
g.addEdge(0, 2);
g.addEdge(1, 2);
g.addEdge(2, 0);
g.addEdge(2, 3);
g.toString();
/* Outputs
0: 0 1 1 0
1: 1 0 1 0
2: 1 1 0 1
3: 0 0 1 0
*/
}
Java Adjazenzmatrix
public class Graph {
private boolean adjMatrix[][];
private int numVertices;
public Graph(int numVertices) {
this.numVertices = numVertices;
adjMatrix = new boolean[numVertices][numVertices];
}
public void addEdge(int i, int j) {
adjMatrix[i][j] = true;
adjMatrix[j][i] = true;
}
public void removeEdge(int i, int j) {
adjMatrix[i][j] = false;
adjMatrix[j][i] = false;
}
public boolean isEdge(int i, int j) {
return adjMatrix[i][j];
}
public String toString() {
StringBuilder s = new StringBuilder();
for (int i = 0; i < numVertices; i++) {
s.append(i + ": ");
for (boolean j : adjMatrix[i]) {
s.append((j?1:0) + " ");
}
s.append("\n");
}
return s.toString();
}
public static void main(String args[])
{
Graph g = new Graph(4);
g.addEdge(0, 1);
g.addEdge(0, 2);
g.addEdge(1, 2);
g.addEdge(2, 0);
g.addEdge(2, 3);
System.out.print(g.toString());
/* Outputs
0: 0 1 1 0
1: 1 0 1 0
2: 1 1 0 1
3: 0 0 1 0
*/
}
}
Adjazenzmatrix in Python
class Graph(object):
def __init__(self, size):
self.adjMatrix = []
for i in range(size):
self.adjMatrix.append([0 for i in range(size)])
self.size = size
def addEdge(self, v1, v2):
if v1 == v2:
print("Same vertex %d and %d" % (v1, v2))
self.adjMatrix[v1][v2] = 1
self.adjMatrix[v2][v1] = 1
def removeEdge(self, v1, v2):
if self.adjMatrix[v1][v2] == 0:
print("No edge between %d and %d" % (v1, v2))
return
self.adjMatrix[v1][v2] = 0
self.adjMatrix[v2][v1] = 0
def containsEdge(self, v1, v2):
return True if self.adjMatrix[v1][v2] > 0 else False
def __len__(self):
return self.size
def toString(self):
for row in self.adjMatrix:
for val in row:
print('{:4}'.format(val)),
print
def main():
g = Graph(5)
g.addEdge(0, 1);
g.addEdge(0, 2);
g.addEdge(1, 2);
g.addEdge(2, 0);
g.addEdge(2, 3);
g.toString()
if __name__ == '__main__':
main()
