資料結構
網路
RDBMS
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝設計
法律研究查詢移除後不會斷開圖的邊
分析圖中每條邊的連通性，以找到移除後不會破壞圖的邊。我們可以透過系統地檢查移除單個邊的影響來識別哪些邊對於保持節點之間的連通性至關重要。“橋邊”或“關鍵邊”是指移除後仍然使圖保持連通的邊。這些邊對於維持圖的整體結構和避免斷開至關重要。在網路分析、交通規劃和基礎設施設計中，必須識別此類邊以確保系統的魯棒性和有效的通訊。
使用的方法
Tarjan 演算法
克魯斯卡爾演算法
Tarjan 演算法
為了在圖中找到關鍵邊並發現強連通分量，使用 Tarjan 演算法。它透過執行深度優先搜尋，根據遍歷的順序為每個節點分配唯一的標識（低連線值）。當節點的低連線值與其祖先的標識匹配時，就找到了一個強連通分量。同一分量內的節點透過非關鍵邊連線，這意味著可以移除它們而不會斷開圖。但是，必須保留連線來自不同分量的節點的邊以保持整體連通性。Tarjan 演算法用於有效地分析圖的結構並識別關鍵邊。
演算法
設定一個空棧來記錄已訪問的節點，一個空列表來儲存關鍵邊，以及一個計數器來跟蹤節點發現的順序。
從圖中的任意一點開始深度優先搜尋 (DFS) 探索。
根據發現的順序，在 DFS 期間為每個節點分配不同的低連線值，並將它們儲存在棧中。
訪問一個節點時，將其低連線值更新為其自身索引和其相鄰節點的低連線值的最小值，以便發現強連通分量 (SCC)。如果節點的低連線值與其索引一致，則該節點是強連通分量的根。透過從棧中彈出節點直到根節點，將節點新增到分量列表中。
繼續 DFS 探索，發現並存儲圖中的所有強連通分量。重複 SCC 識別。
調查強連通分量中每個節點的鄰居。
如果相鄰節點是另一個 SCC 的成員，則連線它們的邊是關鍵邊。
將關鍵邊新增到列表中以供進一步檢查，以便儲存它們。
繼續遍歷圖，直到每個節點都被檢視和處理。
在步驟 8 中獲得的關鍵邊列表包含如果移除會導致圖斷開的邊。為了保持整體連通性，這些邊至關重要。程式識別關鍵邊以進行圖完整性和結構分析。
示例
#include <iostream>
#include <vector>
using namespace std;
const int MAX_NODES = 1000;
vector<int> adj[MAX_NODES];
vector<bool> visited;
vector<int> disc, low;
vector<pair<int, int>> criticalEdges;
int timeCounter = 0;
void dfs(int u, int parent) {
visited[u] = true;
disc[u] = low[u] = ++timeCounter;
for (int v : adj[u]) {
if (v == parent) continue;
if (!visited[v]) {
dfs(v, u);
low[u] = min(low[u], low[v]);
if (low[v] > disc[u])
criticalEdges.emplace_back(min(u, v), max(u, v));
} else {
low[u] = min(low[u], disc[v]);
}
}
}
void findCriticalEdges(int nodes) {
visited.assign(nodes, false);
disc.assign(nodes, 0);
low.assign(nodes, 0);
criticalEdges.clear();
timeCounter = 0;
for (int i = 0; i < nodes; i++) {
if (!visited[i]) {
dfs(i, -1);
}
}
}
int main() {
int nodes = 5; // Number of nodes in the graph
// Add edges to the adjacency list
adj[0].push_back(1);
adj[1].push_back(0);
adj[1].push_back(2);
adj[2].push_back(1);
adj[1].push_back(3);
adj[3].push_back(1);
adj[3].push_back(4);
adj[4].push_back(3);
findCriticalEdges(nodes);
cout << "Critical edges in the Graph:\n";
for (const auto& edge : criticalEdges) {
cout << edge.first << " " << edge.second << "\n";
}
return 0;
}
輸出
Critical edges in the Graph: 1 2 3 4 1 3 0 1
克魯斯卡爾演算法
在查詢移除後不會斷開圖的邊的上下文中，使用克魯斯卡爾演算法建立最小生成樹 (MST)。該演算法迭代地將權重最小的邊新增到 MST 中，同時確保不會出現迴圈，按權重的升序對邊進行排序。對於保持圖內連通性至關重要的邊是包含在 MST 中的邊。其餘邊，即未包含在 MST 中的邊，可以被視為非關鍵邊，因為移除它們不會導致圖斷開，但可能會使圖更重且效率更低。
演算法
建立一個名為“non_critical_edges”的空列表，用於儲存非關鍵邊。
根據權重的遞增順序對 G 的邊進行排序。
建立一個不相交集資料結構，並將其初始化為跟蹤連線的元素。
為 G 中的每個頂點建立一個不相交集。
在排序後的邊列表中，對於每條邊 (u, v)，
驗證當新增邊 (u, v) 時 MST 是否會產生迴圈
使用不相交集資料結構找到包含頂點 u 和 v 的集合的根（代表）。
如果根不同，則不存在迴圈；將邊 (u, v) 新增到 MST 中。否則，跳過此邊並繼續下一個邊。
如果處理完所有邊後剩餘 (n − 1) 條邊，則 MST 完成。終止迴圈。
如果 MST 中的邊數少於 (n − 1)，則圖未完全連線並且存在非關鍵邊。
再次遍歷排序後的邊列表，將剩餘的邊（未在 MST 中找到）新增到“non_critical_edges”列表中。
現在，“non_critical_edges”中包含移除後不會導致圖斷開的邊。
示例
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
struct CustomEdge {
int u, v, weight;
};
struct UniqueDisjointSet {
vector<int> parent, rank;
UniqueDisjointSet(int n) {
parent.resize(n);
rank.resize(n, 0);
for (int i = 0; i < n; ++i)
parent[i] = i;
}
int find(int u) {
if (u != parent[u])
parent[u] = find(parent[u]);
return parent[u];
}
void union_sets(int u, int v) {
int root_u = find(u);
int root_v = find(v);
if (root_u != root_v) {
if (rank[root_u] < rank[root_v])
parent[root_u] = root_v;
else if (rank[root_u] > rank[root_v])
parent[root_v] = root_u;
else {
parent[root_v] = root_u;
rank[root_u]++;
}
}
}
};
vector<CustomEdge> findUniqueNonCriticalEdges(int n, vector<CustomEdge>& edges) {
vector<CustomEdge> non_critical_edges;
UniqueDisjointSet ds(n);
sort(edges.begin(), edges.end(), [](const CustomEdge& a, const CustomEdge& b) {
return a.weight < b.weight;
});
for (const auto& edge : edges) {
int u = edge.u;
int v = edge.v;
if (ds.find(u) != ds.find(v)) {
ds.union_sets(u, v);
}
else {
non_critical_edges.push_back(edge);
}
if (non_critical_edges.size() == n - 1)
break;
}
return non_critical_edges;
}
int main() {
int n = 5;
vector<CustomEdge> edges = {
{0, 1, 2},
{0, 2, 4},
{1, 2, 1},
{1, 3, 3},
{2, 3, 5},
{2, 4, 7},
{3, 4, 6}
};
vector<CustomEdge> unique_non_critical_edges = findUniqueNonCriticalEdges(n, edges);
cout << "Unique Non-Critical Edges:\n";
for (const auto& edge : unique_non_critical_edges) {
cout << "(" << edge.u << ", " << edge.v << ", " << edge.weight << ")\n";
}
return 0;
}
輸出
Unique Non-Critical Edges: (0, 2, 4) (2, 3, 5) (2, 4, 7)
結論
透過巧妙地使用 Tarjan 和克魯斯卡爾演算法，我們有效地識別了可移除的邊，而不會斷開圖。這些非關鍵邊對於保持圖的整體結構和避免斷開至關重要。雖然克魯斯卡爾演算法建立最小生成樹並識別非關鍵邊，但 Tarjan 演算法有助於發現強連通分量。邊連通性分析有助於識別為了斷開圖而必須移除的邊的絕對最小數量。在各種領域（包括網路分析、交通規劃和基礎設施設計）中，瞭解這些關鍵邊和非關鍵邊對於保持魯棒性和有效通訊至關重要。
138 次檢視
