初学図論‐Kahnトポロジー並べ替えアルゴリズム(Kahn's Topological Sort Algorithm)
2525 ワード
筆者は比較的便利な隣接チェーンテーブル表現法を用いた.隣接マトリクスを使用すると、平方レベルの時間消費が必要になる場合があります.
便宜上,筆者はSTLライブラリにおけるキュー構造を用いた.キューが空の場合にループが終了し、エッジがまだ存在する場合は、トポロジー順序なしで図にループが存在することを示します.
コードは次のとおりです.
見てくれてありがとう~
便宜上,筆者はSTLライブラリにおけるキュー構造を用いた.キューが空の場合にループが終了し、エッジがまだ存在する場合は、トポロジー順序なしで図にループが存在することを示します.
コードは次のとおりです.
/**
* The Kahn's Topological Sort Algorithm in C++
* Using the Adjecency List
* Time Cost : O(|V|+|E|)
* Author: Zheng Chen / Arclabs001
* Copyright 2015 Xi'an University of Posts & Telecommunications
*/
#include <iostream>
#include <queue>
#include <vector>
using namespace std;
const int N = 5; // The number of Vertex
enum status {UNDISCOVERED,VISITED};
struct Vertex
{
int inDegree, outDegree;
int data;
status _stat;
}V[N];
vector<int> AdjList[N]; //Using vector to simulate the adjlist
queue<int> vertexQueue; //The call queue
/**
* Initialize the graph as below:
The Graph:
0->1->3
| | |
\/ \/ \/
2->4<--
* @return The pointer to the start vertex
*/
Vertex* init_graph()
{
while(!vertexQueue.empty())
vertexQueue.pop();
for(int i=0; i<N; i++)
{
AdjList[i].clear();
V[i]._stat = UNDISCOVERED;
V[i].data = i;
}
V[0].inDegree = 0; V[0].outDegree = 2;
V[1].inDegree = 1; V[1].outDegree = 3;
V[2].inDegree = 1; V[2].outDegree = 1;
V[3].inDegree = 1; V[3].outDegree = 1;
V[4].inDegree = 3; V[4].outDegree = 0;
AdjList[0].push_back(1); AdjList[0].push_back(2);
AdjList[1].push_back(3); AdjList[1].push_back(4);
AdjList[2].push_back(4);
AdjList[3].push_back(4);
return & V[0];
}
bool Topological_Sort()
{
for(int i=0; i<N; i++)
{
if(V[i].inDegree == 0)
vertexQueue.push(i);
}
while(!vertexQueue.empty())
{
int top = vertexQueue.front();
V[top].outDegree = 0;
V[top]._stat = VISITED;
int i=0;
for(int v : AdjList[top])
{
--V[v].inDegree;
AdjList[top][i++] = -1;
if(V[v].inDegree == 0)
vertexQueue.push(v);
}
cout<<top<<" ";
vertexQueue.pop();
}
for(int i=0; i<N; i++)
{
for(int v : AdjList[i])
if(v != -1)
{
return false;
}
}
return true;
}
int main()
{
init_graph();
bool status = Topological_Sort();
if(status == false)
{
cout<<"Error! The graph has at least one cycle!"<<endl;
}
return 0;
}
見てくれてありがとう~