这是我的拓扑排序算法：C++
具体分析见注释，总体时间复杂度为O(n+e)
#include "ALDGraph.h"
#include "SqStack.h"
#include
#include
using namespace std;
//初始化inDegree[]数组，时间复杂度O(n+e)
static void findInDegree(ALDGraph G, int* inDegree)
{
for(int i = 0; i < G.vexNum; ++i)
{
ArcNode* p = G.vertexes[i].firstArc;
while(p)
{
++inDegree[p->adjVex];
p = p->nextArc;
}
}
}
Status TopologicalSort(ALDGraph G)
{
int* inDegree = new int[G.vexNum];
memset(inDegree, 0, sizeof(int)*G.vexNum);
//ERROR:注意不是memset(inDegree, 0, 20);第三个参数是总的字节数，而不是初始化元素的个数。
/*int inDegree[20];
memset(inDegree, 0, sizeof(int) * 20);*/
findInDegree(G, inDegree);
SqStack S;
InitStack_Sq(S);
//将入度为0的顶点入栈，时间复杂度为O(n)
for(int i = 0; i < G.vexNum; ++i)
{
if(0 == inDegree[i])
{
Push_Sq(S, i);
}
}
int cnt = 0;
bool first = true;
cout << "拓扑排序开始----------------\n";
cout << "拓扑排序之后的结果，如下：\n";
//拓扑排序主体， 时间复杂度为O(n+e)
while(!StackEmpty_Sq(S))
{
int i;
Pop_Sq(S, i);
if(first)
{
cout << G.vertexes[i].data;
first = false;
}
else
{
cout << " -> " << G.vertexes[i].data;
}
++cnt;
for(ArcNode* p = G.vertexes[i].firstArc; p; p = p->nextArc)
{
int k = p->adjVex;
if(0 == (--inDegree[k]))
{
Push_Sq(S, k);
}
}
}
cout << endl;
cout << "拓扑排序结束----------------\n\n";
if(cnt < G.vexNum)
{
cout << "此有向图中存在环路，拓扑排序出错" << endl;
return ERROR;
}
else
{
return OK;
}
delete[] inDegree;
}
如果觉得《图邻接表拓扑排序算法c语言完整 在用邻接表表示图时 拓扑排序算法时间复杂度为（）...》对你有帮助，请点赞、收藏，并留下你的观点哦！
