极客笔记C++ 在有向图中打印不属于任何循环的节点
在协调图中，识别不属于任何循环的枢纽对于不同的应用程序非常重要。这些枢纽节点构成了非循环子图的基础，并在理解整体图结构中扮演重要角色。通过使用有效的图遍历算法，例如深度优先搜索（DFS）或Tarjan算法用于强连通分量，我们可以轻松确定和打印不参与任何循环的节点。这些方法确保突出显示没有循环参与的节点，为图的非循环部分提供有价值的见解，并支持各种与图相关的问题解决场景。
使用的方法
- 带有循环检测的深度优先搜索（DFS）
-
Tarjan算法用于强连通分量
带有循环检测的深度优先搜索（DFS）
在此方法中，我们使用深度优先搜索（DFS）遍历协调图并在途中检测循环。我们标记已访问的节点并保持一个列表来跟踪当前DFS路径中的节点。如果遇到一条反向边（指向当前DFS路径中的节点的边），我们就识别出一个循环。在DFS结束时，当前DFS路径中的节点将是循环的一部分。当前DFS路径中不存在的节点不属于任何循环，并可以被打印出来。
步骤
- 对图执行深度优先搜索（DFS），从每个未访问的节点开始。
-
在DFS过程中，标记已访问的节点并将其添加到当前DFS路径列表中。
-
如果遇到一条反向边（指向当前DFS路径中的节点的边），我们识别出一个循环，并将当前DFS路径中的所有节点标记为循环的一部分。
-
当DFS对一个节点完成后，将其从当前DFS路径列表中移除。
-
在对所有节点完成DFS后，不属于任何循环的节点将被保留下来，我们可以将它们打印出来。
示例
#include <iostream>
#include <vector>
class Graph {
public:
Graph(int numVertices);
void addEdge(int src, int dest);
void DFS();
private:
void DFSUtil(int v, std::vector<bool>& visited, std::vector<int>& dfsPath);
int numVertices;
std::vector<std::vector<int>> adjList;
};
Graph::Graph(int numVertices) : numVertices(numVertices) {
adjList.resize(numVertices);
}
void Graph::addEdge(int src, int dest) {
adjList[src].push_back(dest);
}
void Graph::DFSUtil(int v, std::vector<bool>& visited, std::vector<int>& dfsPath) {
visited[v] = true;
dfsPath.push_back(v);
for (int neighbor : adjList[v]) {
if (!visited[neighbor]) {
DFSUtil(neighbor, visited, dfsPath);
}
else {
std::cout << "Cycle found: ";
for (size_t i = 0; i < dfsPath.size(); ++i) {
if (dfsPath[i] == neighbor) {
while (i < dfsPath.size()) {
std::cout << dfsPath[i] << " ";
++i;
}
break;
}
}
std::cout << std::endl;
}
}
dfsPath.pop_back();
}
void Graph::DFS() {
std::vector<bool> visited(numVertices, false);
std::vector<int> dfsPath;
for (int i = 0; i < numVertices; ++i) {
if (!visited[i]) {
DFSUtil(i, visited, dfsPath);
}
}
}
int main() {
Graph graph(6);
graph.addEdge(0, 1);
graph.addEdge(1, 2);
graph.addEdge(2, 3);
graph.addEdge(3, 4);
graph.addEdge(4, 1);
graph.addEdge(4, 5);
std::cout << "DFS traversal with cycle detection:\n";
graph.DFS();
return 0;
}
输出
DFS traversal with cycle detection:
Cycle found: 1 2 3 4
塔尔贡算法求解强连通分量
塔尔贡算法是一种用于查找有向图中所有强连通分量的算法。强连通分量是指在一个子图中，任意两个节点之间存在一条连通路径。不属于任何强连通分量的节点也就不属于任何环。通过找到强连通分量，我们可以识别出不属于任何环的节点，并进行打印。
步骤
- 对于给定的有向图，应用塔尔贡算法来查找所有强连通分量。
-
在找到所有强连通分量之后，识别出属于某个强连通分量的节点。
-
不属于任何强连通分量的节点也就不属于任何环，并可以进行打印。
-
这两种方法都能找出并打印在有向图中不属于任何环的节点。深度优先搜索（DFS）方法提供了简单和直接的实现，而塔尔贡算法更加复杂，但提供了有关强连通分量的额外信息，这对于特定的图相关任务可能是有用的。方法的选择取决于特定要求和上下文。
示例
#include <iostream>
#include <vector>
#include <stack>
#include <algorithm>
using namespace std;
class Graph {
int V;
vector<vector<int>> adj;
vector<bool> visited;
vector<int> disc, low;
stack<int> st;
vector<vector<int>> SCCs;
vector<bool> essentialNodes;
public:
Graph(int V) : V(V) {
adj.resize(V);
visited.resize(V, false);
disc.resize(V, -1);
low.resize(V, -1);
essentialNodes.resize(V, true);
}
void addEdge(int u, int v) {
adj[u].push_back(v);
}
void tarjanDFS(int u) {
static int time = 0;
disc[u] = low[u] = ++time;
st.push(u);
visited[u] = true;
for (int v : adj[u]) {
if (disc[v] == -1) {
tarjanDFS(v);
low[u] = min(low[u], low[v]);
} else if (visited[v]) {
low[u] = min(low[u], disc[v]);
}
}
if (low[u] == disc[u]) {
vector<int> SCC;
int v;
do {
v = st.top();
st.pop();
SCC.push_back(v);
visited[v] = false;
} while (v != u);
SCCs.push_back(SCC);
}
}
void tarjan() {
for (int i = 0; i < V; ++i) {
if (disc[i] == -1) {
tarjanDFS(i);
}
}
}
void identifyEssentialNodes() {
for (const vector<int>& SCC : SCCs) {
for (int v : SCC) {
for (int u : adj[v]) {
if (find(SCC.begin(), SCC.end(), u) == SCC.end()) {
essentialNodes[u] = false;
}
}
}
}
}
void printEssentialNodes() {
cout << "Essential Nodes for Each SCC:\n";
for (int i = 0; i < V; ++i) {
if (essentialNodes[i]) {
cout << i << " ";
}
}
cout << endl;
}
};
int main() {
Graph g(6);
g.addEdge(0, 1);
g.addEdge(1, 2);
g.addEdge(2, 0);
g.addEdge(1, 3);
g.addEdge(3, 4);
g.addEdge(4, 5);
g.addEdge(5, 3);
g.tarjan();
g.identifyEssentialNodes();
g.printEssentialNodes();
return 0;
}
输出
Essential Nodes for Each SCC:
0 1 2 4 5
结论
这两种方法真正解决了在一个有向图中识别不属于任何环的中心问题。深度优先搜索（DFS）方法易于执行，并且需要最少的额外数据结构。另一方面，Tarjan算法提供了关于强连通分量的额外信息，在某些情况下可能会有用。
选择这两种方法之间的决策取决于问题的具体要求以及在识别与环不相关的节点之外是否需要额外的信息。通常情况下，如果唯一目标是查找不属于任何环的节点，则可能更倾向于使用DFS方法，因为它简单明了。然而，如果需要进一步分析强连通分量，则Tarjan算法可以是一个有价值的工具。这两种方法都提供了高效的解决方案，并可以根据有向图的特性和分析结果的期望进行调整。