本文共 4984 字，大约阅读时间需要 16 分钟。
图的邻接矩阵和邻接表矩阵
void createGraph(vector>& edge, vector >& edge1,int start, int end, vector inDegree) { edge[start][end] = 1; edge1[start].push_back(end);}//打印存储的图void displayGraph(vector >& edge, vector >& edge1) { int i, j; cout << "邻接矩阵: " << endl; for (i = 0; i < VERTEXNUM; i++) { for (j = 0; j < VERTEXNUM; j++) { //printf("%d ", edge[i][j]); cout << edge[i][j] << " "; } cout << endl; } cout << "邻接表矩阵: " << endl; for (i = 0; i < VERTEXNUM; i++) { for (j = 0; j < edge1[i].size(); j++) { //printf("%d ", edge[i][j]); cout << edge1[i][j] << " "; } cout << endl; }}
深度优先遍历
void DFS(vector>& edge, vector & vertexStatusArr) { cout << "start BFT graph: " << endl; for (int i = 0; i < VERTEXNUM; i++) { DFScore(edge, i, vertexStatusArr); } cout << endl;}void DFScore(vector >& edge, int i, vector & vertexStatusArr) { if (vertexStatusArr[i] == 1) { return; } cout << i << " "; vertexStatusArr[i] = 1; for (int j = 0; j < VERTEXNUM; j++) { if (edge[i][j] == 1) { DFScore(edge, j, vertexStatusArr); } }}
广度优先遍历
void BFS(vector>& edge, vector & vertexStatusArr) { queue q; q.push(0); vertexStatusArr[0] = 1; int idx = 0; while (!q.empty()) { idx = q.front(); q.pop(); cout << idx << " "; for (int j = 0; j < VERTEXNUM; j++) { if (edge[idx][j] == 1 && vertexStatusArr[j] == 0) { q.push(j); vertexStatusArr[j] = 1; } } } cout << endl;}
拓扑排序算法
bool TopSort(vector>& G, int n, vector & inDegree) { vector res; int cnt = 0; // 记录加入图片排序的顶点数 queue q; for (int i = 0; i < n; i++) { if (inDegree[i] == 0) { // 入度为0,入队 q.push(i); } } while (!q.empty()) { // 取队首 int from = q.front(); q.pop(); // 访问from res.push_back(from); // 遍历邻接表:它能到的顶点 for (int i = 0; i < G[from].size(); i++) { int to = G[from][i]; if (--inDegree[to] == 0) { q.push(to); } } // 把form能到的边全部清空 G[from].clear(); cnt++; } for (auto x : res) { cout << x << ends; } cout << endl; if (cnt == n) { return true; } return false;}
一段代码实现一个图的多种遍历
#include#include #include using namespace std;#define VERTEXNUM 5void createGraph(vector >& edge, vector >& edge1 ,int start, int end, vector inDegree);void displayGraph(vector >& edge, vector >& edge1);void DFS(vector >& edge, vector & vertexStatusArr);void DFScore(vector >& edge, int i, vector & vertexStatusArr);void BFS(vector >& edge, vector & vertexStatusArr);bool TopSort(vector >& G, int n, vector & inDegree);int main(void) { //初始化邻接矩阵 vector >edge(VERTEXNUM, vector (VERTEXNUM, 0)); //存放顶点的遍历状态，0：未遍历，1：已遍历 vector vertexStatusArr(VERTEXNUM, 0); vector vertexStatusArr1(VERTEXNUM, 0); vector inDegree(VERTEXNUM);//入度 vector >edge1(VERTEXNUM);//邻接表矩阵 cout << "after init: " << endl; displayGraph(edge, edge1); //创建图 createGraph(edge, edge1, 0, 1, inDegree); createGraph(edge, edge1, 0, 2, inDegree); createGraph(edge, edge1, 2, 1, inDegree); createGraph(edge, edge1, 0, 3, inDegree); createGraph(edge, edge1, 1, 3, inDegree); createGraph(edge, edge1, 3, 4, inDegree); createGraph(edge, edge1, 2, 4, inDegree); for (auto x : edge1) { for (auto y : x) inDegree[y]++; } /*for (int i = 0; i < VERTEXNUM; i++) { cout << inDegree[i] << " "; } cout<< endl;*/ //可以展示入度。 cout << "after create: " << endl; displayGraph(edge,edge1); //深度优先遍历 cout << "DFS: " << endl; DFS(edge, vertexStatusArr); cout << "BFS: " << endl; BFS(edge, vertexStatusArr1); cout << "TopologicalSort: " << endl; bool res = TopSort(edge1, VERTEXNUM, inDegree); return 0;}
参考资料：https://blog.csdn.net/JMW1407/article/details/108590505?ops_request_misc=%25257B%252522request%25255Fid%252522%25253A%252522160751646119721940226866%252522%25252C%252522scm%252522%25253A%25252220140713.130102334.pc%25255Fall.%252522%25257D&request_id=160751646119721940226866&biz_id=0&utm_medium=distribute.pc_search_result.none-task-blog-2allfirst_rank_v2~rank_v29-6-108590505.first_rank_v2_pc_rank_v29&utm_term=C++%E6%B7%B1%E5%BA%A6%E4%BC%98%E5%85%88%E9%81%8D%E5%8E%86%E7%AE%97%E6%B3%95
https://blog.csdn.net/qjh5606/article/details/88633020?ops_request_misc=%25257B%252522request%25255Fid%252522%25253A%252522160751788919725271670256%252522%25252C%252522scm%252522%25253A%25252220140713.130102334.pc%25255Fall.%252522%25257D&request_id=160751788919725271670256&biz_id=0&utm_medium=distribute.pc_search_result.none-task-blog-2allfirst_rank_v2~rank_v29-7-88633020.first_rank_v2_pc_rank_v29&utm_term=C++%E6%8B%93%E6%89%91%E6%8E%92%E5%BA%8F%E7%AE%97%E6%B3%95 两个链接有一些理论层面的知识，可供参阅。