-
強連通圖
鎖定
- 中文名
- 強連通圖
- 外文名
- Strongly Connected Graph
- 領 域
- 數學
- 對 象
- 有向圖
- 釋 義
- 有向圖中任意兩點間都存在路徑
- 相關概念
- 有向圖的強連通分量
強連通圖定理及其證明
證明：
（1）充分性：如果G中有一個迴路，它至少包含每個節點一次，則G中任兩個節點都是互相可達的，故G是強連通圖。
強連通圖強連通圖的邊問題
圖1強連通圖
（1）最多的情況：即n個頂點中兩兩相連，若不計方向，n個點兩兩相連有n（n-1）/2條邊，而由於強連通圖是有向圖，故每條邊有兩個方向，n（n-1）/2×2=n（n-1），故有n個頂點的強連通圖最多有n（n-1）條邊。
（2）最少的情況：即n個頂點圍成一個圈，且圈上各邊方向一致，即均為順時針或者逆時針，此時有n條邊。
下面舉例説明：如圖1所示，設ABCD四個點構成強連通圖，則：
（1）邊數最多有4×3=12條，如圖1所示。
圖2最少邊數
強連通圖強連通圖的判斷
問題：給一個有向圖，判斷給圖是否是強連通的。
如圖3所示，則是一個強連通圖。
對於無向圖則比較簡單，只需要從某一個頂點出發，使用BFS或DFS搜索，如果可以遍歷到所有的頂點，則給定的圖是連通的。
但這種方法對有向圖並不適用，例如 ： 1 -> 2 -> 3 -> 4，並不是強連通圖。
強連通圖方法一
可以調用DFS搜索 V 次，V是頂點的個數，就是對每個頂點都做一次DFS搜索，判斷是否可達。這樣的複雜度為O(V*(V+E))。
強連通圖方法二
可以參考求解連通分量的算法Tarjan算法，我們可以在O(V+E) 的時間內找到所有的連通分量，如果連通分量的個數為1，則説明該圖是強連通的。
#include <iostream>
#include <list>
#include <stack>
using namespace std;
class Graph
{
int V; // 頂點個數
list<int> *adj; // 鄰接表存儲
// DFS遍歷，打印以v為起點的 強連通分量
void DFSUtil(int v, bool visited[]);
public:
Graph(int V) { this->V = V; adj = new list<int>[V];}
~Graph() { delete [] adj; }
void addEdge(int v, int w);
//判斷是是否是強連通圖
bool isSC();
// 得到當前圖的逆置
Graph getTranspose();
};
void Graph::DFSUtil(int v, bool visited[])
{
visited[v] = true;
list<int>::iterator i;
for (i = adj[v].begin(); i != adj[v].end(); ++i)
if (!visited[*i])
DFSUtil(*i, visited);
}
// 返回當前圖的轉置圖
Graph Graph::getTranspose()
{
Graph g(V);
for (int v = 0; v < V; v++)
{
list<int>::iterator i;
for(i = adj[v].begin(); i != adj[v].end(); ++i)
{
g.adj[*i].push_back(v);
}
}
return g;
}
void Graph::addEdge(int v, int w)
{
adj[v].push_back(w);
}
bool Graph::isSC()
{
bool visited[V];
for (int i = 0; i < V; i++)
visited[i] = false;
DFSUtil(0, visited);
//如果有沒有被訪問的點就返回false
for (int i = 0; i < V; i++)
if (visited[i] == false)
return false;
// 創建當前圖的轉置圖
Graph gr = getTranspose();
for(int i = 0; i < V; i++)
visited[i] = false;
gr.DFSUtil(0, visited);
// 查看是否是所有的點都被訪問到
for (int i = 0; i < V; i++)
if (visited[i] == false)
return false;
return true;
}
// 測試
int main()
{
// 創建圖1
Graph g1(5);
g1.addEdge(0, 1);
g1.addEdge(1, 2);
g1.addEdge(2, 3);
g1.addEdge(3, 0);
g1.addEdge(2, 4);
g1.addEdge(4, 2);
g1.isSC()? cout << "Yes\n" : cout << "No\n";
// 創建圖2
Graph g2(4);
g2.addEdge(0, 1);
g2.addEdge(1, 2);
g2.addEdge(2, 3);
g2.isSC()? cout << "Yes\n" : cout << "No\n";
return 0;
}
