第10周图（上）第5讲-本周小结.pdf

《第10周图（上）第5讲-本周小结.pdf》由会员分享，可在线阅读，更多相关《第10周图（上）第5讲-本周小结.pdf（19页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、1图的逻辑结构 图形表示：直接用图表示图形表示：直接用图表示 二元组表示：二元组表示：G=(V，E)，V为顶点集，为顶点集，E为边集为边集 1/19 顶点之间多对多关系顶点之间多对多关系 无向关系无向关系 无向图无向图 有向关系有向关系 有向图有向图 数据结构中讨论的图是没有多重边的！顶点编号：数据结构中讨论的图是没有多重边的！顶点编号：0n-1 01 2 01 2 (0，1)无向边出现两次无向边出现两次 有向边出现两次有向边出现两次 2/19 若无向图若无向图G(V，E)中含中含7个顶点，则保证图个顶点，则保证图G在在 任何情况任何情况下都是连通的，则需要的边数最少是（下都是连通的，则需要的

2、边数最少是（ ）。）。 A. 6B. 15C. 16D. 21 对于具有对于具有n个顶点的无向图，当其中个顶点的无向图，当其中n-1个顶点构成一个完全图时，再个顶点构成一个完全图时，再 加上一条边（连接该完全图和另外一个顶点）必然构成一个连通图加上一条边（连接该完全图和另外一个顶点）必然构成一个连通图 所以本题中，若所以本题中，若 6个顶点构成一个完全图，再加上一条边，这样的图个顶点构成一个完全图，再加上一条边，这样的图 无论如何都是一个连通图无论如何都是一个连通图 最少边数最少边数=(n-1)(n-2)/2+1=16 3/19 下列关于无向连通图特征的叙述中，正确的是（下列关于无向连通图特征

3、的叙述中，正确的是（ ）。）。 I. 所有顶点的度之和为偶数所有顶点的度之和为偶数 II. 边数大于顶点个数减边数大于顶点个数减1 III. 至少有一个顶点的度为至少有一个顶点的度为1 A. 只有只有IB. 只有只有IIC. I和和D. I和和III 所有顶点的度之和所有顶点的度之和 = 2e，为偶数，为偶数 I正确。正确。 无向连通图中，无向连通图中，en- -1 1 II错误。错误。 无向连通图中，可能存在度为无向连通图中，可能存在度为1 的顶点的顶点 III 错误。错误。 A 4/19 2图的存储结构 邻接矩阵邻接矩阵 邻接表邻接表 5/19 以下关于图的存储结构的叙述中正确的是以下关于

4、图的存储结构的叙述中正确的是。 A. 一个图的邻接矩阵表示唯一，邻接表表示唯一一个图的邻接矩阵表示唯一，邻接表表示唯一 B. 一个图的邻接矩阵表示唯一，邻接表表示可能不唯一一个图的邻接矩阵表示唯一，邻接表表示可能不唯一 C. 一个图的邻接矩阵表示可能不唯一，邻接表表示唯一一个图的邻接矩阵表示可能不唯一，邻接表表示唯一 D. 一个图的邻接矩阵表示可能不唯一，邻接表表示可能不唯一一个图的邻接矩阵表示可能不唯一，邻接表表示可能不唯一 一个图的邻接矩阵表示唯一一个图的邻接矩阵表示唯一 邻接表表示可能不唯一（一个顶点相邻的所有顶点构邻接表表示可能不唯一（一个顶点相邻的所有顶点构 成一个单链表，其中相邻顶

5、点的节点顺序可以任意）成一个单链表，其中相邻顶点的节点顺序可以任意） B 6/19 以下关于图的存储结构的叙述中正确的是（以下关于图的存储结构的叙述中正确的是（ ）。）。 A. 邻接矩阵占用的存储空间大小只与图中顶点数有关，而与边数无关邻接矩阵占用的存储空间大小只与图中顶点数有关，而与边数无关 B. 邻接矩阵占用的存储空间大小只与图中边数有关，而与顶点数无关邻接矩阵占用的存储空间大小只与图中边数有关，而与顶点数无关 C. 邻接表占用的存储空间大小只与图中顶点数有关，而与边数无关邻接表占用的存储空间大小只与图中顶点数有关，而与边数无关 D. 邻接表占用的存储空间大小只与图中边数有关，而与顶点数无

