列印有向圖中不屬於任何循環的節點

在協調圖中，識別不屬於任何循環的集線器對於不同的應用程式至關重要。這些中心建構了非循環子圖的基礎，並在理解一般圖表結構方面發揮重要作用。透過使用有效的圖表交叉計算，例如 Profundity First Hunt (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 

Tarjan 的強連通分量演算法

Tarjan 的計算是一種強大的計算，用於追蹤協調圖中所有重點關聯的部分。明確關聯的部分是集線器的子集，其中子集中的任兩個集線器之間存在協調方式。不屬於任何緊密關聯部件的輪轂也不屬於任何循環。透過尋找重點關聯的零件，我們可以識別不屬於任何循環的輪轂並列印它們\

演算法

• 將 Tarjan 的計算應用於引導圖，以追蹤所有重點關聯的部分。

• 在追蹤所有重要關聯部分後，區分對於緊密關聯部分至關重要的中心。

• 不屬於任何明確關聯部件的集線器不屬於任何循環，並且可以列印。

• 這兩種方法確實區分並印製了不屬於協調圖表中任何週期的中心。 DFS 方法提供了更簡單且更直接的執行，而 Tarjan 的計算更複雜，但提供了有關重點關聯部分的額外數據，這對於特定的圖表相關任務很有幫助。方法的決定取決於具體的需要和主要緊迫問題的背景。

範例

#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 的計算可能是一個重要的工具。這兩種方法提供了熟練的安排，並且可以根據協調圖表的屬性和考試的理想結果進行調整

以上是列印有向圖中不屬於任何循環的節點的詳細內容。更多資訊請關注PHP中文網其他相關文章！