Matryca sąsiedztwa wykresów (z przykładami kodu w językach C ++, Java i Python)

W tym samouczku dowiesz się, czym jest macierz sąsiedztwa. Znajdziesz również działające przykłady macierzy sąsiedztwa w językach C, C ++, Java i Python.

Macierz sąsiedztwa to sposób na przedstawienie wykresu G = (V, E) jako macierzy wartości logicznych.

Reprezentacja macierzy sąsiedztwa

Rozmiar macierzy to VxVgdzie Vjest liczba wierzchołków na wykresie, a wartość wpisu Aijwynosi 1 lub 0 w zależności od tego, czy istnieje krawędź od wierzchołka i do wierzchołka j.

Przykład macierzy sąsiedztwa

Poniższy obraz przedstawia wykres i odpowiadającą mu macierz sąsiedztwa.

Macierz sąsiedztwa z wykresu

W przypadku wykresów nieukierunkowanych macierz jest symetryczna względem przekątnej, ponieważ każda krawędź (i,j)jest również krawędzią (j,i).

Zalety macierzy sąsiedztwa

Podstawowe operacje, takie jak dodawanie krawędzi, usuwanie krawędzi i sprawdzanie, czy istnieje krawędź od wierzchołka i do wierzchołka j, są niezwykle efektywnymi czasowo operacjami o stałym czasie.

Jeśli wykres jest gęsty, a liczba krawędzi jest duża, pierwszym wyborem powinna być macierz sąsiedztwa. Nawet jeśli wykres i macierz sąsiedztwa są rzadkie, możemy to przedstawić za pomocą struktur danych dla rzadkich macierzy.

Największą zaletą jest jednak zastosowanie matryc. Niedawne postępy w sprzęcie umożliwiają nam wykonywanie nawet kosztownych operacji macierzowych na GPU.

Wykonując operacje na sąsiedniej macierzy, możemy uzyskać ważne informacje na temat natury wykresu i relacji między jego wierzchołkami.

Wady macierzy sąsiedztwa

VxVWymagania przestrzenne macierzy przylegania umożliwia hog pamięci. Wykresy na wolności zwykle nie mają zbyt wielu połączeń i jest to główny powód, dla którego listy sąsiedztwa są lepszym wyborem dla większości zadań.

Podczas gdy podstawowe operacje są łatwe, operacje takie jak inEdgesi outEdgessą drogie, gdy używa się reprezentacji macierzy sąsiedztwa.

Przykłady w Pythonie, Javie i C / C ++

Jeśli wiesz, jak tworzyć dwuwymiarowe tablice, wiesz również, jak utworzyć macierz sąsiedztwa.

Python Java C +

 # Adjacency Matrix representation in Python class Graph(object): # Initialize the matrix def __init__(self, size): self.adjMatrix = () for i in range(size): self.adjMatrix.append((0 for i in range(size))) self.size = size # Add edges def add_edge(self, v1, v2): if v1 == v2: print("Same vertex %d and %d" % (v1, v2)) self.adjMatrix(v1)(v2) = 1 self.adjMatrix(v2)(v1) = 1 # Remove edges def remove_edge(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 __len__(self): return self.size # Print the matrix def print_matrix(self): for row in self.adjMatrix: for val in row: print('(:4)'.format(val)), print def main(): g = Graph(5) g.add_edge(0, 1) g.add_edge(0, 2) g.add_edge(1, 2) g.add_edge(2, 0) g.add_edge(2, 3) g.print_matrix() if __name__ == '__main__': main()

 // Adjacency Matrix representation in Java public class Graph ( private boolean adjMatrix()(); private int numVertices; // Initialize the matrix public Graph(int numVertices) ( this.numVertices = numVertices; adjMatrix = new boolean(numVertices)(numVertices); ) // Add edges public void addEdge(int i, int j) ( adjMatrix(i)(j) = true; adjMatrix(j)(i) = true; ) // Remove edges public void removeEdge(int i, int j) ( adjMatrix(i)(j) = false; adjMatrix(j)(i) = false; ) // Print the matrix 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(""); ) 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()); ) )

 // Adjacency Matrix representation in C #include #define V 4 // Initialize the matrix to zero void init(int arr()(V)) ( int i, j; for (i = 0; i < V; i++) for (j = 0; j < V; j++) arr(i)(j) = 0; ) // Add edges void addEdge(int arr()(V), int i, int j) ( arr(i)(j) = 1; arr(j)(i) = 1; ) // Print the matrix void printAdjMatrix(int arr()(V)) ( int i, j; for (i = 0; i < V; i++) ( printf("%d: ", i); for (j = 0; j < V; j++) ( printf("%d ", arr(i)(j)); ) printf(""); ) ) int main() ( int adjMatrix(V)(V); init(adjMatrix); addEdge(adjMatrix, 0, 1); addEdge(adjMatrix, 0, 2); addEdge(adjMatrix, 1, 2); addEdge(adjMatrix, 2, 0); addEdge(adjMatrix, 2, 3); printAdjMatrix(adjMatrix); return 0; )

 // Adjacency Matrix representation in C++ #include using namespace std; class Graph ( private: bool** adjMatrix; int numVertices; public: // Initialize the matrix to zero 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; ) ) // Add edges void addEdge(int i, int j) ( adjMatrix(i)(j) = true; adjMatrix(j)(i) = true; ) // Remove edges void removeEdge(int i, int j) ( adjMatrix(i)(j) = false; adjMatrix(j)(i) = false; ) // Print the martix void toString() ( for (int i = 0; i < numVertices; i++) ( cout << i << " : "; for (int j = 0; j < numVertices; j++) cout << adjMatrix(i)(j) << " "; cout << ""; ) ) ~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(); )