拓扑排序的简单实现

输出如下的拓扑图：

image.png

具体代码如下：

#include <iostream>
#include <queue>

using namespace std;

int main()
{
char charArr[]={'A','B','C','D','E'};
int N =sizeof(charArr)/sizeof(char);
queue<int> mQueue;//用于保存入度为0的字符对应的下标
bool boolArr[N][N]={false};//用于保存两点之间是否有连接，并初始化为false
int indegree[N]={0}; //保存每一个点的入度大小，并初始化为0

//设置两点之间有连接则设为true
boolArr[0][1]=true,boolArr[0][2]=true,boolArr[1][2]=true,boolArr[1][3]=true,boolArr[2][3]=true,boolArr[2][4]=true,boolArr[4][3]=true;

for(int i=0;i<N;i++){
    for(int j=0;j<N;j++){
        if(boolArr[i][j]){
            indegree[j]++;
            cout<<i<<"——>"<<j<<endl;
        }
    }
}
for(int i=0;i<N;i++){
    cout<<charArr[i]<<"入度="<<indegree[i]<<" ";
    if(indegree[i]==0){
        mQueue.push(i);
    }
}
cout<<endl;
cout<<"输出字符序列如下所示:"<<endl;

while(!mQueue.empty()){
    int temp=mQueue.front();
    mQueue.pop();
    cout<<charArr[temp]<<" ";
    for(int i=0;i<N;i++){
        if(boolArr[temp][i]){
            indegree[i]--;
            if(indegree[i]==0){
                mQueue.push(i);
            }
        }
    }
}
return 0;

}

运行结果：

image.png