对于一个使用邻接表存储的有向图G,可以利用深度优先遍历方法,对该图中结点进行拓扑排序。其基本思想是:在遍历过程中,每访问一个顶点,就将其邻接到的顶点的入度减1,并对其未访问的、入度为0的邻接到的顶点进行递归。 (1)给出完成上述功能的图的邻接表定义

admin2019-08-01  35

问题 对于一个使用邻接表存储的有向图G,可以利用深度优先遍历方法,对该图中结点进行拓扑排序。其基本思想是:在遍历过程中,每访问一个顶点,就将其邻接到的顶点的入度减1,并对其未访问的、入度为0的邻接到的顶点进行递归。
    (1)给出完成上述功能的图的邻接表定义。
    (2)定义在算法中使用的全局辅助数组。
    (3)写出在遍历图的同时进行拓扑排序的算法。

选项

答案(1)邻接表定义 typedef struct ArcNode{ int adjvex; struct ArcNode*next; }ArcNode; typedef struct VNode{ vertype data; ArcNode*firstarc: }VNode,AdjList[MAX]; (2)全局数组定义 int visited[]=0;finished[]=0;flag=1; //flag测试拓扑排序是否成功 ArcNode*final=null: //final是指向顶点链表的指针,初始化为0 (3)算法 void dfs(AdjList g,vertype V){ //以顶点v开始深度优先遍历有向图g,顶点信息就是顶点编号 ArcNode*t: //指向边结点的临时变量 printf(”%d”,V); visited[v]=1; P=g[v].firstarc; while(P!=null){ j=p一>adjvex; if(visited[j]==l&&finished[j]==0)flag=0; //dfs结束前出现回边 else if(visited[j]==0){dfs(g,j);finished[j]=1;} P=P一>next: }//while t=(ArcNode*)malloc(sizeof(ArcNode)); //申请边结点 t一>adjvex=v:t一>next=final;final=t; //将该顶点插入链表 }//dfs结束 int dfs_Topsort(Adjlist g){ //对以邻接表为存储结构的有向图进行拓扑排序,拓扑成功返回1,否则返回0 i=1: while(flag&&i<=n) if(visited.[i]==0){dfs(g,i);finished[i]=1;}//if return(flag); }

解析
转载请注明原文地址:https://jikaoti.com/ti/QzGjFFFM
0

最新回复(0)