《数据结构》课件-第7章(图)

★基本术语NorthChinaElectricPowerUniversity

图是由顶点的非空有穷集合与顶点之间关系(边或弧)的集合构成的结构,通常表示为

G=(V,E)其中,V为顶点集合,E为关系(边或弧)的集合.一.图的定义(b)这条边依附于顶点vi和vj。(vi,vj)<vi,vj>vjvivjvi

关于一条边或弧的表示方法:(1)

用图形:(2)用符号:(3)

用语言:(a)

顶点vi与vj是这条边的两个邻接点。NorthChinaElectricPowerUniversityv1v2v3v4

其中

V1={v1,v2,v3,v4}E1={(v1,v2),(v1,v3),(v1,v4),(v2,v3),(v2,v4),(v3,v4)}G1=(V1,E1)v1v2v3v4其中

V2={v1,v2,v3,v4}E2={<v1,v2>,<v2,v1>,<v2,v3>,<v4,v3>}G2=(V2,E2)NorthChinaElectricPowerUniversity

无向图：

有向图：与边有关的数据称为权,边上带权的图称为网络。二.图的分类对于（vi,vj)E,必有（vj,vi)E，并且偶对中顶点的前后顺序无关。若<vi,vj>E是顶点的有序偶对。

网(络)：v1v2v3v4v1v2v3v4v1v2v3v4104178NorthChinaElectricPowerUniversity1.顶点的度对于有向图而言,有:

顶点的出度:

以顶点vi为出发点的边的数目,记为OD(vi).

顶点的入度:

以顶点vi为终止点的边的数目,记为ID(vi).

TD(vi)=OD(vi)+ID(vi)三.名词术语依附于顶点vi的边的数目,记为TD(vi).v1v3v4v1v2v3v4v2NorthChinaElectricPowerUniversity

边的数目达到最大的图称为完全图.边的数目达到或接近最大的图称为稠密图,否则,称为稀疏图.

具有n个顶点的有向图最多有n(n-1)条边.

具有n个顶点的无向图最多有n(n-1)/2条边.

对于具有n个顶点,e条边的图,有

2e=

TD(vi)ni=1结论1结论2结论3NorthChinaElectricPowerUniversity2.

路径DCEBAP(A,E):

A,B,EA,C,D,E

出发点与终止点相同的路径称为回路或环；顶点序列中顶点不重复出现的路径称为简单路径。不带权的图的路径长度是指路径上所经过的边的数目，带权的图的路径长度是指路径上经过的边上的权值之和。

顶点vx到vy之间有路径P(vx,vy)的充分必要条件为:存在顶点序列vx,vi1,vi2,…,vim,vy,并且序列中相邻两个顶点构造的顶点偶对分别为图中的一条边。NorthChinaElectricPowerUniversity3.子图v1v2v3v4

对于图G=(V,E)与G´=(V´,E´),若有V´

V,E´

E,则称G´为G的一个子图.v1v2v3v4v1v2NorthChinaElectricPowerUniversity4.图的连通

无向图中顶点vi到vj有路径,则称顶点vi与vj是连通的。若无向图中任意两个顶点都连通,则称该无向图是连通的。

若有向图中顶点vi到vj有路径,并且顶点vj到vi也有路径,则称顶点vi与vj是连通的。若有向图中任意两个顶点都连通,则称该有向图是强连通的。(1)无向图的连通(2)有向图的连通NorthChinaElectricPowerUniversity5.生成树

包含具有n个顶点的连通图G的全部n个顶点,仅包含其n-1条边的连通子图称为G的一个生成树。v1v3v4v2v1v3v4v2v1v3v4v2v1v3v4v2v1v3v4v2NorthChinaElectricPowerUniversity对于一个图,需要存储的信息应该包括:(1)所有顶点的数据信息；(2)顶点之间关系(边或弧)的信息;(3)权的信息。★图的存储结构一.邻接矩阵存储方法1.定义一个一维数组VERTEX[1:n]存放图中所有顶点的数据信息.2.定义一个二维数组A[1:n,1:n]存放图中所有顶点之间关系的信息(该数组被称为邻接矩阵),有

