数据结构第9章图

1、(vertex)：n 125634abcd无向图无向图有向图有向图v=1, 2, 3, 4, 5, 6e=(1, 2), (1, 5), (1,6), (2, 3), (2, 4), (3, 4), (4, 5), (4, 6)（边）（边）v= a, b, c, de= , , , （弧（弧）adt graph 数据对象数据对象: : d=ai|1 i n, n 0, ai属属elemtype类型类型 数据关系数据关系: : r1=| ai ,aj d, 1 i n, 1 j n, 每个元素可以有多个直接前驱和可以有多个直接后继每个元素可以有多个直接前驱和可以有多个直接后继 基本运算基本运算:

2、 : initgraph(t); cleargraph(t); dsf(t); bsf(t); 抽象数据类型数的定义abc1234。例：存在例：存在(1, 2)，则顶点，则顶点1与与2互为邻接点。互为邻接点。 存在存在, 则顶点则顶点a与与b互为邻接点。互为邻接点。125634abcd例：例：td(1)=3 td(4)=4 td(5)=2例：例：td(b)=id(b)+od(b) td(d)=id(d)+od(d)=2+1=3=2+3=50123子图子图0130123023任意图都是其自身子图任意图都是其自身子图abcd 8 1 93 4 11 23125634例：例：v1到到v3的路径：的路

