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

2019-03-29 08:27

量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


第七章图习题_数据结构(3).doc 将本文的Word文档下载到电脑 下载失败或者文档不完整,请联系客服人员解决!

下一篇:2015春季高考考前训练 4

相关阅读
本类排行
× 注册会员免费下载(下载后可以自由复制和排版)

马上注册会员

注:下载文档有可能“只有目录或者内容不全”等情况,请下载之前注意辨别,如果您已付费且无法下载或内容有问题,请联系我们协助你处理。
微信: QQ: