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

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

admin2019-08-01  81
问题 对于一个使用邻接表存储的有向图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]==1&&finished[j]==0)flag=0； ／／dis结束前出现回边 else if(visited[j]==0){dfs(g，j)；finished[j]=1；} p=p一>next： }／／while t=(AreNode*)malloc(sizeof(AreNode))； ／／申请边结点 t->adjvex=v；t->next=final；final=t； ／／将该顶点插入链表 }／／dfs结束 im 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)： } 提示：此题考查的知识点是图的遍历。对有向图进行深度优先遍历可以判定图中是否有回路。若从有向图某个顶点v出发遍历，在dfs(v)结束之前，出现从顶点u到顶点v的回边，图中必存在环。由于dfs产生的是逆拓扑排序，故设一类型是指向邻接表的边结点的全局指针变量final，在dfs函数退出时，把顶点v插入到final所指的链表中，链表中的结点就是一个正常的拓扑序列。
解析
转载请注明原文地址:https://kaotiyun.com/show/skCi777K
本试题收录于： 计算机408题库学硕统考专业分类
0

计算机408

学硕统考专业

相关试题推荐
随机试题
最新回复(0)