数据结构实验4——拓扑排序

article/2025/10/4 17:31:06

一、实验名称：拓扑排序

二、实验学时：6学时

三、实验目的

1.理解拓扑排序的特性和算法；

2.通过构造图的邻接表，掌握拓扑排序算法。

四、实验内容(步骤)

1.建立邻接表存储的图；

2.对图进行拓扑排序；

3.输出拓扑排序序列。

实验源代码：

#include<iostream>
#include<cstring>
#include<cstdlib>#define MAXSIZE 10
#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0using namespace std;typedef int Elemtype;
typedef struct
{Elemtype data[MAXSIZE];int top;	
}SqStack;int InitStack(SqStack &S)
{S.top=-1;return OK;
}int StackEmpty(SqStack S)
{return (S.top==-1?TRUE:FALSE);
}int StackFull(SqStack S)
{return (S.top==MAXSIZE-1?TRUE:FALSE);
}int Push(SqStack &S,Elemtype e)
{if(StackFull(S))return ERROR;S.top++;S.data[S.top]=e;return OK; 
}int Pop(SqStack &S,Elemtype &e)
{if(StackEmpty(S))return ERROR;e=S.data[S.top];S.top--;return OK;
}// 定义图的存储结构
typedef char VertexType[20];
typedef struct ArcNode
{int adjvex; // 该弧所指向的顶点的位置struct ArcNode *nextarc; // 指向下一条弧的指针// InfoType *info; // 该弧相关信息的指针 
}ArcNode; typedef struct VNode
{VertexType data; // 顶点信息 V0ArcNode *firstarc; // 指向第一条依附该顶点的弧的指针 
}VNode;typedef struct
{VNode vertexs[20];int vexnum,arcnum; // 图的当前顶点数和弧数// GraphKind kind // 图的种类标志	
}ALGraph; int GetIndex(ALGraph G,char *v) // 获得顶点对应下标 
{int vIndex=-1;for(int i=0;i<G.vexnum;i++){if(strcmp(G.vertexs[i].data,v)==0){vIndex=i;break;	}	}if(vIndex==-1){printf("构成弧的顶点%s输入有误。\n",v);exit(0);}elsereturn vIndex;
}void CreateGraph(ALGraph &G)
{int i,k;ArcNode *p,*q,*s;VertexType vi,vj;printf("请输入有向图的顶点数和边（弧）数：");scanf("%d %d",&G.vexnum,&G.arcnum);// 创建头结点printf("请输入顶点名称：");for(i=0;i<G.vexnum;i++){scanf("%s",G.vertexs[i].data); // 结点数，可输入v0,v1,…等G.vertexs[i].firstarc=NULL;	}// 尾插入法建立各结点的单链表for(k=1;k<=G.arcnum;k++){printf("请输入构成第%d条弧的顶点：",k);scanf("%s%s",vi,vj);s=new ArcNode;s->adjvex=GetIndex(G,vj);s->nextarc=NULL;p=G.vertexs[GetIndex(G,vi)].firstarc;if(p==NULL){// 第1个结点G.vertexs[GetIndex(G,vi)].firstarc=s;}else{// 找到表尾while(p){q=p;p=p->nextarc;	}q->nextarc=s;}}
}void PrinAL(ALGraph G) // 以邻接表的形式输出图
{int i;ArcNode *p;printf("\n图的邻接表为：\n");for(i=0;i<G.vexnum;i++){if(G.vertexs[i].firstarc)printf("%d：%s----",i,G.vertexs[i].data);elseprintf("%d：%s---NULL",i,G.vertexs[i].data); p=G.vertexs[i].firstarc;while(p){printf("%d",p->adjvex);p=p->nextarc;if(p)printf("--->");}printf("\n");}
}void FindInDegree(ALGraph G,int indegree[])
{int i,k;ArcNode *p;for(i=0;i<G.vexnum;i++)indegree[i]=0;for(i=0;i<G.vexnum;i++){p=G.vertexs[i].firstarc;while(p){k=p->adjvex;indegree[k]++;p=p->nextarc;}}
}void TopologicalSort(ALGraph G) // 进行拓扑排序 
{ // 有向图 G 采用邻接表存储结构 int i,count,n,k; int indegree[20]; // 定义用于保存入度的数组 ArcNode *p;SqStack S;FindInDegree(G,indegree); // 求各顶点的入度存放于数组 indegree 中 InitStack(S); // 初始化栈 count=0; // 定义 count 用于记录输出的顶点数 for(i=0;i<G.vexnum;i++){if(indegree[i]==0)Push(S,i); // 将图中所有入度为0的顶点入栈 }printf("拓扑序列为：");while(!StackEmpty(S)){Pop(S,n); // 取出第一个入度为0的顶点入栈 printf("%s ",G.vertexs[n].data); // 输出 count++; // 计数 for(p=G.vertexs[n].firstarc;p!=NULL;p=p->nextarc){k=p->adjvex; // 获得 p点的后续顶点号 if(!(--indegree[k])) // 对 p点各后续顶点减1，如果入度为0则入栈 Push(S,k);}}printf("\n");if(count<G.vexnum)printf("有向图中存在环！\n"); // 结点未全部输出，图中含有回路 
}int main()
{ALGraph G;CreateGraph(G);PrinAL(G);TopologicalSort(G);return 0;
}

运行结果