大数据分析第8章图-6（小结）

第8章-小结1图的逻辑结构逻辑表示方式图形表示：直接用图表示二元组表示：G=(V，E)，V为顶点集，E为边集1/35逻辑特性顶点之间多对多关系无向关系

无向图有向关系

有向图数据结构中讨论的图是没有多重边的！顶点编号：0～n-1012012××(0，1)无向边出现两次<0，1>有向边出现两次2/35若无向图G(V，E)中含7个顶点，则保证图G在任何情况下都是连通的，则需要的边数最少是（）。A.6 B.15 C.16 D.21对于具有n个顶点的无向图，当其中n-1个顶点构成一个完全图时，再加上一条边（连接该完全图和另外一个顶点）必然构成一个连通图所以本题中，若6个顶点构成一个完全图，再加上一条边，这样的图无论如何都是一个连通图最少边数=(n-1)(n-2)/2+1=163/35解示例下列关于无向连通图特征的叙述中，正确的是（）。I.所有顶点的度之和为偶数II.边数大于顶点个数减1III.至少有一个顶点的度为1A.只有I B.只有II C.I和Ⅱ D.I和III所有顶点的度之和=2e，为偶数

I正确。无向连通图中，e≥n-1

II错误。无向连通图中，可能存在度为1的顶点

III错误。A4/35解示例2图的存储结构图的两种主要存储方法邻接矩阵邻接表5/35图两种存储方法的特点以下关于图的存储结构的叙述中正确的是

。A.一个图的邻接矩阵表示唯一，邻接表表示唯一B.一个图的邻接矩阵表示唯一，邻接表表示可能不唯一C.一个图的邻接矩阵表示可能不唯一，邻接表表示唯一D.一个图的邻接矩阵表示可能不唯一，邻接表表示可能不唯一一个图的邻接矩阵表示唯一邻接表表示可能不唯一（一个顶点相邻的所有顶点构成一个单链表，其中相邻顶点的节点顺序可以任意）答案为B6/35解示例以下关于图的存储结构的叙述中正确的是（）。A.邻接矩阵占用的存储空间大小只与图中顶点数有关，而与边数无关B.邻接矩阵占用的存储空间大小只与图中边数有关，而与顶点数无关C.邻接表占用的存储空间大小只与图中顶点数有关，而与边数无关D.邻接表占用的存储空间大小只与图中边数有关，而与顶点数无关无向图：用邻接矩阵存储时，占用的存储空间大小为O(n2)；用邻接表存储时，占用的存储空间大小为O(n+2e)。有向图：用邻接矩阵存储时，占用的存储空间大小为O(n2)；用邻接表存储时，占用的存储空间大小为O(n+e)答案为A7/35解示例3图的遍历遍历过程某种次序访问所有顶点不重复访问8/35深度优先遍历广度优先遍历

常用图遍历方法具有递归性图算法图查找图遍历9/35假设图采用邻接矩阵表示。设计一个从顶点v出发的深度优先遍历算法。0101

1101

100101

11110110110w找顶点v的相邻顶点w10/35示例intvisited[MAXV];

//全局变量，所有元素置初值0voidMDFS(MGraphg，intv){intw;printf("%d"，v); //访问顶点vvisited[v]=1; //置访问标记for(w=0;w<g.n;w++) //找顶点v的所有相邻点if(g.edges[v][w]!=0&&g.edges[v][w]!=INF&&visited[w]==0)

MDFS(g，w); //找顶点v的未访问过的相邻点w}算法如下：11/35时间复杂度为O(n2)

DFS遍历算法应用示例图采用邻接表作为存储结构。对于一个无向连通图G，假设不知道n和e，设计一个算法判断是否为一棵树。若是树，返回true；否则返回false。若G->e=G->n-1

树图？但G->e和G->n未知！对于无向连通图G，采用DFS，访问的顶点数vn为n，试探的边数en恰好为2e。一棵树en/2=vn-1或者en=2(vn-1)12/35解示例intvisited[MaxSize];voidDFS2(ALGraph*G，intv，int&vn，int&en){ArcNode*p;visited[v]=1;vn++; //遍历过的顶点数增1p=G->adjlist[v].firstarc;while(p!=NULL){en++; //试探过的边数增1if(visited[p->adjvex]==0)

DFS2(G，p->adjvex，vn，en);p=p->nextarc;}}13/35boolGIsTree(ALGraph*G)//判断无向图G是否是一棵树{intvn=0，en=0，i;for(i=0;i<MaxSize;i++)

visited[i]=0;

