第七章图习题_数据结构(3)

量final，在dfs函数退出时，把顶点v插入到final所指的链表中，链表中的结点就是一个正常的拓扑序列。邻接表的定义与本书相同，这里只写出拓扑排序算法。

int visited[]=0; finished[]=0; flag=1; //flag测试拓扑排序是否成功 ArcNode *final=null; //final是指向顶点链表的指针，初始化为0 void dfs(AdjList g,vertype v)

//以顶点v开始深度优先遍历有向图g，顶点信息就是顶点编号. {ArcNode *t; //指向边结点的临时变量

printf(\ while(p!=null) {j=p->adjvex;

if (visited[j]==1 && finished[j]==0) flag=0 //dfs结束前出现回边 else if(visited[j]==0) {dfs(g,j); finished[j]=1;} //if 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);

}// dfs-Topsort

百度搜索“77cn”或“免费范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，免费范文网，提供经典小说综合文库第七章图习题_数据结构(3)在线全文阅读。