1

当顶点vi到顶点vj有边时A[i][j]=

0

当顶点vi到顶点vj无边时

NorthChinaElectricPowerUniversity对于带权的图,有

wij

当顶点vi到顶点vj有边,且边的权为wij

A[i][j]=

当顶点vi到顶点vj无边时

oo0111101111011110A1=v1v2v3v4Vertex1[1:4]v1v2v3v4Vertex2[1:4]

4

6

7

8

A2=v1v2v3v4v1v2v3104178NorthChinaElectricPowerUniversity邻接矩阵的类型定义如下:#defineVnum图的顶点数enumadj{0,1};typedefadj_adjmatrix[vnum][vnum]adjmatrix;typedefstruct{VexTypeVexs[Vnum];//顶点的信息

adjmatrixarcs;//邻接矩阵}graph;建立无向网邻接矩阵的算法如下:voidbuild-graph(graph&ga){for(i=0;i<n;i++)scanf(“%d”,ga.Vexs[i]);for(i=0;i++;i<n)for(j=0;j++;j<n)ga.arcs[i][j]=maxint;for(k=0;k++;k<e)//读入边(i,j)和权

{scanf(“%d,%d,%d”,i,j,w);ga.arcs[i][j]=w;ga.arcs[j][i]=w;}}

NorthChinaElectricPowerUniversity(1)无向图的邻接矩阵一定是一个对称矩阵;(2)不带权的有向图的邻接矩阵一般是一个稀疏矩阵;(3)无向图的邻接矩阵的第i行(或第i列)非0或非

元素的个数为第i个顶点的度数;(4)有向图的邻接矩阵的第i行非0或非元素的个数为第i个顶点的出度;第i列非0或非元素的个数为第

i个顶点的入度。特点:NorthChinaElectricPowerUniversity二.邻接表存储方法核心思想:对具有n个顶点的图建立n个线性链表存储该图.1.每一个链表前面设置一个头结点,用来存放一个顶点的数据信息,称之为顶点结点.其结构为:vertexlink其中,vertex

域存放某个顶点的数据信息;

link域存放某个链表中第一个结点的地址.2.第i个链表中的每一个链结点(称之为边结点)表示以第i

个顶点为出发点的一条边;边结点的构造为nextweightadjvex其中,next

域为指针域;

weight

域为权值域(若图不带权,则无此域);

adjvex

域存放以第i个顶点为出发点的一条边的另一端点在头结点数组中的位置.n个头结点之间为一数组结构.NorthChinaElectricPowerUniversity1234v1v2v3v447861233^^^^(1)无向图的第i个链表中边结点的个数是第i个顶点度数.(2)有向图的第i个链表中边结点的个数是第i个顶点的出度。特点:^^^^1234v1v3v2v4234332411421v1v2v3v4v1v2v3v46478typedefstructedgenode{intadjvex;//该边所指向的顶点的序号

floatweight;//边上的权值

structedgenode*next;//指向下一条弧的指针}*edgeptr;typedefstruct{VerTypevertex;edgeptrlink;}vexnode;typedefvexnodeAdj_List[MAX_VERTEX_NUM];

邻接表的类型定义NorthChinaElectricPowerUniversity

voidbuild_adjlist(Adj_Listga){scanf(“%d,%d”,&n,&e);//读入顶点数，边数efor(i=0;i<n;i++)//初始化邻接表

{ga[i].vertex=i;ga[i].link=NULL;}for(k=0;k<e;k++){scanf(“%d,%d”,&i,&j);//读入顶点对<i,j>p=newstructedgenode;p->adjvex=j;p->next=ga[i].link;ga[i].link=p;}}建立图的邻接表的算法：NorthChinaElectricPowerUniversityNorthChinaElectricPowerUniversity1234v1v2v3v46412^^7284^^关于逆邻接表v1v2v3v46478三.十字链表存储方法

在用邻接表表示有向图时，有时需要同时使用邻接表和逆邻接表。用有向图的十字链表可把这两个结合起来表示。

其中，tail和head

分别表示弧的尾顶点和头顶点；dut是弧的权值；hlink

链接以head为头的另一条弧；tlink链接以tail为尾的另一条弧。另外，设立一个由n个表头结点构成的向量，每个表头结点存放一个顶点，其结构也由上述五个域组成，head域存放该顶点的入度；tail域存放出度;hlink链接以该顶点为头的弧；tlink链接以该顶点为尾的弧。tailheadduttlinkhlinkNorthChinaElectricPowerUniversity0030300000126347002322450000348001^^^^^21436781234123452^^^

在邻接多重表中,每一条边只有一个边结点。边结点的结构如下：

markvertex1vertex2path1path2

其中,mark是记录是否处理过的标记;vertex1和vertex2是该边两顶点位置。path1域指向下一条依附于顶点vertex1的边；path2是指向下一条依附于顶点vertex2的边。四.邻接多重表存储方法

顶点结点的结构存储顶点信息的结点表以顺序表方式组织,每一个顶点结点有两个数据域：其中，data存放与该顶点相关的信息，Firstout是指示第一条依附该顶点的边的指针。在邻接多重表中,所有依附于同一个顶点的边都链接在同一个单链表中。dataFirstoutNorthChinaElectricPowerUniversity

从顶点i出发,可以循链找到所有依附于该顶点的边，也可以找到它的所有邻接顶点。NorthChinaElectricPowerUniversityNorthChinaElectricPowerUniversityADEFCBABCDEF^^^^^^12345623461341245123534615例：已知一具有n个顶点的无向图G采用邻接表存储方法,

写一算法,删除图中数据信息为item的那个顶点.需要做的工作:(1)寻找满足条件的那个顶点;(2)从头结点数组中删除该顶点;(3)删除与该顶点相关的边;(4)修改有关的边结点的adjvex域的内容。NorthChinaElectricPowerUniversityADEFCBABCDEF^^^^^12345623461341245123534615ADEFCBABDEFF^^123456235131243514^^^NorthChinaElectricPowerUniversityvoidDel(g,n,item){k=0;for(i=1;i<=n;i++)if(g[i].vertex==item){k=i;break;}if(k==0)return;p=g[k].link;

for(i=k+1;i<=n;i++){g[i-1].vertex=g[i].vertex;g[i-1].link=g[i].link;}n=n–1;//顶点的个数减1//while(p!=null){q=p;p=p->next;deleteq;}

for(i=1;i<=n;i++){p=g[i].link;while(p!=null）

if(p->adjvex==k){if(g[i].link==p)g[i].link[i]=p->next;elseq->next:=p->next;r=p;p=p->next;deleter;}else{if(p->adjvex>k)p->adjvex=p->adjvex–1;q=p;p=p->next;}}}NorthChinaElectricPowerUniversity

从图中某个指定的顶点出发,按照某一原则对图中所有顶点都访问一次,得到一个由图中所有顶点组成的序列,这一过程称为图的遍历.原则:

从图中某个指定的顶点v出发,先访问顶点v,然后从顶点v未被访问过的一个邻接点W1出发,访问了顶点W1后，再从W1出发，访问和W1邻接且未被访问过的任意顶点W2，然后从W2出发进行如上访问，重复，直到某一顶点所有邻接点都被访问过时，接着退回到尚有邻接点未被访问过的顶点，再从该顶点出发，重复上述过程，直到所有的被访问过的顶点的邻接点都已被访问为止。一.深度优先搜索★图的遍历

为了标记某一时刻图中哪些顶点是否被访问,定义一维数组visited[1:n],有

1

表示第i个顶点已经被访问

visited[i]=

0

表示第i个顶点还未被访问

NorthChinaElectricPowerUniversity例如：用深度优先搜索法遍历下图。123456782

3^1

4

5^1

6

7^2

8^2

8^3

8^3

8^4

5

6

7^V1V2V3V4V5V6V7V812345678voiddfs(Adj_Listg,intv0)｛//从v0出发，深度优先遍历图g，g以邻接表为存储结构

printf(“%d”,v0);visited[v0]=1;//标志v0已访问

p=g[v0].link;//找v0的第一个邻接点

while(p!=NULL){if(visited[p->adjvex]==0)dfs(g,p->adjvex);p=p->next;//回溯—找v0的下一个邻接点

}}NorthChinaElectricPowerUniversity深度优先搜索的递归算法：voiddfs(Adj_Listg,intv0)｛top=0;printf(“%d”,v0);visited[v0]=1;//标志v0已访问

p=g[v0].link;//找v0的第一个邻接点

while(p!=NULL||top>0){while(p!=NULL){if(visited[p->adjvex]==1)p=p->next;//找v0的下一个邻接点

else{w=p->adjvex;printf(“%d”,w);visited[w]=1;top++;S[top]=p;p=g[w].link;}}if(top>0){p=S[top];top--;p=p->next;}}}NorthChinaElectricPowerUniversity深度优先搜索的非递归算法：

分析上述过程,在遍历图时,对图中每个顶点至多调用一次dfs过程，因为一旦某个顶点被标志成已被访问，就不再从它出发进行搜索。因此，遍历图的过程实质上是对每个顶点查找其邻接点的过程。其耗费的时间则取决于所采用的存储结构，当用二维数组表示邻接矩阵作图的存储结构时，查找每个顶点的邻接点所需时间为O(n2),其中n为图中顶点数;而当以邻接表作图的存储结构时，查找邻接点所需时间为O(e)，其中e为无向图中的边数或有向图中弧的个数。因此，当以邻接表作存储结构时，深度优先搜索遍历图的时间复杂度为O(n+e)。深度优先搜索遍历算法的复杂性分析：NorthChinaElectricPowerUniversity二.广度优先搜索原则:

从图中某个指定的顶点v出发,先访问顶点v,然后依次访问顶点v的各个未被访问过的邻接点W1,W2,…,Wt，然后再依次访问W1,W2,…,Wt的所有的未被访问过的邻接点，再从这些被访问的顶点出发，逐次进行访问，直到所有顶点都被访问到为止。12345678例如右图：从V1出发，V1访问了;

再访问与V1邻接的V2，V3;

然后再访问与V2邻接的V4、V5，与V3邻接的V6、V7;

再访问与V4邻接的V8则所有的顶点都被访问到了因此遍历结束。遍历的顺序是：V1→V2→V3→V4→V5→V6→V7→V8

①对于广度优先搜索的方法，我们用不着去记录所走过的路径。我们只需记录与每一个顶点相邻接的所有顶点，而且当访问完这些顶点时，按照先记录先搜索的方式，对被记录的顶点进行广度优先搜索。（即若W1在W2之前被访问，则W1的邻接点也在W2的邻接点之前被访问。）所以我们用一个队列Q来记录这些顶点是比较方便的（依次存放被访问的结点）。②和dfs算法一样，在这里也需要一个辅助函数Visited[W]来标志顶点是否被访问过。③我们仍假设图用邻接表来表示。算法：voidbfs(Adj_Listg,intv0)//g为图的邻接矩阵或邻接表，从V0出发，用广度优先搜索法//遍历图，visited[w]为标志向量，其初值为0NorthChinaElectricPowerUniversity{visited[v0]=1;printf(“%d”,v0);f=0;r=0;p=g[v0].link;do{while(p!=NULL){v=p->adjvex;if(visited[v]==0){q[r]=v;r++;printf(“%d”,v);visited[v]=1;}p=p->next;//找某一顶点的所有邻接点并进队

}if(f!=r)//v出队

{v=q[f];f++;p=g[v].link;}}while((p!=NULL)||(f!=r))}

