그래프가 있다고 가정합니다. 그래프가 강하게 연결되어 있는지 여부를 Kosaraju 알고리즘을 사용하여 확인해야 합니다. 그래프는 강하게 연결되어 있다고 하며, 두 정점 사이에 경로가 있으면 그래프가 연결된 것입니다. 무방향 그래프는 강하게 연결된 그래프입니다.
일부 무방향 그래프는 연결될 수 있지만 강력하게 연결되지는 않습니다. 이것은 강하게 연결된 그래프의 예입니다.
이것은 연결되었지만 강하게 연결되지 않은 그래프의 예입니다.
여기서는 다음과 같은 Kosaraju 알고리즘 단계를 사용하여 그래프가 강하게 연결되어 있는지 확인하는 방법을 살펴보겠습니다.
단계 -
-
모든 노드를 방문하지 않은 것으로 표시
-
임의의 정점 u에서 DFS 순회를 시작합니다. DFS가 모든 노드를 방문하는 데 실패하면 false를 반환합니다.
-
그래프의 모든 모서리 반전
-
모든 정점을 방문하지 않은 노드로 다시 설정
-
해당 정점 u에서 DFS 탐색을 시작합니다. DFS가 모든 노드를 방문하는 데 실패하면 false를 반환합니다. 그렇지 않으면 사실입니다.
예시
#include <iostream>
#include <list>
#include <stack>
using namespace std;
class Graph {
int V;
list<int> *adj;
void dfs(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 isStronglyConnected();
Graph reverseArc();
};
void Graph::dfs(int v, bool visited[]) {
visited[v] = true;
list<int>::iterator i;
for (i = adj[v].begin(); i != adj[v].end(); ++i)
if (!visited[*i])
dfs(*i, visited);
}
Graph Graph::reverseArc() {
Graph graph(V);
for (int v = 0; v < V; v++) {
list<int>::iterator i;
for(i = adj[v].begin(); i != adj[v].end(); ++i)
graph.adj[*i].push_back(v);
}
return graph;
}
void Graph::addEdge(int u, int v) {
adj[u].push_back(v);
}
bool Graph::isStronglyConnected() {
bool visited[V];
for (int i = 0; i < V; i++)
visited[i] = false;
dfs(0, visited);
for (int i = 0; i < V; i++)
if (visited[i] == false)
return false;
Graph graph = reverseArc();
for(int i = 0; i < V; i++)
visited[i] = false;
graph.dfs(0, visited);
for (int i = 0; i < V; i++)
if (visited[i] == false)
return false;
return true;
}
int main() {
Graph graph(5);
graph.addEdge(0, 1);
graph.addEdge(1, 2);
graph.addEdge(2, 3);
graph.addEdge(3, 0);
graph.addEdge(2, 4);
graph.addEdge(4, 2);
graph.isStronglyConnected()? cout << "This is strongly connected" : cout << "This is not strongly connected";
} 출력
This is strongly connected