DFS2(G，0，vn，en);if(en==2*(vn-1)) returntrue;else returnfalse;}14/35假设一个有向图采用邻接表作为存储结构。试设计一个算法，判断其中是否存在回路。vwi当visited[w]=1，visited[i]=1时表示顶点w到i存在一条路径若顶点i有一个邻接点w，表示i到w存在一条路径，从而构成回路回路15/35示例解voidCycle(ALGraph*G，intv，bool&has){//调用时has置初值falseArcNode*p; intw;visited[v]=1; //置已访问标记p=G->adjlist[v].firstarc; //p指向顶点v的第一个邻接点while(p!=NULL){ w=p->adjvex; if(visited[w]==0) //若顶点w未访问，递归访问它

Cycle(G，w，has); else //又找到了已访问过的顶点说明有回路 has=true; p=p->nextarc; //找下一个邻接点}}16/35boolHasCycle(ALGraph*G)//判断有向图G中是否有回路{boolhas=false;for(inti=0;i<G->n;i++){Cycle(G，i，has);if(has)returntrue;}returnfalse;}思考：如果是无向图呢？17/35假设图G采用邻接表存储。设计一个算法，求不带权无向连通图G中距离顶点v最远的一个顶点。

BFS遍历算法应用示例vk最外圈中的任何一个顶点是最远的顶点BFS遍历完毕，队列中最后一个出队且没有相邻访问顶点的顶点k属于该圈中的顶点18/35解示例intMaxdist(ALGraph*G，intv){ArcNode*p;intQu[MAXV]，front=0，rear=0; //队列及队头、尾指针intvisited[MAXV]，i，j，k;for(i=0;i<G->n;i++) //初始化访问标志数组 visited[i]=0;rear++;Qu[rear]=v; //顶点v进队visited[v]=1; //标记v已访问19/35while(rear!=front){front=(front+1)%MAXV;k=Qu[front]; //顶点出队p=G->adjlist[k].firstarc; //找第一个邻接点while(p!=NULL) //所有未访问过的邻接点进队{j=p->adjvex; if(visited[j]==0) //若j未访问过 {visited[j]=1; //将顶点j进队 rear=(rear+1)%MAXV;Qu[rear]=j; } p=p->nextarc; //找下一个邻接点}}returnk;}20/354生成树和最小生成树

生成树和最小生成树定义带权连通图生成树极小连通子图最小生成树所有边权值和最小21/35构建生成树的方法深度优先遍历

深度优先生成树广度优先遍历

广度优先生成树广度优先生成树高度

≤

深度优先生成树高度22/35若一个具有n个顶点和e条边的无向图是一个森林（n>e），则该森林必有（）棵树。A.e B.n C.n-e D.1设该森林有m棵树，结点个数分别为n1、n2、…、nm总结点数n=n1+n2+…

+nm第i棵树的边数=ni-1（可以看成自己的生成树）总边数=(n1-1)+(n2-1)+…+(nm-1)=n-m=e，所以m=n-e答案为C23/35解示例构建最小生成树的算法起点v

所有顶点分为U（v∈U）和V-U每次选择这两个集合之间的最小边O(n2)Kruskal算法Prim算法将边按权值递增排列每次选择权值小并且不构成回路的边O(elog2e)24/35一个带权连通图中所有权值最小的边一定会出现在所有的最小生成树中？不一定！120311121201113Kruskal25/35示例对某个带权连通图构造最小生成树，以下说法中正确的是（）。Ⅰ.该图的所有最小生成树的总代价一定是唯一的Ⅱ.该图的最小生成树是唯一的Ⅲ.用Prim算法从不同顶点开始构造的所有最小生成树一定相同Ⅳ.使用Prim和Kruskal算法得到的最小生成树总不相同A.仅Ⅰ B.仅Ⅱ C.仅Ⅰ、Ⅲ

仅Ⅱ、Ⅳ

×A××26/35示例5最短路径

单源最短路径―Dijkstra算法源点v加入S，U=V-S初始化：

若v→i有边：dist[i]=(v，i)权值path[i]=v否则：dist[i]=∞path[i]=-1从U中选择dist最小的顶点u考察所有从u有出边的顶点j，调整：若dist[u]+(u，j)权值<dist[j]：dist[j]=dist[u]+(u，j)权值path[j]=u否则：

不变直到S=V时间复杂度：O(n2)27/35Dijkstra算法是（）方法求出图中从源点到其余顶点最短路径的。A.按长度递减的顺序求出图的某顶点到其余顶点的最短路径B.按长度递增的顺序求出图的某顶点到其余顶点的最短路径C.通过深度优先遍历求出图中某顶点到其余顶点的最短路径D.通过广度优先遍历求出图中某顶点到其余顶点的最短路径

S加入S集合的顶点：最短路径不再改变越后加入的顶点，dist越长28/35示例以下叙述正确的是（）。A.最短路径一定是简单路径B.Dijkstra算法不适合有回路的带权图求最短路径C.Dijkstra算法不适合求任意两个顶点的最短路径D.Floyd算法求两个顶点的最短路径时，pathk-1一定是pathk的子集

29/35示例多源最短路径―Flody算法ij0～n-1迭代

时间复杂度：O(n3)30/35设下图中的顶点表示村庄，有向边代表交通路线，若要建立一家医院，试问建在哪一个村庄能使各村庄总体交通代价最小。034121212131