NorthChinaElectricPowerUniversityNorthChinaElectricPowerUniversity

可以用深度优先搜索或广度优先搜索算法来判断图是否连通。在对无向图进行遍历时，对于连通图，仅需要一次搜索过程，图中的顶点就全部被访问。对于非连通图，则需要多次调用搜索过程，而每次调用得到的顶点访问序列恰好为其各个连通分量中的顶点集。三.求图的连通分量intCount_Component(adj_listg,intn)

{intcount;

for(v=0;v<n;v++)/*初始化visited数组

visited[v]=0;

count=0;

for(v=0;v<n;v++)

if(visited[v]==0)

{count++;

dfs(g,v);

}returncount;}

NorthChinaElectricPowerUniversity★最小生成树和最短路径问题

带权连通图中,总的权值之和最小的带权生成树为最小生成树.最小生成树也称最小代价生成树,或最小花费生成树.构造网的最小生成树的依据：在网中选择n-1条边，连接网的n个顶点；2.尽可能选取权值为最小的边。最小生成树：v4v2v6v5v3v116115691814192220最小生成树的权值

=56Kruskal算法：

1.设T的初态为空集；

2.当T中边数小于n-1时做下列工作①从E中选取权值最小的边(v,w)，并删除之；②若(v,w)不和T中的边一起构成回路，则将边(v,w)加入到T中去。1246536536215465124653①T为空NorthChinaElectricPowerUniversity124653②选权值最小的边(1,3)

从E中将其删去11246531③选E中最小的边(4,6)从E中将其删去212465312④从E中选最小的边(2,5)从E中将其删去3124653123⑤从E中选最小的边(3,6)从E中将其删去4NorthChinaElectricPowerUniversity⑥从E中选最小的边(3,4)，但加入T后会使T中出现回路，所以边(3,4)不可取，把边(3,4)从E中删除。再看(1,4)同样会使T构成回路，仍不可取，从E中删去(1,4)，选(2,3)，从E中删去(2,3),最后已够5条边了，这样生成树就是最小生成树。最小生成树可能不唯一，但权的总数相同。24653123415

算法的思想明确、也很简单，但具体实现时比较困难，需要解决一些具体的问题，譬如如何所选的新边没有和已选的边构成回路。算法讨论：NorthChinaElectricPowerUniversityPrim算法：

1.设V(T)的初态为空集(V(T)为落在生成树上的顶点集合);2.在连通图上任选一顶点加入到V(T)集合中去；

3.将下列步骤重复n-1次：①在i属于V(T)，j不属于V(T)的边中，选权值最小的边

(i,j)；②将顶点j加入到V(T)中去；③输出i,j及Wij。NorthChinaElectricPowerUniversity例：①初态V(T)=φ

②选①顶点=>V(T)=｛1｝③做n-1次1)边(1,2)的权值最小，∴将②=>V(T)=｛1,2｝;weight(1,2)=161246532)边(2,3)的权值最小，∴将③=>V(T)=｛1,2,3｝;

weight

(2,3)=53)边(3,4)的权值最小，∴将④=>V(T)=｛1,2,3,4｝;

weight(3,4)=616561819211114336NorthChinaElectricPowerUniversity4)边(2,6)的权值最小，∴将⑥=>V(T)=｛1,2,3,4,6｝;

weight(2,6)=115)边(4,5)的权值最小，∴将⑤=>V(T)=｛1,2,3,4,5,6｝;

weight(4,5)=18∑i=16Weight=561246531656181921111433612465316561811NorthChinaElectricPowerUniversity最短路径问题:一.路径长度的定义1.不带权的图:路径上所经过的边的数目。2.带权的图:路径上所经过的边上的权值之和.二.问题的提出三.解决问题所需要确定的数据结构1.图的存储:以1~n分别代表n个顶点,采用邻接矩阵存储该图,有

Wij

当顶点vi到顶点vj有边,且权为Wij

A[i,j]=

当顶点vi到顶点vj无边时

0

当vi=vj时

设出发顶点为v(通常称为源点)。确定源点到其他各顶点的最短路径，常应用于选择路线，架设电线等.NorthChinaElectricPowerUniversity2.设置一个标志数组S[1:n]记录源点v到图中哪些顶点的最短路径已经找到，有：

1表示源点到顶点i的最短路径已经找到

S[i]=

0

表示源点到顶点i的最短路径尚未找到初始时，

S[v]=1,S[i]=0

i=1,2,,niv{3.设置数组dist[1:n]分别记录源点v到图中各顶点的最短路径的路径长度，其中，dist[i]记录源点到顶点i的最短路径的长度；初始时，dist数组的值为邻接矩阵第v行的n个元素值。

4.设置数组path[1:n]分别记录源点v到图中各顶点的最短路径所经过的顶点序列，其中，path[i]记录源点到顶点i的路径，初始时，path[i]=

v

,

i=1,2,3,,n013524455010201015152033530v0是源点最短路径v0→v210v0→v2→v310+15=25v0→v2→v3→v110+15+20v0→v445v0→v5无路可走

从以上可以发现每一条最短路径中间所经过的顶点具有如下特点：下一条最短路径(设其终点为x)可能是<v0,x>,或者<v0,u,…,v,x>，而u,…,v都是已求得的最短路径终点。例

假设S为已求得的最短路径的终点的集合(S初态为空集)，则下一条长度次短的最短路径（设终点为x）：或者是弧<v0,x>；或者是中间经过S集合中顶点，最后到达顶点x的路径。Dijkstra算法思想：NorthChinaElectricPowerUniversity四.算法(用自然语言表达)

b)设S为已找到从v0出发的最短路径的终点的集合,它的初态为源点（v0)。

c)设从v0出发到G中其余各顶点(终点)vi的最短路径长度为：初态→dist[i]=cost[v0,vi]Vi∈V(G)②选择u，使dist[u]=Min｛dist[i]|vi不属于S,vi∈V(G)}

（则u为目前求得的一条从v0出发的最短路径的终点）令S=S∪｛u｝（u进入s）

①设cost为带权的邻接矩阵

a)cost<i,j>=<i,j>上的权值(i,j之间有弧)∞(i,j之间无弧)｛

③修改所有不在S的终点的最短路径的长度，若

dist[u]+cost[u,i]<dist[i]，则修改dist[i]为dist[i]=dist[u]+cost[u,i]同时修改相应的路径.④重复操作②③共n-1次，由此求得从v0到G中其余各顶点的最短路径是依路径长度递增的序列。voidshortpath(cost,v0)/*求从源点v0到其它各顶点的最短路径,cost为有向图的带权邻接矩阵，v0为其中某个顶点的编号；dist[i]为当前找到的从v0到i的最短路径长度；path[i]为相应的路径；max为计算机内允许的最大值*/

{for(i=0;i<n;i++){dist[i]=cost[v0][i];

if(dist[i]<max)path[i]=[v0]+[i];//[]表示集合，+表示两个集合相并

elsepath[i]=[];//[]表示为空集

}NorthChinaElectricPowerUniversity//建立dist及path的初态

s=char(v0);num=0;//s为已找到最短路径的终点的集合

while(num<n-1){wm=max;u=v0;for(i=0;i<n;i++)//选dist[i]的最小值

if(!(iins)&&dist[i]<wm)//若i不属于s且dist[i]<wm{u=i;wm=dist[i];}//按dist[i]的最小值选取了us=s+[u];//将u加入最短路径的终点集合sfor(i=0;i<n;i++)//修改dist和past的值

if(!(iins)&&dist[u]+cost[u][i]<dist[i])//若i不属于s{dist[i]=dist[u]+cost[u][i];path[i]=path[u]+[i];}num++;}}

算法执行时间：第一个FOR循环是O(n)，接下来循环共进行n-1次，每一次执行时间是O(n)，所以总的时间为O(n2)。NorthChinaElectricPowerUniversityNorthChinaElectricPowerUniversityFloyed算法思想：

从i到j的路径上每次增加一个结点k，看这个增加了一个结点k的新路径的长度是否比原来的路径长度小，若小,则以新路径代之,否则保持原路径。A(k)[i][j]=min{A(k-1)[i][j],A(k-1)[i][k]+A(k-1)[k][j]}(1≤k≤n)

算法计算公式：其中:A(k)[i][j]表示顶点i,j之间的中间点的序号不大于k的最短距离;

由于G中顶点编号不大于n，所以最后到了An[i][j]就代表i到j的最短路径之长。NorthChinaElectricPowerUniversity算法描述：voidall_path(cost){for(i=1;i<=n;i++)for(j=1;j<=n;j++){a[i][j]=cost[i][j];if((i!=j)&&(a[i][j]<max)path[i][j]=[i]+[j];}

for(k=1;k<=n;k++)for(i=1;i<=n;i++)for(j=1;j<=n;j++)if(a[i,k]+a[k,j]<a[i,j]){a[i][j]=a[i][k]+a[k][j];path[i][j]=path[i][k]+path[k][j];}}NorthChinaElectricPowerUniversitycost=04116023∞0cost:带权邻接矩阵A：最短路径长度P：相应的路径

例：641132ABC321初态K=0时，A(0)12312

304116023∞0

ABACPath(0)12312

3BABCCA

NorthChinaElectricPowerUniversityK=1时，A(1)123Path(1)123104111ABAC26022BABC33703CACABK=2时，A(2)123Path(2)12310461ABABC26022BABC33703CACABNorthChinaElectricPowerUniversityK=3时，A(3)123Path(3)12310461ABABC25022BCABC33703CACABNorthChinaElectricPowerUniversity★AOV网与拓扑排序一.AOV网举例：验收筹备招标备料进驻工地测量挖地基浇注水泥搭架子…例1NorthChinaElectricPowerUniversity程序语言数据结构离散数学软件工程操作系统编译原理数据库计算机组成汇编网络数字逻辑计算机导论例2二.AOV网的定义

以顶点表示活动，以有向边表示活动之间的优先关系的有向图称为AOV网。NorthChinaElectricPowerUniversity

在AOV网中，若顶点i到顶点j之间有有向路径，则称顶点i为顶点j的前驱，顶点j为顶点i的后继；若顶点i到顶点j之间为一条有向边，则称顶点i为顶点j的直接前驱，顶点j为顶点i的直接后继。

三.拓扑排序

检查AOV网是否存在回路的方法是对AOV网进行拓扑排序，构造一个序列，使得该序列满足条件：

1.若在AOV网中，顶点i优先于顶点j,则在该序列中也是顶点i优先于顶点j。

2.若在AOV网中，顶点i与顶点j之间不存在优先关系,则在该序列中建立它们的优先关系，即顶点i优先于顶点j，或顶点j优先于顶点i。

3.若能够构造出拓扑序列，则拓扑序列包含AOV网的全部顶点。NorthChinaElectricPowerUniversity

四.拓扑排序方法1.从AOV网中任选择一个没有前驱(入度为0)的顶点；2.从AOV网中去掉该顶点以及以该顶点为出发点的所有边；3.重复上述过程，直到网中的所有顶点都被去掉,或者网中还有顶点，但不存在入度为0的顶点。

五.算法思想

建立一个栈（这个栈存放入度为0的结点）检查邻接表，将所有入度为零的顶点送栈，随后输出入度为0的顶点。Vj输出时，将Vj的直接后继Vk(k=1,2,,…)的入度减1，并将入度减到零的顶点进栈。当栈为空时，则检查一下是否输出了有向图的全部顶点（n个）：若是，则排序结束；反之，则网中有环。一个好的算法，一般在时空两个方面都应尽量的节约，对于拓扑排序算法，我们可以另开辟一块空间作为栈，还可以想办法利用它现有的存储空间，形成一个链栈。NorthChinaElectricPowerUniversityv1v4v3v2v6v5v7v1v5v7v3v6v2v4例v4v3v2v6v7v4v3v2v6v5v7v4v3v2v7v4v3v7v4v7v7v1v4v3v2v6v5v7357^123456v1v2v3v4v5v6^7002111v7334^^7^6^7^voidtoposort(Adj_Listg)

/*假设G为有n个顶点,e条弧的有向图,g是它的邻接表的表头向量，每个分量有三个域vex,in,next，对入度为0的顶点设计带链的栈，top指示栈顶元素，in为入度*/{readlist();//输入e条弧并建立邻接表

top=0;

for(i=1;i<=n;i++)//查入度为零的顶点，并建立链栈

if(g[i].in==0){g[i].in=top;top=i;}NorthChinaElectricPowerUniversitym=0;//设m为计数器计算输出的顶点个数while(top!=0){j=top;top=g[top].in;//退栈printf(“v%d”,j);m++;//输出顶点并计数

q=g[j].link;//q是指针，指示以j为尾的弧

while(q!=NULL){k=q->vex;//顶点k为j的直接后继

g[k].in=g[k].in-1;//入度减1if(g[k].in==0){g[k].in=top;top=k;//入度为零的顶点进栈}q=q->next;}}if(m<n)printf(“thenetworkhavecycle”);//输出顶点数不足n，说明网中有环

}NorthChinaElectricPowerUniversity

假设有向图有n个顶点，e条边，那么建立邻接表的执行时间为O(e)；搜索入度为0的时间为O(n)；在拓扑排序过程中，若有向图无环，则每个顶点进一次栈，入度减1的运算在WHILEtop≠0的语句中共执行e次，所以总的执行时间为O(n+e)。当有向图中无环时，也可利用深度优先搜索进行拓扑排序。因为图中无环,则由图中某点出发进行深度优先搜索遍历时，最先退出dfs过程的顶点，即出度为0的顶点，是拓扑有序序列中最后一个顶点。由此，按退出dfs(深度)过程的先后记录下来的顶点序列，即为逆向的拓扑有序序列。

六.复杂性分析NorthChinaElectricPowerUniversity★AOE网与关键路径筹备付款签合同做预置件验收施工…招标7天联系材料8天图纸设计15天进驻工地4天运材料6天搬运3天例NorthChinaElectricPowerUniversity一.AOE网的定义

AOE网为一个带权的有向无环图，其中，顶点表示事件，有向边表示活动，边上的权值表示活动持续的时间。v1v4v2v3v5v7v9v8v6a1a2a3a4a5a6a7a8a9a10a1164511297244

正常情况下，AOE网中只有一个入度为0的顶点，称之为源点；有一个出度为0的顶点，称之为终点。NorthChinaElectricPowerUniversity1.只有在某个顶点所代表的事件发生以后,该顶点引发的活动才能开始。2.进入某事件的所有边所代表的活动都已完成,该顶点所代表的事件才能发生。AOE网的特点：1.关键路径的定义

从源点到终点的路径中具有最大路径长度的路径为关键路径;关键路径上的活动称为关键活动。二.关键路径2.关键路径的特点1)关键路径的长度为完成整个工程所需要的最短时间。2)关键路径的长度变化(即任意关键活动的权值变化)将影响整个工程的进度，而其他非关键活动在一定范围内的变化不会影响工期。NorthChinaElectricPowerUniversity求关键活动的思路：

e(i)

—

活动ai的最早开始时间

l(i)

—

活动ai的最迟开始时间若l(i)–a(i)=0，则说明活动ai为一个关键活动。Ve(k)—

事件k的最早发生时间kaiVl(k)—

事件k的最迟发生时间aik事件k的最早发生时间Ve(k)事件k的最迟发生时间Vl(k)活动的ai最早开始时间e(i)活动的ai最迟开始时间l(i)求e(i)=l(i)结论NorthChinaElectricPowerUniversity1.计算事件k的最早发