打印有向图中不属于任何环的节点

在一个有向图中，识别不属于任何环的节点对于各种应用至关重要。这些节点构成了非循环子图的基础，并在理解整体图结构中发挥着重要作用。通过使用有效的图遍历算法，例如深度优先搜索 (DFS) 或 Tarjan 算法用于强连通分量，我们可以轻松地确定并打印不参与任何环的节点。这些方法确保了没有环参与的节点被突出显示，从而提供了对图的非循环部分的重要见解，并支持各种图相关的解决问题的情况。

使用的方法

  • 带环检测的深度优先搜索 (DFS)

  • Tarjan 算法用于强连通分量

带环检测的深度优先搜索 (DFS)

在这种方法中，我们使用深度优先搜索 (DFS) 来遍历有向图并在途中识别环。我们标记已访问的节点并保留一个列表来跟踪当前 DFS 路径中的节点。如果我们遇到后向边（指向当前 DFS 路径中节点的边），则我们检测到一个环。在 DFS 结束时，当前 DFS 路径中的节点将是环的一部分。不在当前 DFS 路径中的节点不属于任何环，可以打印出来。

算法

  • 对图执行深度优先搜索 (DFS)，从每个未访问的节点开始。

  • 在 DFS 期间，标记已访问的节点并将它们添加到当前 DFS 路径列表中。

  • 如果我们遇到后向边（指向当前 DFS 路径中节点的边），则我们检测到一个环并将当前 DFS 路径中的所有节点标记为环的一部分。

  • 当 DFS 对于某个节点完成时，将其从当前 DFS 路径列表中移除。

  • 在完成所有节点的 DFS 后，不属于任何环的节点将保持未标记，我们可以打印它们。

示例

Open Compiler
#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

Explore our latest online courses and learn new skills at your own pace. Enroll and become a certified expert to boost your career.

Tarjan 算法用于强连通分量

Tarjan 算法是一种强大的算法，用于在有向图中找到所有强连通分量。强连通分量是节点的一个子集，其中子集中任意两个节点之间都存在一条有向路径。不属于任何强连通分量的节点不属于任何环。通过找到强连通分量，我们可以识别不属于任何环的节点并打印它们。

算法

  • 将 Tarjan 算法应用于有向图以找到所有强连通分量。

  • 在找到所有强连通分量之后，识别属于强连通分量的节点。

  • 不属于任何强连通分量的节点不属于任何环，可以打印出来。

  • 这两种方法都能够有效地识别和打印有向图中不属于任何环的节点。DFS 方法提供了更简单和更直接的实现，而 Tarjan 算法更复杂，但提供了有关强连通分量的额外信息，这对于某些图相关的任务可能很有用。方法的选择取决于特定需求和主要问题的上下文。

示例

Open Compiler
#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 算法可以成为一个有价值的工具。这两种方法都提供了有效的解决方案，并且可以根据有向图的特性和分析的预期结果进行调整。

更新于: 2023年8月4日

180 次查看

开启你的 职业生涯

通过完成课程获得认证

开始学习
广告