• 图学习笔记

     1、邻接矩阵（vector二维数组）的DFS（递归实现）

    1. class Graph {
    2. public:
    3.     Graph(int vertices);
    4.     void addEdge(int from, int to);
    5.     void DFS(int startVertex);
    6.  
    7. private:
    8.     int vertices;
    9.     vectorint>> adjMatrix;
    10.     vector<bool> visited;
    11.  
    12.     void DFSRecursive(int vertex);
    13. };
    14.  
    15. Graph::Graph(int vertices) {
    16.     this->vertices = vertices;
    17.     adjMatrix.resize(vertices, vector<int>(vertices, 0));
    18.     visited.assign(vertices, false);
    19. }
    20.  
    21. // 无向图
    22. void Graph::addEdge(int from, int to) {
    23.     adjMatrix[from][to] = 1;
    24.     adjMatrix[to][from] = 1; // For undirected graph
    25. }
    26.  
    27. void Graph::DFS(int startVertex) {
    28.     for (int i = 0; i < vertices; i++) {
    29.         visited[i] = false;
    30.     }
    31.     DFSRecursive(startVertex);
    32.     // 确保每一个点都能被遍历到，包括孤立点
    33.     for (int i = 0; i < vertices; i++) {
    34.         if(visited[i] == 0)    
    35.             DFSRecursive(i);
    36.     }
    37. }
    38.  
    39. void Graph::DFSRecursive(int vertex) {
    40.     visited[vertex] = true;
    41.     cout << "Visited vertex: " << vertex << endl;
    42.  
    43.     for (int i = 0; i < vertices; i++) {
    44.         if (adjMatrix[vertex][i] == 1 && !visited[i]) {
    45.             DFSRecursive(i);
    46.         }
    47.     }
    48. }

      2、邻接表（vector实现）的DFS（栈实现）

    1. class Graph {
    2. public:
    3.     Graph(int vertices);
    4.     void addEdge(int from, int to);
    5.     void DFS(int startVertex);
    6.  
    7. private:
    8.     int vertices;
    9.     vectorint>> adjList;
    10. };
    11.  
    12. Graph::Graph(int vertices) {
    13.     this->vertices = vertices;
    14.     adjList.resize(vertices);
    15. }
    16.  
    17. // 邻接表，每行长度不一。无向图
    18. void Graph::addEdge(int from, int to) {
    19.     adjList[from].push_back(to);
    20.     adjList[to].push_back(from); 
    21. }
    22.  
    23. void Graph::DFS(int startVertex) {
    24.     vector<bool> visited(vertices, false);
    25.     stack<int> s;
    26.  
    27.     visited[startVertex] = true;
    28.     s.push(startVertex);
    29.  
    30.  
    31.     while (!s.empty()) {
    32.         int vertex = s.top();
    33.         s.pop();
    34.         cout << "Visited vertex: " << vertex << endl;
    35.  
    36.         for (int neighbor : adjList[vertex]) {
    37.             if (!visited[neighbor]) {
    38.                 visited[neighbor] = true;
    39.                 s.push(neighbor);
    40.             }
    41.         }
    42.     }
    43. }

    3、邻接表（vector实现）的BFS（队列实现）

    1. class Graph {
    2. public:
    3.     Graph(int vertices);
    4.     void addEdge(int from, int to);
    5.     void BFS(int startVertex);
    6.  
    7. private:
    8.     int vertices;
    9.     vectorint>> adjList;
    10. };
    11.  
    12. Graph::Graph(int vertices) {
    13.     this->vertices = vertices;
    14.     adjList.resize(vertices);
    15. }
    16.  
    17. // 无向图
    18. void Graph::addEdge(int from, int to) {
    19.     adjList[from].push_back(to);
    20.     adjList[to].push_back(from);
    21. }
    22.  
    23. void Graph::BFS(int startVertex) {
    24.     vector<bool> visited(vertices, false);
    25.     queue<int> q;
    26.  
    27.     visited[startVertex] = true;
    28.     q.push(startVertex);
    29.  
    30.     while (!q.empty()) {
    31.         int vertex = q.front();
    32.         q.pop();
    33.         cout << "Visited vertex: " << vertex << endl;
    34.  
    35.         for (int neighbor : adjList[vertex]) {
    36.             if (!visited[neighbor]) {
    37.                 visited[neighbor] = true;
    38.                 q.push(neighbor);
    39.             }
    40.         }
    41.     }
    42. }

    4、链式前向星DFS和BFS

    1. #include 
    2. #include 
    3. #include 
    4.  
    5. using namespace std;
    6.  
    7. const int maxn = 100000; // 假定最大顶点数
    8.  
    9. struct Edge {
    10.     int to, w, next; // 终点，边权，同起点的上一条边的编号
    11. } edge[maxn]; // 边集
    12.  
    13. int head[maxn]; // head[i]，表示以i为起点的第一条边在边集数组的位置（编号）
    14. int cnt = 0; // 记录边的数量
    15. int n, m; // 顶点数和边数
    16.  
    17. void init() {
    18.     for (int i = 1; i <= n; i++) head[i] = -1;
    19.     cnt = 0;
    20. }
    21.  
    22. // 添加新边
    23. void add_edge(int u, int v, int w) {
    24.     edge[cnt].to = v; // 终点
    25.     edge[cnt].w = w; // 权值
    26.     edge[cnt].next = head[u]; // 以u为起点上一条边的编号，也就是与这个边起点相同的上一条边的编号
    27.     head[u] = cnt++; // 更新以u为起点上一条边的编号
    28. }
    29.  
    30. void DFS(int startVertex) {
    31.     vector<bool> visited(n + 1, false);
    32.     stack<int> s;
    33.     
    34.     s.push(startVertex);
    35.     visited[startVertex] = true;
    36.     
    37.     while (!s.empty()) {
    38.         int vertex = s.top();
    39.         s.pop();
    40.         cout << "Visited vertex: " << vertex << endl;
    41.         
    42.         for (int j = head[vertex]; j != -1; j = edge[j].next) {
    43.             int neighborVertex = edge[j].to;
    44.             if (!visited[neighborVertex]) {
    45.                 s.push(neighborVertex);
    46.                 visited[neighborVertex] = true;
    47.             }
    48.         }
    49.     }
    50. }
    51.  
    52. void BFS(int startVertex) {
    53.     vector<bool> visited(n + 1, false);
    54.     queue<int> q;
    55.  
    56.     q.push(startVertex);
    57.     visited[startVertex] = true;
    58.  
    59.     while (!q.empty()) {
    60.         int vertex = q.front();
    61.         q.pop();
    62.         cout << "Visited vertex: " << vertex << endl;
    63.  
    64.         for (int j = head[vertex]; j != -1; j = edge[j].next) {
    65.             int neighborVertex = edge[j].to;
    66.             if (!visited[neighborVertex]) {
    67.                 q.push(neighborVertex);
    68.                 visited[neighborVertex] = true;
    69.             }
    70.         }
    71.     }
    72. }
    73.  
    74. int main() {
    75.     cin >> n >> m;
    76.     int u, v, w;
    77.     init(); // 初始化
    78.     for (int i = 1; i <= m; i++) // 输入m条边
    79.     {
    80.         cin >> u >> v >> w;
    81.         add_edge(u, v, w); // 加边
    82.     }
    83.  
    84.     int startVertex;
    85.     cout << "Enter the starting vertex for DFS: ";
    86.     cin >> startVertex;
    87.     DFS(startVertex);
    88.  
    89.     cout << "Enter the starting vertex for BFS: ";
    90.     cin >> startVertex;
    91.     BFS(startVertex);
    92.  
    93.     return 0;
    94. }

    5、无向图中，DFS判断连通块数量

    1. 	void DFS() {
    2. 		vis.resize(vertices);
    3. 		vis.assign(vertices, 0);
    4. 		unlinked_part = 0;       // unlinked_part记录连通块数量
    5.  
    6. 		for (int i = 0; i < vertices; i++) {
    7. 			if (vis[i] == 0) {
    8. 				DFSRecursive(i);
    9. 				unlinked_part++;
    10. 			}
    11. 		}
    12. 	}
    13. 	void DFSRecursive(int start) {
    14. 		vis[start] = 1;
    15. 		for (int i = 0; i < vertices; i++) {
    16. 			if (adjMatrix[start][i] == 1 && !vis[i]) {
    17. 				DFSRecursive(i);
    18. 			}
    19. 		}
    20. 	}

    6、最小生成树

    连通的带权无向图称为连通网。 最小生成树(Minimum Cost Spanning Tree)是代价最小的连通网的生成树，即该生成树上的边的权值和最小。
        
    最小生成树的性质：
    必须使用且仅使用连通网中的n-1条边来联结网络中的n个顶点；
    不能使用产生回路的边；
    各边上的权值的总和达到最小。
    （1）Prim算法 
    1. class Graph {
    2. 	int vertices;
    3. 	vectorint>> adjMatrix;
    4. 	mapint> ele1;
    5. 	map<int, string> ele2;
    6. 	vector<int> vis;
    7. 	struct Closeedge {
    8. 		int from;
    9. 		int lowcost;
    10. 	};
    11.  
    12. public:
    13. 	Graph() {}
    14.  
    15. 	void build_Graph() {
    16. 		int n;
    17. 		cin >> n;
    18. 		this->vertices = n;
    19. 		adjMatrix.resize(vertices, vector<int>(vertices, INF));
    20. 		
    21. 		string* e = new string[n];
    22. 		for (int i = 0; i < n; i++) {
    23. 			cin >> e[i];
    24. 			ele1[e[i]] = i;  // 记录节点字符对应的下标
    25. 			ele2[i] = e[i];  // 记录下标对应的字符
    26. 		}
    27. 		int m;
    28. 		cin >> m;
    29. 		edgenum = m;
    30. 		for (int i = 0; i < m; i++) {
    31. 			string from, to;
    32. 			int value;
    33. 			cin >> from >> to >> value;
    34. 			addEdge(ele1[from], ele1[to], value);
    35. 		}
    36. 	}
    37.  
    38. 	void addEdge(int from, int to,int value) {
    39. 		adjMatrix[from][to] = 1;
    40. 		adjMatrix[to][from] = 1;
    41. 	}
    42.  
    43.  
    44. 	int Min(vector vec) {
    45. 		int k = -1, minn = INF;
    46. 		for (int i = 0; i < vertices; i++) {
    47. 			if (minn > vec[i].lowcost && vec[i].lowcost > 0) {
    48. 				minn = vec[i].lowcost;
    49. 				k = i;
    50. 			}
    51. 		}
    52. 		return k;
    53. 	}
    54.  
    55. 	void Prim(string u) {
    56. 		int start = ele1[u];		 // start为起始节点的下标
    57. 		int totlowcost = 0;			 // 记录最小权值和
    58. 		vector<int> ans;			 // 记录被选节点
    59. 		map<int, int> ans_cost;		 // 记录最小生成树每条路径的权值
    60. 		vector closeedge(vertices);  // 用于保存未选顶点的最小权值边closedge和这条边的另一个已选顶点
    61.  
    62. 		for (int i = 0; i < vertices; i++) {
    63. 			closeedge[i] = { start, adjMatrix[start][i] };  // 初始化
    64. 		}
    65.  
    66. 		closeedge[start].lowcost = 0;
    67. 		for (int i = 1; i < vertices; i++) {
    68. 			int k = Min(closeedge);    // 选择当前已选节点到未选节点最小权值边对应的未选节点
    69. 			totlowcost += closeedge[k].lowcost;
    70. 			ans.push_back(k);
    71. 			ans_cost[k] = closeedge[k].lowcost;
    72. 			closeedge[k].lowcost = 0;  // 已选顶点的最小权值边置0，后续将不再被选
    73.  
    74. 			for (int j = 0; j < vertices; j++) {
    75. 				if (adjMatrix[k][j] < closeedge[j].lowcost) {
    76. 					closeedge[j] = Closeedge{ k, adjMatrix[k][j] };  // 更新未选顶点的最小权值边
    77. 				}
    78. 			}
    79. 		}
    80.  
    81. 		cout << totlowcost << endl;
    82. 		for (int i = 0; i < vertices - 1; i++) {
    83. 			int k = ans[i];
    84. 			cout << ele2[closeedge[k].from] << " " << ele2[k] << " " << ans_cost[k] << endl;
    85. 		}
    86. 	}
    87.  
    88. };

    （2）Kruscal算法

    1. class MFSet {
    2. 	int n;
    3. 	vector<int> fa;
    4. public:
    5. 	MFSet(int n) {
    6. 		this->n = n;
    7. 		fa.resize(n);
    8. 		for (int i = 0; i < n; i++)
    9. 			fa[i] = i;
    10. 	}
    11. 	int find(int k) {
    12. 		if (fa[k] != k) return fa[k] = find(fa[k]);
    13. 		else return k;
    14. 	}
    15. 	void concat(int i, int k) {
    16. 		fa[fa[i]] = fa[k];
    17. 		for (int i = 0; i < n; i++)
    18. 			find(i);
    19. 	}
    20. 	int check() {
    21. 		int che = fa[0];
    22. 		for (int i = 0; i < n; i++) {
    23. 			if (che != fa[i]) return 0;
    24. 		}
    25. 		return 1;
    26. 	}
    27. };
    28.  
    29. class Graph {
    30. 	int vertices;
    31. 	int edgenum;
    32. 	vectorint>> adjMatrix;
    33. 	mapint> ele1;
    34. 	map<int, string> ele2;
    35. 	vector<int> vis;
    36.  
    37. 	struct edge {
    38. 		int from;
    39. 		int to;
    40. 	};
    41.  
    42. public:
    43. 	Graph() {}
    44.  
    45. 	void build_Graph() {
    46. 		int n;
    47. 		cin >> n;
    48. 		this->vertices = n;
    49. 		adjMatrix.resize(vertices, vector<int>(vertices, INF));
    50. 		
    51. 		string* e = new string[n];
    52. 		for (int i = 0; i < n; i++) {
    53. 			cin >> e[i];
    54. 			ele1[e[i]] = i;  // 记录节点字符对应的下标
    55. 			ele2[i] = e[i];  // 记录下标对应的字符
    56. 		}
    57. 		int m;
    58. 		cin >> m;
    59. 		edgenum = m;
    60. 		for (int i = 0; i < m; i++) {
    61. 			string from, to;
    62. 			int value;
    63. 			cin >> from >> to >> value;
    64. 			addEdge(ele1[from], ele1[to], value);
    65. 		}
    66. 	}
    67.  
    68. 	void addEdge(int from, int to,int value) {
    69. 		adjMatrix[from][to] = 1;
    70. 		adjMatrix[to][from] = 1;
    71. 	}
    72.  
    73. 	void find_min(int &a, int &b, vectorint>>& vis_adj) {
    74. 		int minn = INF;
    75. 		for (int i = 0; i < vertices; i++) {
    76. 			for (int j = i+1; j < vertices; j++) {
    77. 				if (minn > adjMatrix[i][j] && vis_adj[i][j] == 0) {
    78. 					minn = adjMatrix[i][j];
    79. 					a = i, b = j;
    80. 				}
    81. 			}
    82. 		}
    83. 		vis_adj[a][b] = 1;
    84. 	}
    85. 	void Kruscal(){
    86. 		vector ans;             // 记录最小生成树上的每条路径
    87. 		vectorint>> vis_adj;  // 记录图中哪些边被选入最小生成树
    88. 		vis_adj.resize(vertices, vector<int>(vertices,0));
    89. 		MFSet mfset(vertices);        // 并查集，记录每个节点所在集合
    90. 		int totlowcost = 0;
    91.  
    92. 		int t = edgenum;
    93. 		while (t--) {
    94. 			int u, v;
    95. 			find_min(u, v,vis_adj);   // 寻找未被选的最小权值边
    96.  
    97. 			if (mfset.find(u) != mfset.find(v)) {  // 两个节点属于不同集合，该边选入最小生成树的路径中
    98. 				mfset.concat(u, v);
    99. 				ans.push_back({ u,v });
    100. 				totlowcost += adjMatrix[u][v];
    101. 			}
    102. 			
    103. 			if (mfset.check() == 1) break;   // 判断是否全部节点都属于同一集合，若是，则最小生成树已生成
    104. 		}
    105. 		if (mfset.check() == 0) {
    106. 			cout <<  -1 << endl;
    107. 		}
    108. 		else {
    109. 			cout << totlowcost << endl;
    110. 			for (int i = 0; i < ans.size(); i++) {
    111. 				cout << ele2[ans[i].from] << " " << ele2[ans[i].to] << " " << adjMatrix[ans[i].from][ans[i].to] << endl;
    112. 			}
    113. 		}
    114. 	}
    115. 	
    116. };

    7、无向图DFS生成森林

    1. #include 
    2. #include 
    3. #include 
    4. using namespace std;
    5.  
    6. // 树节点
    7. struct treenode{
    8.     int val;
    9.     vector son; // 存儿子节点指针
    10.     treenode(int n) { val = n; }
    11. };
    12.  
    13. vector Root;  // 存每棵树的树根
    14.  
    15.  
    16. class Graph {
    17. public:
    18.     Graph(int vertices);
    19.     void addEdge(int from, int to);
    20.     void DFS();
    21.     treenode* DFSRecursive(int vertex);
    22.  
    23. private:
    24.     int vertices;
    25.     vectorint>> adjMatrix;
    26.     vector<bool> visited;
    27. };
    28.  
    29. Graph::Graph(int vertices) {
    30.     this->vertices = vertices;
    31.     adjMatrix.resize(vertices, vector<int>(vertices, 0));
    32.     visited.assign(vertices, false);
    33. }
    34.  
    35. // 无向图
    36. void Graph::addEdge(int from, int to) {
    37.     adjMatrix[from][to] = 1;
    38.     adjMatrix[to][from] = 1; 
    39. }
    40.  
    41. void Graph::DFS() {
    42.     visited.assign(vertices, 0);
    43.  
    44.     for (int i = 0; i < vertices; i++) {
    45.         if (visited[i] == 0) {
    46.             treenode* root;
    47.             root=DFSRecursive(i);
    48.             Root.push_back(root);
    49.         }
    50.     }
    51. }
    52.  
    53. treenode* Graph::DFSRecursive(int vertex) {
    54.     visited[vertex] = true;
    55.     treenode* p = new treenode{ vertex };
    56.  
    57.     for (int i = 0; i < vertices; i++) {
    58.         if (adjMatrix[vertex][i] == 1 && !visited[i]) {
    59.             p->son.push_back(DFSRecursive(i));
    60.         }
    61.     }
    62.     return p;
    63. }
    64.  
    65. void show_tree(treenode *p) {
    66.     cout << p->val;
    67.     for (int i = 0; i < p->son.size(); i++) {
    68.         if(p != nullptr)
    69.             show_tree(p->son[i]);
    70.     }
    71. }
    72.  
    73. int main() {
    74.     int n, m;
    75.     cin >> n >> m;
    76.     Graph G(n);
    77.     for (int i = 0; i < m; i++) {
    78.         int u, v;
    79.         cin >> u >> v;
    80.         G.addEdge(u, v);
    81.         G.addEdge(u, v);
    82.     }
    83.     G.DFS();
    84.     
    85.     for (int i = 0; i < Root.size(); i++) {
    86.         show_tree(Root[i]);
    87.         cout << endl;
    88.     }
    89.     return 0;
    90. }

    8、图的最短路径（迪杰斯特拉算法）

    1. #include
    2. #include
    3. #include
    4. #include
    5. #include
    6. #include
    7. #include
    8. #define INF 0x3f3f3f3f
    9. using namespace std;
    10.  
    11.  
    12. class Graph {
    13. 	int vertices;
    14. 	vectorint>> adjMatrix;
    15. 	mapint> ele1;
    16. 	map<int, string> ele2;
    17. 	vector<int> vis;
    18.  
    19. public:
    20. 	Graph() {}
    21.  
    22. 	void build_Graph() {
    23. 		int n;
    24. 		cin >> n;
    25. 		this->vertices = n;
    26. 		adjMatrix.assign(vertices, vector<int>(vertices));
    27.  
    28. 		string* e = new string[n];
    29. 		for (int i = 0; i < n; i++) {
    30. 			cin >> e[i];
    31. 			ele1[e[i]] = i;  // 记录节点字符对应的下标
    32. 			ele2[i] = e[i];  // 记录下标对应的字符
    33. 		}
    34.  
    35. 		for (int i = 0; i < n; i++) {
    36. 			for (int j = 0; j < n; j++) {
    37. 				int tmp;
    38. 				cin >> tmp;
    39. 				addEdge(i, j, tmp);
    40. 			}
    41. 		}
    42. 	}
    43.  
    44. 	void addEdge(int from, int to, int value) {
    45. 		adjMatrix[from][to] = value;
    46. 	}
    47.  
    48. 	void Dijkstra() {
    49. 		vectorint>> path;   // 记录起点到其他每个节点最短路径的路径
    50. 		path.resize(vertices);
    51. 		vis.assign(vertices, 0);
    52. 		vector<int> dis;           // 记录起点到其他每个节点的最短路径距离
    53. 		dis.assign(vertices, INF);
    54.  
    55. 		string start;
    56. 		cin >> start;
    57. 		int v = ele1[start];
    58. 		vis[v] = 1;
    59. 		dis[v] = 0;
    60. 		for (int i = 0; i < vertices; i++) {
    61. 			if(adjMatrix[v][i])
    62. 			{
    63. 				dis[i] = dis[v] + adjMatrix[v][i];   // 更新起点到其他点的最短路径距离
    64. 				path[i].push(v);
    65. 			}
    66. 		}
    67.  
    68. 		for (int i = 0; i < vertices - 1; i++) {
    69. 			int Min = INF;
    70. 			for (int j = 0; j < vertices; j++)
    71. 				if (!vis[j] && Min > dis[j])
    72. 				{
    73. 					v = j;
    74. 					Min = dis[j];
    75. 				}
    76. 			vis[v] = 1;
    77.  
    78. 			// 用当先被选中点来更新到最短路径距离
    79. 			for (int j = 0; j < vertices; j++) {
    80. 				if (!vis[j] && adjMatrix[v][j] && Min + adjMatrix[v][j] < dis[j]) {
    81. 					path[j] = path[v];
    82. 					path[j].push(v);
    83. 					dis[j] = Min + adjMatrix[v][j];
    84. 				}
    85. 			}
    86. 		}
    87.  
    88. 		// 输出
    89. 		for (int i = 0; i < vertices; i++) {
    90. 			if (i != ele1[start]) {
    91. 				cout << start << "-" << ele2[i] << "-";
    92. 				if (dis[i] == INF) {
    93. 					cout << "-1" << endl;
    94. 				}
    95. 				else {
    96. 					cout << dis[i] << "----[";
    97. 					while(!path[i].empty()) {
    98. 						cout << ele2[path[i].front()] << " ";
    99. 						path[i].pop();
    100. 					}
    101. 					cout << ele2[i] << " ]" << endl;
    102. 				}
    103. 			}
    104. 		}
    105.  
    106. 	}
    107. };
    108.  
    109. int main() {
    110. 	int t;
    111. 	cin >> t;
    112. 	while (t--) {
    113. 		Graph G;
    114. 		G.build_Graph();
    115. 		G.Dijkstra();
    116. 	}
    117. }

    9、判断图上是否出现正环,即环上所有的边相乘大于1（货币套汇问题）

    1. #include
    2. #include
    3. #include
    4. #include
    5. #include
    6. #include
    7. #include
    8. #define INF 0x3f3f3f3f
    9. using namespace std;
    10.  
    11.  
    12. class Graph {
    13. 	int vertices;
    14. 	vectordouble>> adjMatrix;
    15. 	mapint> ele1;
    16. 	map<int, string> ele2;
    17. 	vector<int> vis;
    18. 	vectordouble>> check; // check记录从i到j节点路径权值的乘积
    19. 	int flag;
    20.  
    21. public:
    22. 	Graph() {}
    23.  
    24. 	void build_Graph() {
    25. 		int n;
    26. 		cin >> n;
    27. 		this->vertices = n;
    28. 		adjMatrix.assign(vertices, vector<double>(vertices, 0));
    29. 		int m;
    30. 		cin >> m;
    31.  
    32. 		string* e = new string[n];
    33. 		for (int i = 0; i < n; i++) {
    34. 			cin >> e[i];
    35. 			ele1[e[i]] = i;  // 记录节点字符对应的下标
    36. 			ele2[i] = e[i];  // 记录下标对应的字符
    37. 		}
    38.  
    39. 		for (int i = 0; i < m; i++) {
    40. 			string from, to;
    41. 			double value;
    42. 			cin >> from >> value >> to;
    43. 			addEdge(ele1[from], ele1[to], value);
    44. 		}
    45.  
    46. 	}
    47.  
    48. 	void addEdge(int from, int to, double value) {
    49. 		adjMatrix[from][to] = value;
    50. 	}
    51.  
    52.  
    53. 	int DFS() {
    54. 		vis.assign(vertices, 0);
    55. 		for (int i = 0; i < vertices; i++) {
    56. 			for (int j = 0; j < vertices; j++) {
    57. 				if (i == j) check[i][j] = 1;
    58. 				else check[i][j] = 0;
    59. 			}
    60. 		}
    61. 		flag = 0;
    62.  
    63. 		for (int i = 0; i < vertices; i++) {
    64. 			if (vis[i] == 0)
    65. 				DFSRecursive(i);
    66. 			if (flag == 1) return 1;
    67. 		}
    68. 		return 0;
    69. 	}
    70.  
    71. 	void DFSRecursive(int vertex) {
    72. 		vis[vertex] = true;
    73.  
    74. 		for (int i = 0; i < vertices; i++) {
    75.  
    76. 			// adjMatrix[vertex][i] && vis[i] == 1 即表示存在环，
    77. 			// check[i][vertex] * adjMatrix[vertex][i]即从i到j节点路径权值的乘积*j到i权值的乘积 = 环上权值乘积
    78. 			if (adjMatrix[vertex][i] && vis[i]) {  
    79. 				if (check[i][vertex] * adjMatrix[vertex][i] > 1) flag = 1;
    80. 				continue;
    81. 			}
    82. 			else if(adjMatrix[vertex][i]){
    83. 				for (int j = 0; j < vertices; j++) {
    84. 					check[j][i] = check[j][vertex] * adjMatrix[vertex][i];
    85. 				}
    86. 				DFSRecursive(i);
    87. 			}
    88. 		}
    89. 	}
    90.  
    91. };
    92.  
    93. int main() {
    94. 	int t;
    95. 	cin >> t;
    96. 	while (t--) {
    97. 		Graph G;
    98. 		G.build_Graph();
    99. 		if (G.DFS()) {
    100. 			cout << "YES" << endl;
    101. 		}
    102. 		else cout << "NO" << endl;
    103. 	}
    104. }

    10、键路径-STL版（含拓扑排序）

    1. #include
    2. #include
    3. #include
    4. #include
    5. #include
    6. #include
    7. #include
    8. #define INF 0x3f3f3f3f
    9. using namespace std;
    10.  
    11.  
    12. class Graph {
    13. 	int vertices;
    14. 	vectorint>> adjMatrix;
    15. 	vector<int> ve;    // 记录顶点的最早开始时间
    16. 	vector<int> vl;    // 记录顶点的最晚开始时间
    17. 	stack<int> st_re;  // 存AOE图的拓扑序列
    18. 	queue<int> q;      // 用于处理AOE图的拓扑序列
    19. 	vector<int> init;  // 记录节点入度
    20.  
    21. public:
    22. 	Graph() {}
    23.  
    24. 	void build_Graph() {
    25. 		int n;
    26. 		cin >> n;
    27. 		this->vertices = n;
    28. 		adjMatrix.assign(vertices, vector<int>(vertices, 0));
    29. 		init.assign(vertices, 0);
    30.  
    31. 		int m;
    32. 		cin >> m;
    33. 		for (int i = 0; i < m; i++) {
    34. 			int u, v, e;
    35. 			cin >> u >> v >> e;
    36. 			adjMatrix[u][v] = e;
    37. 			init[v]++;
    38. 		}
    39. 	}
    40.  
    41. 	void Topoorder() {
    42. 		for (int i = 0; i < vertices; i++) {
    43. 			if (init[i] == 0) q.push(i);
    44. 		}
    45. 		
    46. 		ve.assign(vertices, 0);
    47.  
    48. 		while (!q.empty()) {
    49. 			int w = q.front();
    50. 			st_re.push(w);
    51. 			q.pop();
    52. 			for (int i = 0; i < vertices; i++) {
    53. 				if (adjMatrix[w][i] != 0) {
    54. 					init[i]--;
    55. 					if (init[i] == 0) q.push(i);
    56. 					if (ve[w] + adjMatrix[w][i] > ve[i]) ve[i] = ve[w] + adjMatrix[w][i];
    57. 				}
    58. 			}
    59. 		}
    60.  
    61. 		// 输出每个顶点的最早开始时间
    62. 		for (int i = 0; i < vertices; i++) {
    63. 			cout << ve[i] << " ";
    64. 		}
    65. 		cout << endl;
    66.  
    67. 	}
    68. 	void CriticalPath() {
    69. 		vl.assign(vertices, ve[st_re.top()]); // ***注意：vl的初始化是用拓扑排序的最后一个顶点的ve值做初始化，而非
    70. 											  // 用ve[vertices - 1]做初始化，节点vertices - 1不一定为拓扑排序的最
    71. 											  // 后一个顶点，即不一定为AOE网的终点
    72. 		while (!st_re.empty()) {
    73. 			int w = st_re.top();
    74. 			st_re.pop();
    75. 			for (int i = 0; i < vertices; i++) {
    76. 				if (adjMatrix[i][w] != 0) {
    77. 					if (vl[w] - adjMatrix[i][w] < vl[i]) vl[i] = vl[w] - adjMatrix[i][w];
    78. 				}
    79. 			}
    80. 		}
    81.  
    82. 		// 输出每个顶点的最迟开始时间
    83. 		for (int i = 0; i < vertices; i++) {
    84. 			cout << vl[i] << " ";
    85. 		}
    86. 		cout << endl;
    87.  
    88. 		// 输出关键路径
    89. 		for (int i = 0; i < vertices; i++) {
    90. 			if (i == vertices - 1) cout << i << endl;
    91. 			if (ve[i] == vl[i] && i < vertices - 1) cout << i << "->";
    92. 		}
    93. 	}
    94. };
    95.  
    96. int main() {
    97. 	Graph G;
    98. 	G.build_Graph();
    99. 	G.Topoorder();
    100. 	G.CriticalPath();
    101. }

    11、旅游规划

    有了一张自驾旅游路线图，你会知道城市间的高速公路长度、以及该公路要收取的过路费。现在需要你写一个程序，帮助前来咨询的游客找一条出发地和目的地之间的最短路径。如果有若干条路径都是最短的，那么需要输出最便宜的一条路径。

    1. #include
    2. #include
    3. #include
    4. #include
    5. #include
    6. #include
    7. #include
    8. #define INF 0x3f3f3f3f
    9. using namespace std;
    10.  
    11.  
    12. class Graph {
    13. 	int vertices;
    14. 	struct vec{
    15. 		int wag;
    16. 		int charge;
    17. 	};
    18. 	vector> adjMatrix;
    19. 	vector<int> vis;
    20. 	int start, end;
    21.  
    22. public:
    23. 	Graph() {}
    24.  
    25. 	void build_Graph() {
    26. 		int n;
    27. 		cin >> n;
    28. 		this->vertices = n;
    29. 		adjMatrix.assign(vertices, vector(vertices, {0,0}));
    30.  
    31. 		int m;
    32. 		cin >> m;
    33.  
    34. 		cin >> start >> end;
    35.  
    36. 		for (int i = 0; i < m; i++) {
    37. 			int u, v, w, c;
    38. 			cin >> u >> v >> w >> c;
    39. 			addEdge(u, v, w, c);
    40. 		}
    41. 	}
    42.  
    43. 	void addEdge(int from, int to, int w, int c) {
    44. 		adjMatrix[from][to].wag = w;
    45. 		adjMatrix[from][to].charge = c;
    46. 	}
    47.  
    48. 	void Dijkstra() {
    49. 		vector<int> charge;
    50. 		charge.assign(vertices, 0);
    51. 		vis.assign(vertices, 0);
    52. 		vector<int> dis;
    53. 		dis.assign(vertices, INF);
    54.  
    55. 		int v = start;
    56. 		vis[v] = 1;
    57. 		dis[v] = 0;
    58. 		charge[v] = 0;
    59. 		
    60. 		for (int i = 0; i < vertices; i++) {
    61. 			if(adjMatrix[v][i].wag)
    62. 			{
    63. 				dis[i] = dis[v] + adjMatrix[v][i].wag;
    64. 				charge[i] += adjMatrix[v][i].charge;
    65. 			}
    66. 		}
    67.  
    68. 		for (int i = 0; i < vertices - 1; i++) {
    69. 			int Min = INF;
    70. 			for (int j = 0; j < vertices; j++)
    71. 				if (!vis[j] && Min > dis[j])
    72. 				{
    73. 					v = j;
    74. 					Min = dis[j];
    75. 				}
    76. 			vis[v] = 1;
    77.  
    78. 			int tmpcharge;
    79. 			for (int j = 0; j < vertices; j++) {
    80. 				tmpcharge = INF;
    81. 				if (!vis[j] && adjMatrix[v][j].wag && Min + adjMatrix[v][j].wag <= dis[j]) {
    82. 					if (Min + adjMatrix[v][j].wag == dis[j] && charge[v] + adjMatrix[v][j].charge < tmpcharge) tmpcharge = charge[v] + adjMatrix[v][j].charge;
    83. 					dis[j] = Min + adjMatrix[v][j].wag;
    84. 				}
    85. 				if(tmpcharge != INF) charge[j] = tmpcharge;
    86. 			}
    87. 		}
    88. 		cout << dis[end] << " " << charge[end];
    89. 	}
    90. };
    91.  
    92. int main() {
    93. 	
    94. 	Graph G;
    95. 	G.build_Graph();
    96. 	G.Dijkstra();
    97. 	
    98. }

    12、拯救007（坐标转为图节点）

    将坐标轴上的点看作图的节点，将岸上坐标、鳄鱼坐标和岛上中心看作节点，看能否从岛上中心的节点遍历到岸上节点，若可，即可以逃脱

    1. #include
    2. #include
    3. #include
    4. #include
    5. #include
    6. #include
    7. #include
    8. #include
    9. #define INF 0x3f3f3f3f
    10. using namespace std;
    11.  
    12.  
    13. class Graph {
    14. 	int vertices;
    15. 	vectorint>> adjMatrix;
    16. 	struct Node {
    17. 		int x, y;
    18. 		Node() {}
    19. 		Node(int xx, int yy) { x = xx, y = yy; }
    20. 	};
    21. 	vector<int> vis;
    22. 	int D;
    23. 	vector node;
    24. 	int flag;
    25.  
    26. public:
    27. 	Graph() {}
    28.  
    29. 	void build_Graph() {
    30. 		int n;
    31. 		cin >> n;
    32. 		this->vertices = n + 1;
    33. 		adjMatrix.assign(vertices + 1, vector<int>(vertices + 1, 0));
    34. 		cin >> D;
    35.  
    36. 		for (int i = 0; i < n; i++) {
    37. 			int x, y;
    38. 			cin >> x >> y;
    39. 			node.push_back(Node{ x,y });
    40. 		}
    41. 		node.push_back(Node{ 0,0 });
    42.  
    43. 		for (int i = 0; i < n; i++) {
    44. 			for (int j = 0; j < n; j++) {
    45. 				if (i == j || distance(node[i], node[j]) > D) adjMatrix[i][j] = 0;
    46. 				else if (distance(node[i], node[j]) <= D) {
    47. 					adjMatrix[i][j] = 1;
    48. 					adjMatrix[j][i] = 1;
    49. 				}
    50. 			}
    51. 		}
    52. 		for (int i = 0; i < n; i++) {
    53. 			if (node[i].x*node[i].x + node[i].y * node[i].y  <= (7.5 + D)*(7.5 + D)) {
    54. 				adjMatrix[n][i] = 1;
    55. 			}
    56. 			else {
    57. 				adjMatrix[n][i] = 0;	
    58. 			}
    59. 		}
    60. 		adjMatrix[n][n] = 0;
    61. 	}
    62.  
    63. 	double distance(Node a, Node b) {
    64. 		return sqrt((a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y));
    65. 	}
    66.  
    67. 	void addEdge(int from, int to, int value) {
    68. 		adjMatrix[from][to] = value;
    69. 	}
    70. 	int check(Node p) {
    71. 		if (p.x - (-50) <= D || 50 - p.x <= D || p.y - (-50) <= D || 50 - p.y <= D) {
    72. 			return 1;
    73. 		}
    74. 		else return 0;
    75. 	}
    76.  
    77.  
    78. 	int DFS() {
    79.  
    80. 		vis.assign(vertices, 0);
    81. 		flag = 0;
    82.  
    83. 		
    84. 		for (int i = 0; i < vertices - 1; i++)
    85. 		{
    86. 			if (!vis[i] && adjMatrix[vertices - 1][i])  // 遍历图的起点只能从（0，0）开始
    87. 			{
    88. 				
    89. 				DFSRecursive(i);
    90. 			}
    91. 			if (flag == 1) return 1;
    92. 		}
    93. 		return 0;
    94. 	}
    95.  
    96. 	void DFSRecursive(int vertex) {
    97. 		vis[vertex] = 1;
    98. 		if (check(node[vertex]) || flag == 1)
    99. 		{
    100. 			flag = 1; return;
    101. 		}
    102. 		for (int i = 0; i < vertices - 1; i++)
    103. 		{
    104. 			if (!vis[i] && adjMatrix[vertex][i])
    105. 			{
    106. 				DFSRecursive(i);
    107. 			}
    108. 		}
    109.  
    110. 	}
    111. };
    112.  
    113. int main() {
    114. 	Graph G;
    115. 	G.build_Graph();
    116. 	int check = G.DFS();
    117. 	if (check == 1) {
    118.  
    119. 		printf("Yes\n");
    120. 	}
    121. 	else {
    122. 		printf("No\n");
    123. 	}
    124. }

    13、判断环

    无向图：将图中度为1的顶点一个个删掉，同时把与该顶点相连的顶点度数减1，若图中仍存在度大于1的顶点，说明图中有环。

    有向图：将图中入度为0的顶点一个个删掉，同时把与该顶点相连的顶点入度减1，若图中仍存在入读不为0的顶点，说明图中有环。

    1. // 无向图判断环
    2.  
    3. #include
    4. #define MAXN 100010
    5. using namespace std;
    6.  
    7. vectorint>> vec;
    8. int n;
    9. vector<int> d;
    10.  
    11. int main()
    12. {
    13.     cin >> n;
    14.     d.resize(n + 1, 0);
    15.     vec.resize(n + 1);
    16.     for (int i = 1; i <= n; i++) {
    17.         int a, b;
    18.         cin >> a >> b;
    19.         d[a]++, d[b]++;
    20.         vec[a].push_back(b);
    21.         vec[b].push_back(a);
    22.     }
    23.  
    24.     queue<int> q;
    25.     for (int i = 1; i <= n; i++) {
    26.         if (d[i] == 1) q.push(i);
    27.     }
    28.     while (!q.empty()) {
    29.         int p = q.front();
    30.         q.pop();
    31.         for (int i = 0; i < vec[p].size(); i++) {
    32.             --d[vec[p][i]];
    33.             if (d[vec[p][i]] == 1) {
    34.                 q.push(vec[p][i]);
    35.             }
    36.         }
    37.     }
    38.     for (int i = 1; i <= n; i++) {
    39.         if (d[i] > 1) cout << i << " ";
    40.     }
    41.     return 0;
    42. }

  • 相关阅读:
    Linux：最全的开发常用命令
    python 多项式回归以及可视化
    流量封顶时代，容联七陌智能客服构筑企业“第二增长曲线”
    谷粒商城P85发布商品时规格参数不显示问题
    360 评估反馈工具 – 它的含义以及使用它的原因
    【BOOST C++ 17 出错处理】（3） Boost.Exception
    前端—— 分层模型和应用协议
    解决 MyBatis-Plus 中 ID 自增问题
    直播预告 | 10月12日虹科灭菌原理和灭菌工艺验证免费课程开讲，晚8点不见不散！
    1.0、C语言数据结构 ——初识数据结构和算法
  • 原文地址：https://blog.csdn.net/m0_74099951/article/details/134216177