[#include[HTML_REMOVED]

include[HTML_REMOVED]

define MaxVex 100

using namespace std;

typedef struct EdgeNode{
int adjvex;
int weight;
struct EdgeNode* next;
}EdgeNode;

typedef struct VexNode{
int data;
EdgeNode * firstedge;
}VexNode;

typedef struct{
VexNode vex[MaxVex];
int vexnum,edgenum;
}Adjlist;

typedef struct {
int v0;
int v1;
int weight;
}EdgeInfo;//这个是我用来创建图的数据结构，也是kruskal的辅助数据结构

void create(Adjlist &M,EdgeInfo data[],int n){
for(int i=1;i<=M.vexnum;i) M.vex[i].firstedge=NULL;
for(int i=1;i<=n;i){
int u0=data[i].v0;
int u1=data[i].v1;
EdgeNode p=(EdgeNode )malloc(sizeof(EdgeNode));
//这里还必须要分配空间才能使用
p->adjvex=u1;
p->weight=data[i].weight;
p->next=M.vex[u0].firstedge;
M.vex[u0].firstedge=p;
}
}
//上述实现了构建邻接表
//这里实现拓扑排序
int indegree[MaxVex];
int topo[MaxVex];//这里最好实现一个数组，我们还要判断是否有环
void find_indegree(Adjlist G){
for(int i=1;i<=G.vexnum;i) indegree[i]=0;
for(int i=1;i<=G.vexnum;i){
EdgeNode *p=G.vex[i].firstedge;
while(p!=NULL){
int t=p->adjvex;
indegree[t]++;
p=p->next;
}
}
}

void toposort(Adjlist G,int topo[]){
find_indegree(G);
int stack[MaxVex];
int top=0,toponum=0;//tuponum表示当前tupo序列中有几个结点
for(int i=1;i<=G.vexnum;i){
if(indegree[i]==0){
stack[top]=i;
}
}
while(top>0){
int t=stack[–top];
cout<[HTML_REMOVED]adjvex;
indegree[k]–;
if(indegree[k]==0) stack[top++]=k;
p=p->next;
}
}
if(toponum==G.vexnum) cout<<”拓扑完成”;
}

int main(){
Adjlist G;
G.vexnum=6,G.edgenum=8;
EdgeInfo data[]={{0,0,0},{1,2,3},{1,3,2},{2,5,3},{2,4,2},{3,4,4},{3,6,3},
{4,6,2},{5,6,1}};
Adjlist &M=G;
create(M,data,8);
// for(int i=1;i<=G.vexnum;i++){
// EdgeNode* p=G.vex[i].firstedge;
// while(p!=NULL){
// cout<[HTML_REMOVED]adjvex<<’ ‘;
// p=p->next;
// }
// cout<<endl;
// }
//完美构建邻接表
toposort(G,topo);
}](https://blog.csdn.net/weixin_64084604/article/details/128475014?ops_request_misc=%257B%2522request%255Fid%2522%253A%2522BDD733B4-350E-4EF8-A17E-5C3DBC145E4F%2522%252C%2522scm%2522%253A%252220140713.130102334..%2522%257D&request_id=BDD733B4-350E-4EF8-A17E-5C3DBC145E4F&biz_id=0&utm_medium=distribute.pc_search_result.none-task-blog-2~all~top_positive~default-1-128475014-null-null.142^v100^pc_search_result_base5&utm_term=%E5%85%B3%E9%94%AE%E8%B7%AF%E5%BE%84&spm=1018.2226.3001.4187)