邻接矩阵适合稠密图，邻接表适合稀疏图
1 // 稠密图 - 邻接矩阵 2 class DenseGraph { 3 4 private: 5 int n, m;//顶点和边 6 bool directed;//有向图还是无向图 7 vector<vector<bool>> g;//邻接矩阵的表示 8 //用bool值表示两个顶点之间是否有边 9 public: 10 DenseGraph(int n, int m) {//构造函数进行初始化 11 this->m = 0;//边数初始为0 12 this->n = n;//顶点数 13 for (int i = 0; i < n; i++) { 14 g.push_back(vector<bool>(n, false)); 15 } 16 } 17 ~DenseGraph() { 18 19 } 20 21 int V() { return n; } 22 int E() { return m; } 23 void addEdge(int v, int w) { 24 assert(v >= 0 && v < n); 25 assert(w >= 0 && w < n); 26 if (hasEdge(v, w)) return;//判断连个点是否相连 27 g[v][w] = true; 28 if (!directed) 29 g[w][v] = true; 30 31 m++; 32 } 33 bool hasEdge(int v, int w) { 34 assert(v >= 0 && v < n); 35 assert(w >= 0 && w < n); 36 return g[v][w]; 37 } 38 39 void show() { 40 41 for (int i = 0; i < n; i++) { 42 for (int j = 0; j < n; j++) 43 cout << g[i][j] << " "; 44 cout << endl; 45 } 46 } 47 48 49 class adjIterator {//构造一个图的迭代器，用来访问途中某一顶点的连接点 50 private: 51 DenseGraph &G;//图 52 int v;//顶点 53 int index;//索引 54 public: 55 adjIterator(DenseGraph &graph, int v) : G(graph) { 56 this->v = v; 57 this->index = -1; 58 } 59 60 int begin() { 61 62 index = -1; 63 return next();//将顶点自身 64 } 65 66 int next() { 67 for (index += 1; index < G.V(); index++) 68 if (G.g[v][index]) 69 return index; 70 return -1; 71 } 72 73 bool end() { 74 return index >= G.V(); 75 } 76 }; 77 78 };
1 // 稀疏图 - 邻接表 2 class SparseGraph { 3 4 private: 5 int n, m; 6 bool directed; 7 vector<vector<int>> g; 8 9 public: 10 SparseGraph(int n, bool directed) { 11 this->n = n; 12 this->m = 0; 13 this->directed = directed; 14 for (int i = 0; i < n; i++) 15 g.push_back(vector<int>()); 16 } 17 18 ~SparseGraph() { 19 20 } 21 22 int V() { return n; } 23 int E() { return m; } 24 25 void addEdge(int v, int w) { 26 27 assert(v >= 0 && v < n); 28 assert(w >= 0 && w < n); 29 30 g[v].push_back(w); 31 if (v != w && !directed) 32 g[w].push_back(v); 33 34 m++; 35 } 36 37 bool hasEdge(int v, int w) { 38 39 assert(v >= 0 && v < n); 40 assert(w >= 0 && w < n); 41 42 for (int i = 0; i < g[v].size(); i++) 43 if (g[v][i] == w) 44 return true; 45 return false; 46 } 47 48 void show() { 49 50 for (int i = 0; i < n; i++) { 51 cout << "vertex " << i << ": "; 52 for (int j = 0; j < g[i].size(); j++) 53 cout << g[i][j] << " "; 54 cout << endl; 55 } 56 } 57 58 59 class adjIterator { 60 private: 61 SparseGraph &G; 62 int v; 63 int index; 64 public: 65 adjIterator(SparseGraph &graph, int v) : G(graph) { 66 this->v = v; 67 this->index = 0; 68 } 69 70 int begin() { 71 index = 0; 72 if (G.g[v].size()) 73 return G.g[v][index]; 74 return -1; 75 } 76 77 int next() { 78 index++; 79 if (index < G.g[v].size()) 80 return G.g[v][index]; 81 return -1; 82 } 83 84 bool end() { 85 return index >= G.g[v].size(); 86 } 87 }; 88 };
读取图的信息的类：
1 template <typename Graph> 2 class ReadGraph { 3 4 public: 5 ReadGraph(Graph &graph, const string &filename) { 6 7 ifstream file(filename); 8 string line; 9 int V, E; 10 11 assert(file.is_open()); 12 13 assert(getline(file, line)); 14 stringstream ss(line); 15 ss >> V >> E; 16 17 assert(V == graph.V()); 18 19 for (int i = 0; i < E; i++) { 20 21 assert(getline(file, line)); 22 stringstream ss(line); 23 24 int a, b; 25 ss >> a >> b; 26 assert(a >= 0 && a < V); 27 assert(b >= 0 && b < V); 28 graph.addEdge(a, b); 29 } 30 } 31 };
遍历临边：
深度优先遍历：
深度优先搜索：
1 template <typename Graph>
2 class Component {
3
4 private:
5 Graph &G;
6 bool *visited;
7 int ccount;
8 int *id;
9
10 void dfs(int v) {
11
12 visited[v] = true;
13 id[v] = ccount;
14 typename Graph::adjIterator adj(G, v);
15 for (int i = adj.begin(); !adj.end(); i = adj.next()) {
16 if (!visited[i])
17 dfs(i);
18 }
19 }
20
21 public:
22 Component(Graph &graph) : G(graph) {
23
24 visited = new bool[G.V()];
25 id = new int[G.V()];
26 ccount = 0;//连通域个数
27 for (int i = 0; i < G.V(); i++) {
28 visited[i] = false;
29 id[i] = -1;
30 }
31
32 for (int i = 0; i < G.V(); i++)
33 if (!visited[i]) {
34 dfs(i);//深度优先搜索
35 ccount++;
36 }
37 }
38
39 ~Component() {
40 delete[] visited;
41 delete[] id;
42 }
43
44 int count() {
45 return ccount;
46 }
47
48 bool isConnected(int v, int w) {
49 assert(v >= 0 && v < G.V());
50 assert(w >= 0 && w < G.V());
51 return id[v] == id[w];
52 }
53 };
路径：
1 template <typename Graph> 2 class Path { 3 4 private: 5 Graph &G; 6 int s; 7 bool* visited; 8 int * from; 9 10 void dfs(int v) { 11 12 visited[v] = true; 13 14 typename Graph::adjIterator adj(G, v); 15 for (int i = adj.begin(); !adj.end(); i = adj.next()) { 16 if (!visited[i]) { 17 from[i] = v; 18 dfs(i); 19 } 20 } 21 } 22 23 public: 24 Path(Graph &graph, int s) :G(graph) { 25 26 // 算法初始化 27 assert(s >= 0 && s < G.V()); 28 29 visited = new bool[G.V()]; 30 from = new int[G.V()]; 31 for (int i = 0; i < G.V(); i++) { 32 visited[i] = false; 33 from[i] = -1; 34 } 35 this->s = s; 36 37 // 寻路算法 38 dfs(s); 39 } 40 41 ~Path() { 42 43 delete[] visited; 44 delete[] from; 45 } 46 47 bool hasPath(int w) { 48 assert(w >= 0 && w < G.V()); 49 return visited[w]; 50 } 51 52 void path(int w, vector<int> &vec) { 53 54 stack<int> s; 55 56 int p = w; 57 while (p != -1) { 58 s.push(p); 59 p = from[p]; 60 } 61 62 vec.clear(); 63 while (!s.empty()) { 64 vec.push_back(s.top()); 65 s.pop(); 66 } 67 } 68 69 void showPath(int w) { 70 71 vector<int> vec; 72 path(w, vec); 73 for (int i = 0; i < vec.size(); i++) { 74 cout << vec[i]; 75 if (i == vec.size() - 1) 76 cout << endl; 77 else 78 cout << " -> "; 79 } 80 } 81 };
广度优先遍历：使用队列实现。可以求出最短路径
1 template <typename Graph> 2 class ShortestPath { 3 4 private: 5 Graph &G; 6 int s; 7 bool *visited; 8 int *from; 9 int *ord; 10 11 public: 12 ShortestPath(Graph &graph, int s) :G(graph) { 13 14 // 算法初始化 15 assert(s >= 0 && s < graph.V()); 16 17 visited = new bool[graph.V()]; 18 from = new int[graph.V()]; 19 ord = new int[graph.V()]; 20 for (int i = 0; i < graph.V(); i++) { 21 visited[i] = false; 22 from[i] = -1; 23 ord[i] = -1; 24 } 25 this->s = s; 26 27 queue<int> q; 28 29 // 无向图最短路径算法 30 q.push(s); 31 visited[s] = true; 32 ord[s] = 0; 33 while (!q.empty()) { 34 35 int v = q.front(); 36 q.pop(); 37 38 typename Graph::adjIterator adj(G, v); 39 for (int i = adj.begin(); !adj.end(); i = adj.next()) 40 if (!visited[i]) { 41 q.push(i); 42 visited[i] = true; 43 from[i] = v; 44 ord[i] = ord[v] + 1; 45 } 46 } 47 48 } 49 50 ~ShortestPath() { 51 52 delete[] visited; 53 delete[] from; 54 delete[] ord; 55 } 56 57 bool hasPath(int w) { 58 assert(w >= 0 && w < G.V()); 59 return visited[w]; 60 } 61 62 void path(int w, vector<int> &vec) { 63 64 assert(w >= 0 && w < G.V()); 65 66 stack<int> s; 67 68 int p = w; 69 while (p != -1) { 70 s.push(p); 71 p = from[p]; 72 } 73 74 vec.clear(); 75 while (!s.empty()) { 76 vec.push_back(s.top()); 77 s.pop(); 78 } 79 } 80 81 void showPath(int w) { 82 83 assert(w >= 0 && w < G.V()); 84 85 vector<int> vec; 86 path(w, vec); 87 for (int i = 0; i < vec.size(); i++) { 88 cout << vec[i]; 89 if (i == vec.size() - 1) 90 cout << endl; 91 else 92 cout << " -> "; 93 } 94 } 95 96 int length(int w) { 97 assert(w >= 0 && w < G.V()); 98 return ord[w]; 99 } 100 };