3、径：123 、123423、16423、1544. 路径长度：路径长度： 2 、 5 、 4 、 3 .12563441532连通图连通图非连通图非连通图两个连通分量两个连通分量125634125634abcd abcd 强连通图强连通图非强连通图非强连通图cabd 两个强连通分量两个强连通分量 ) , ( , 否否则则 或或若若0 n ga-e*输入各顶点信息存入输入各顶点信息存入ga-vexs *输入各边信息（或权值）存入输入各边信息（或权值）存入ga-edages a=vexs1 2 3 4abef cd123456 abcdef(a, b) (a,e) (a, f )256 (b, a

4、) (b,c) (b, d)1 3 4 (c, b) (c,d) 2 4 (d, b) (d,c) (d, e) (d, f ) 2 3 5 6 (e, a) (e,d) ( f, a) ( f,d) 1 41 4 data firstarc 4 8 2 19 6 7 3 104 8 198 7 4 2 6adjvex info nextarc3 6 10 7 2 319 10adjvex nextarc注：在注：在无向图无向图中每中每个边生成两个结点个边生成两个结点？插入和删除？插入和删除(d,f )=(f,d)? 求顶点的度求顶点的度 data firstarc1234abcd 8 5 9

5、3 7 11 13邻接表：邻接表：在有向图中，将以该顶点作在有向图中，将以该顶点作为为弧尾顶点弧尾顶点的所有弧链接成单链表。的所有弧链接成单链表。abcd 2 8 4 74 91 3 1 5 2 11 3 13 data firstarc1234 abcd 3 3 4 5 4 13 1 8 4 111 7 4 9逆邻接表逆邻接表逆邻接表：逆邻接表：在有向图中，将在有向图中，将以该顶点作为以该顶点作为弧弧头顶点头顶点的所有弧的所有弧链接成单链表。链接成单链表。？求顶点的度？求顶点的度邻接表的结点结构和数据类型邻接表的结点结构和数据类型 data firstarc表头结点表头结点typedef s

6、truct anode int adjvex; /*邻接点存储序号邻接点存储序号*/ infotype info; /*若是网络存储权值若是网络存储权值*/ struct anode *nextarc; /*指向下一个边结点指向下一个边结点*/arcnode;typedef struct vertex data; /*存储顶点元素存储顶点元素*/ arcnode *firstarc; /*指向依附于该顶点的第一边指向依附于该顶点的第一边*/vnode;typedef vnode adjlistmaxv;typedef struct adjlist adjlist; int n,e;algrap

7、h; adjvex nextarc边结点边结点adjvex info nextarc data firstarcadjvex info nextarc123456 abcdef256 1 3 4 2 4 2 3 5 6 1 41 44 8 198 7 4 2 63 6 10 7 2 319 10abef cd 4 8 2 19 6 7 3 10建立邻接表建立邻接表*邻接表初始化邻接表初始化（置各单链表为空表（置各单链表为空表 ga.firstarc=null）*输入各顶点信息存入输入各顶点信息存入 ga.data*输入各边信息，生成新结点，插入相应的单链中。输入各边信息，生成新结点，插入相应的

8、单链中。abcd 8 5 93 7 11 13 data firstarc1234abcd 2 8 4 74 91 3 1 5 2 11 3 13邻接表的基本操作邻接表的基本操作插入：插入： *确定单链表确定单链表*生成新结点生成新结点63 6*头插链表头插链表注：注：有向图只插入有向图只插入(或删除）一个结点，或删除）一个结点，而无向图需插入（或删除）两个结点。而无向图需插入（或删除）两个结点。删除：删除： *确定结点确定结点*删除结点删除结点*释放结点释放结点 abcd 8 5 93 7 11 13a a a b a c a d a 1 2 a 1 4a 2 4 a 3 1 a 4 1 a

9、 4 2 a 4 3 tailvex headvex hlink tlink info弧结点弧结点data firstin firstout顶点结点顶点结点data firstin firstout顶点结点顶点结点tailvex headvex hlink tlink info弧结点弧结点typedef struct arcnode int tailvex,headvex; struct arcnode *hlink,*tlink; infotype info;arcnode;typedef struct vexnode vertextype data; arcnode *firstin,*f

10、irstout;vexnode;十字链表的数据类型十字链表的数据类型a 4 6(d, f)abef cd 4 8 2 19 6 7 3 10a bcdefa 1 2(a, b)a 1 5(a, e)a 1 6(a, f)a 2 3(b, c)a 2 4(b, d)a 3 4(c, d)a 4 5(d, e) mark ivex ilink jvex jlink边结点边结点 data firstedge顶点结点顶点结点 data firstedge顶点结点顶点结点 mark ivex ilink jvex jlink边结点边结点typedef struct enode int mark; int

11、 ivex,jvex; struct enode *ilink,*jlink; infotype info;enode;邻接多重表的数据类型邻接多重表的数据类型typedef struct vnode vertextype data; enode *firstedge;vnode;12563478visited1 2 3 4 5 6 7 8dfs基本思想：基本思想：*访问顶点访问顶点v0。*依次从依次从v0未被访问的邻接点出未被访问的邻接点出发进行深度优先搜索遍历。发进行深度优先搜索遍历。遍历序列：遍历序列：1231256414521426264545262653178177383883733

12、780 0 0 0 0 0 0 01 111111 1注：注：访问访问v0的邻接点与访问的邻接点与访问v0方法一样，用递归方式实现。方法一样，用递归方式实现。12563478dfs(v0)的主要步骤：的主要步骤：(1)访问顶点访问顶点v0(2)确定第一邻接点确定第一邻接点w(3)若若w未访问，未访问， 则从则从w出发进行遍历出发进行遍历dfs(w)(4)确定下一个邻接点确定下一个邻接点w(5)重复重复(3)(4)直到所有邻接点都处理结束直到所有邻接点都处理结束 dfs(v0)的主要步骤：的主要步骤：(1)访问顶点访问顶点v0(2)确定第一邻接点确定第一邻接点w(3)若若w未访问，未访问， 则从

13、则从w出发进行遍历出发进行遍历dfs(w)(4)确定下一个邻接点确定下一个邻接点w(5)重复重复(3)(4)直到所有邻接点都处理结束直到所有邻接点都处理结束 dfs(v0) visite(v0); visitedv0=1; w=first(v0); while( 存在存在w) if (visitedw=0) dfs(w); w=next(v0,w); 125634 data firstarc123456abcdef 562 3 1 4 2 4 3 5 6 2 4 1 1 4dfs(v0) visite(v0); visitedv0=1; w=first(v0); while( 存在存在w) i

14、f (visitedv0=0) dfs(w); w=next(v0,w); 第一邻接点:p= g-adjlistv.firstarc下一个邻接点：p=p-nextarc12563478bfs基本思想：基本思想：*访问顶点访问顶点v0。*依次访问依次访问v0未被访问的邻接点未被访问的邻接点*依次从这些邻接点出发进行广依次从这些邻接点出发进行广度优先搜索遍历。度优先搜索遍历。注：为了从已访问的邻接点出发，设置队列保存结点注：为了从已访问的邻接点出发，设置队列保存结点visited1 2 3 4 5 6 7 8遍历序列：遍历序列：1 2 3 4 5 7 8 612 223 334 445 557 7

15、 7 8 88队列队列0 0 0 0 0 0 0 06 661 1 1 1 11 111 112563478bfs(v0)的主要步骤：的主要步骤：(1)访问顶点访问顶点v0(2)顶点顶点v0入队列入队列(3)取出队头取出队头v 确定第一邻接点确定第一邻接点w 若若w未访问，未访问， 则则访问访问w，w入队列。入队列。 确定下一个邻接点确定下一个邻接点w 重复重复 直到所有邻接点都处理直到所有邻接点都处理(4)重复重复(3)直到队列空。直到队列空。 bfs(v0) init(q); visite(v0); visitedv0=1; enqueue(q,v0); while(!empty(q) )

16、 v=dequeue(q); w=first(v); while( 存在存在w) if (visitedw=0) visite(w); visitedw=1; enqueue(q,w); w=next(v,w); bfs(v0) init(q); visite(v0); visitedv0=1; enqueue(q,v0); while(!empty(q) ) v=dequeue(q); w=first(v); while( 存在存在w) if (visitedw=0) visite(w); visitedw=1; enqueue(q,w); w=next(v,w); 125634 data

17、firstarc123456abcdef 562 3 1 4 2 4 3 5 6 2 4 1 1 4第一邻接点:p=g-adjlistv.firstarc下一个邻接点：p=p-nextarcacdegbfihacdegbfih123456791234567889深度优先搜索过程深度优先搜索过程 深度优先生成树深度优先生成树前进回退acdegbfih123456789123456789广度优先搜索过程广度优先搜索过程 acdegbfhi广度优先生成树广度优先生成树 acdebfgihjonmlk非连通无向图要实现任意图的遍历，则要扫描图中的所有顶点。trqver( ) for( i=1;i=n;

18、i+) visitedi=0; for( i=1;i=n;i+) if (visitedi=0 ) dfs(vi);trqver( ) for( i=1;i=n;i+) visitedi=0; for( i=1;i=n;i+) if (visitedi=0 ) bfs(vi);acdebfgihjonmlk非连通无向图acdebfghijkonml非连通图的连通分量acdebfgihjonmlk非连通无向图acdebfgihjonmlk非连通图的连通分量1624351624351624351251042312104312542深度优先搜索遍历广度优先搜索遍历遍历序列遍历序列:123456遍历序

19、列遍历序列:125634连通图连通图生成树生成树不同的遍历得到不同的生成树不同的遍历得到不同的生成树权值之和权值之和:20权值之和权值之和:143564257156146352应用应用:在若干个城市中建立通讯网。在若干个城市中建立通讯网。mst性质：性质：设设g=g=（v,ev,e）是一个连通网络，）是一个连通网络，u u是顶点集是顶点集v v的一个子集。若（的一个子集。若（u,vu,v）是）是g g中所有的一个端点在中所有的一个端点在u u（即（即u u u u）里，另一个端点不在）里，另一个端点不在u u（即（即v v v-u v-u）里的边中，）里的边中，具有最小权值的一条边，则一定存在

20、具有最小权值的一条边，则一定存在g g的一棵最小生成树的一棵最小生成树包含此边包含此边（u,vu,v）。）。uv-u反正法证明：反正法证明：假设假设g中任何一棵最中任何一棵最小生成树中都不包含边小生成树中都不包含边（u,vu,v）。）。vuvu设设t t是一棵最小生成树，不包（是一棵最小生成树，不包（u,vu,v）, ,一定要包含一条边（一定要包含一条边（u,vu,v）。）。若用（若用（u,vu,v）取代（）取代（u,vu,v）得到一棵）得到一棵新的生成树新的生成树t, t, 由于由于w w （u,vu,v） w w（u,vu,v），则），则tt的权的权tt的权，与假设矛的权，与假设矛盾。盾。

21、535642571561463525461356242361657 756643255u u u u，v v v-uv-u，且，且边边55351246142360657 755632143564257156035241 0 6 1 5 6 0 5 3 1 5 0 7 5 4 5 7 0 2 3 5 0 6 4 2 6 0cost lowcost closest 0 6 1 5 0 0 0 0 0 0最小5540最小222最小最小2050034 0 1 2 3 4 5cost :利用邻接矩阵法存储图利用邻接矩阵法存储图 i=j: costij=0 closest 和和lowcost 分别存储顶点

22、序号和权值，分别存储顶点序号和权值， 当当lowcosti=0: 顶点顶点i已经吸收到已经吸收到u。当当lowcosti 0: 顶点顶点i未被吸收未被吸收v-u。当当0lowcostivi可达的距离0 10 2 记录到达vi的路径1 1 1 1 1 1 1最小最小(si=0) 121修正修正:distmin+costminidisti? 013 3043最小最小(si=0) 143084 010 4最小最小(si=0) 184095 015 5最小最小(si=0) 195最小最小(si=0) 110 4 013 6 113 6path=1346710432101003050206010v0v1

23、 v0v1 10v0v3 v0v3 30v0v2 v0v3 v2 50v0v4 v0v3 v2 v4 50c8c3c5c4c9c6c7c1c2学生课程学习工程图学生课程学习工程图c8c3c5c4c9c6c7c1c2 c0c1c2c3c4c5(a) 有向无环图有向无环图c2c5c1c0c3(b) 输出顶点输出顶点c4c4c1c2c5c3(c) 输出顶点输出顶点c0c0c2c5c1c3(d) 输出顶点输出顶点c3v1v2v3v4v5v6v3123456240012v1v2v3v4v5v6 2 26 126 2 拓扑序列：拓扑序列：v331v4v410v5v5020v1v11v6v60v2v2 51

24、 顶点顶点表示事件，弧表示事件，弧表示活动，其权值为该活动持续的表示活动，其权值为该活动持续的时间。每个事件发生时在它之前的活动已经完成，在它之后的时间。每个事件发生时在它之前的活动已经完成，在它之后的活动可是开始。活动可是开始。问题：问题：（1）工程至少需要多少时间？最短时间）工程至少需要多少时间？最短时间（2）哪些活动是影响工程进度的关键？关键路径）哪些活动是影响工程进度的关键？关键路径a9=21325a1=6a2=47689a10=2a8=7a5=1a6=3a7=9a3=5a4=14a11=4a9=21325a1=6a2=47689a10=2a8=5a5=1a6=3a7=9a3=5a4=14a11=4ve 1 2 3 4 5 6 7 8 90a9=21325a1=6a2=47689a10=2a8=5a5=1a6=3a7=9a3=5a4=14a11=46457816 12 18ve1=0 vej=maxvei+dut(i,j)最短时间最短时间vl 1 2 3 4 5 6 7 8 918a9=21325a1=6a2=47689a10=2a8=5a5=1a6=3a7=9a3=5a4=14a11=414161279660v