6、关邻接表占用的存储空间大小只与图中边数有关，而与顶点数无关 无向图：用邻接矩阵存储时，：用邻接矩阵存储时，占用的存储空间大小为占用的存储空间大小为O(n2)；用邻；用邻 接表存储时，占用的存储空间大小为接表存储时，占用的存储空间大小为O(n+2e)。 有向图：用邻接矩阵存储时，：用邻接矩阵存储时，占用的存储空间大小为占用的存储空间大小为O(n2)；用邻；用邻 接表存储时，占用的存储空间大小为接表存储时，占用的存储空间大小为O(n+e) A 7/19 3图的遍历 某种次序某种次序 访问所有顶点访问所有顶点 不重复访问不重复访问 8/19 深度优先遍历深度优先遍历 广度优先遍历广度优先遍历 具有递

7、归性具有递归性 图算法图算法 图查找图查找 图遍历图遍历 9/19 假设图采用邻接矩阵表示。设计一个从顶点假设图采用邻接矩阵表示。设计一个从顶点v出发的深出发的深 度优先遍历算法。度优先遍历算法。 0 10 11 1 0 110 0 10 11 1 1 10 1 10 1 10 w 找顶点找顶点v的相邻顶点的相邻顶点w 10/19 int visitedMAXV;/全局变量，所有元素置初值全局变量，所有元素置初值0 void MDFS(MGraph g，int v) int w; printf(%d ，v);/访问顶点访问顶点v visitedv=1;/置访问标记置访问标记 for (w=0;

8、we=G-n-1 树图？但树图？但G-e和和G-n未知！未知！ 对于对于无向连通图无向连通图G，采用，采用DFS，访问的顶点数，访问的顶点数vn为为n，试探的，试探的 边数边数en恰好为恰好为2e。 一棵树 en/2=vn-1 或者或者en=2(vn-1) 12/19 int visitedMaxSize; void DFS2(ALGraph *G，int v，int visitedv=1; vn+;/遍历过的顶点数增遍历过的顶点数增1 p=G-adjlistv.firstarc; while (p!=NULL) en+;/试探过的边数增试探过的边数增1 if (visitedp-adjvex

9、=0) DFS2(G，p-adjvex，vn，en); p=p-nextarc; 13/19 bool GIsTree(ALGraph *G) /判断无向图判断无向图G是否是一棵树是否是一棵树 int vn=0，en=0，i; for (i=0; iadjlistv.firstarc;/p指向顶点指向顶点v的第一个邻接点的第一个邻接点 while (p!=NULL) w=p-adjvex; if (visitedw=0)/若顶点若顶点w未访问未访问，递归访问它递归访问它 Cycle(G，w，has); else/又找到了已访问过的顶点说明有回路又找到了已访问过的顶点说明有回路 has=true

10、; p=p-nextarc;/找下一个邻接点找下一个邻接点 16/19 假设图假设图G采用邻接表存储。设计一个算法，求采用邻接表存储。设计一个算法，求不带权无不带权无 向连通图向连通图G中距离顶点中距离顶点v最远的一个顶点最远的一个顶点。 v k 最外圈中的任何一个顶点是最远的顶点最外圈中的任何一个顶点是最远的顶点 BFS遍历完毕，队列中最后一个出队且没有遍历完毕，队列中最后一个出队且没有 相邻访问顶点的顶点相邻访问顶点的顶点k属于该圈中的顶点属于该圈中的顶点 17/19 int Maxdist(ALGraph *G，int v) ArcNode *p; int QuMAXV，front=0，

11、rear=0;/队列及队头、尾指针队列及队头、尾指针 int visitedMAXV，i，j，k; for (i=0;in;i+)/初始化访问标志数组初始化访问标志数组 visitedi=0; rear+;Qurear=v;/顶点顶点v进队进队 visitedv=1;/标记标记v已访问已访问 18/19 while (rear!=front) front=(front+1)%MAXV; k=Qufront;/顶点出队顶点出队 p=G-adjlistk.firstarc;/找第一个邻接点找第一个邻接点 while (p!=NULL)/所有未访问过的邻接点进队所有未访问过的邻接点进队 j=p-adjvex; if (visitedj=0)/若若j未访问过未访问过 visitedj=1;/将顶点将顶点j进队进队 rear=(rear+1)%MAXV;Qurear=j; p=p-nextarc;/找下一个邻接点找下一个邻接点 return k; 19/19