数据结构讲义第7章.ppt

如何进行拓扑排序？ 一、从有向图中选取一个没有前驱的顶点，并输出之; 二、从有向图中删去此顶点以及所有以它为尾的弧; 重复上述两步，直至图空，或者图不空但找不到无前驱的顶点为止。后一种情况则说明有向图中存在环。 没有前驱 -- 入度为零 删除顶点及以它为尾的弧-- 弧头顶点的入度减1 如何在计算机中实现？ 针对上述两步操作，我们可采用邻接表作有向图的存储结构，且在头结点中增加一个存放顶点入度的数组。入度为零的顶点即为没有前驱的顶点，删除顶点及它为尾的弧的操作，则可换以弧头顶点的入度减1来实现。 为了避免重复检测入度为零的顶点，可另设一栈暂存所有入度为零的顶点。 关键路径 与AOV-网相对应的是AOE网，即边表示活动的图。 AOE-网是一个带权的有向无环图，其中，顶点表示事件，弧表示活动，权表示活动持续的时间。通常，AOE-网可用来估算工程的完成时间。 例P183页图7.29 前面已经谈到：对整个工程和系统，人们关心的是两个方面的问题：一是工程能否顺序进行；二是估算整个工程完成所必须的最短时间，对应于有向图，即为进行拓扑排序和关键路径的操作。 十字链表(主要用于有向图) 十字链表（Orthogonal List）是有向图的另一种链式存储结构。可以看成是将有向图的邻接表和逆接表结合起来得到的一种链表。 在十字链表中，对应于有向图中每一条弧有一个结点，对应于每个顶点也有一个结点。　　这些结点的结构如下所示： 弧结点有五个域：尾域　头域　链域hlink　链域tlink info域 头结点有三个域：data信息域 firstin firstout链域,分别指向以该顶点为弧头或弧尾的第一个弧结点。 　　例如，图（a)中所示图的十字链表如图（b)所示。若将有向图的邻接矩阵看成是稀疏矩阵的话，则十字链表也可以看成是邻接矩阵的链表存储结构，在图的十字链表中，弧结点所在链表非循环链表，结点这间相对位置自然形成，不一定按顶点序号有序，表头结点即顶点结点，它们之间而是顺序存储。 V4 　#define MAX_VERTEX_NUM 20 typedef struct ArcBox { 　　int tailvex, headvex; // 该弧的尾和头顶点的位置 　　Struct ArcBox *hlink, *tlink; 　　　　// 分别指向下一个弧头相同和弧尾相同的弧的指针域 　　InfoType *info; // 该弧相关信息的指针 } ArcBox; typedef struct VexNode { 　VertexType data; ArcBox *firstin, *firstout; // 分别指向该顶点第一条入弧和出弧 } VexNode; typedef struct { 　　VexNode xlist[MAX_VERTEX_NUM]; // 表头向量 　　int vexnum, arcnum; // 有向图的当前顶点数和弧数 } OLGraph; 　　只要输入n个顶点的信息和e条弧的信息，便可建立该有向图的十字链表，算法如下： Status CreateDG(OLGraph G) {//采用十字链表存储表示，构造有向图Ｇ（G.kind=DG) scanf(G.vexnum,G.arcnu,IncInfo); for(I=0;IG.vexnum;++I) { scanf(G.xlist[i].data); G.xlist[i].firstin=NULL;G.xlist[i].firstout=NULL;} for(k=0;kG.arcnum;++k) { scanf(v1,v2); i=LocateVex(G,v1); j=LocateVex(G,v2); p=(ArcBox *)malloc(sizeof(ArcBox)); *p={I,j,G.xlist[j].firstin,G.xlist[i].firstout,NULL} G.xlist[j].firstin=G.xlist[i].firstout=p; if(incInfo) Input(*p-info); } } 邻接多重表(主要用于无向图) 邻接多重表(Adjacency Multilist)是无向图的另一种种链式结构。虽然邻接表是无向图的一种很有效的存储结构，在邻接表中容易求得顶点和边的各种信息。但是，在邻接表中每一条边（vi,vj）有两个结点，分别在第i个和第j个链表中，这给某