資料結構
網路
關係型資料庫管理系統
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝設計
法律研究列印有向圖中不屬於任何環的節點
在一個有向圖中，識別不屬於任何環的節點對於各種應用至關重要。這些節點構成了非迴圈子圖的基礎，並在理解整體圖結構中發揮著重要作用。透過使用有效的圖遍歷演算法，例如深度優先搜尋 (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 演算法可以成為一個有價值的工具。這兩種方法都提供了有效的解決方案，並且可以根據有向圖的特性和分析的預期結果進行調整。
180 次檢視
