二维数组邻接矩阵存储(Adjacency matrix)
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 | // C++ tree_BFT // author: Li, Fuchai // date: 2022-2-10 #include<iostream> using namespace std; int vertArr[20][20]; //the adjacency matrix initially 0 int count = 0; void displayMatrix(int v) { int i, j; for(i = 0; i < v; i++) { for(j = 0; j < v; j++) { cout << vertArr[i][j] << " "; } cout << endl; } } void add_edge(int u, int v) { //function to add edge into the matrix vertArr[u][v] = 1; vertArr[v][u] = 1; } int main() { int v = 6; //there are 6 vertices in the graph add_edge(0, 4); add_edge(0, 3); add_edge(1, 2); add_edge(1, 4); add_edge(1, 5); add_edge(2, 3); add_edge(2, 5); add_edge(5, 3); add_edge(5, 4); displayMatrix(v); } |
邻接表存储(Adjacency List)
注意:同一个图,可以有多个不同的邻接表的表示方式。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 | /**************************************************************** * Description: Adjascency List representation in C++ * Author: Alex Li * Date: 2022-02-18 21:19:05 * LastEditTime: 2024-06-24 16:05:25 ****************************************************************/ #include <iostream> #include <vector> using namespace std; vector<vector<int> > adj; // Add edge void addEdge(int s, int d) { adj[s].push_back(d); adj[d].push_back(s); } // Print the graph void printGraph(int V) { for (int d = 0; d < V; ++d) { cout << "\n Vertex " << d << ":"; for (auto x : adj[d]) cout << "-> " << x; printf("\n"); } } int main() { int V = 5; adj.resize(V); addEdge(0, 1); addEdge(0, 2); addEdge(0, 3); addEdge(1, 2); addEdge(2, 4); printGraph(V); } |