第六章图
掌握图的基本概念及相关术语和性质
熟练掌握图的邻接矩阵和邻接表两种存储表示方法
熟练掌握图的两种遍历方法DFS和BFS
熟练掌握最短路径算法（迪杰斯特拉算法）
掌握最小生成树算法及拓扑排序算法思想
6.1图的定义和基本术语
图的定义：图G由两个集合V和E组成，记为G=(V,E)，其中V是顶点的有穷非空集合，E是边的集合。
注意：在图中，顶点个数不能为0，但边数可以为0.
无向边（边）：若顶点到之间的边没有方向，则称这条边为无向边，表示（）
有向边（弧）：若从顶点到之间的边有方向，则称这条边为有向边，表示为
无向图：每条边都是无方向的
有向图：每条边都是有方向的
完全图：任意两个点都有一条边相连
稀疏图：有很少边或弧的图
稠密图：有较多边或弧的图
网：边/弧带权的图
邻接：有边/弧相连的两个顶点之间的关系
关联（依附）：
边/弧与顶点之间的关系
存在()/，则称该边/弧关联于
顶点的度：
与该顶点相关联的边的数目，记为TD(v)
在有向图中，顶点的度等于该顶点的入度和出度之和
顶点v的入度是以v为终点的有向边的条数，记作ID(v)
顶点v的出度是以v为始点的有向边的条数，记作OD(v)
路径：
路径长度：路径上边或弧的数目
回路：第一个顶点和最后一个顶点相同的路径
简单路径：序列中顶点不重复出现的路径
简单回路（简单环）：除路径起点和终点相同外，其余顶点均不相同的路径
子图：
连通图：
在无向图中，如果从一个顶点到另一个顶点有路径，则称顶点和是连通的。
如果图中任意两个顶点都是连通的，则称该图是连通图
连通分量：
无向图中的极大连通子图称为连通分量
极大连通子图
子图是图G的连通子图，将G的任何不再该子图中的顶点加入，子图不再连通
强连通图：
在有向图中，对图中任意一对顶点和，若从顶点到顶点和从顶点到顶点均有路径，则称该有向图是强连通图
强连通分量：
有向图中的极大强连通子图
极大强连通子图
子图G是强连通子图，将G的任何不再该子图中的顶点加入，子图不再是强连通的
极小连通子图：子图是G的连通子图，在该子图中删除任何一条边，子图不再连通
生成树：包含无向图G所有顶点的极小连通子图
生成森林：在非连通图中，由每个连通分量都可以得到一棵生成树，这些连通分量的生成树就组成了一个非连通图的生成森林
6.2图的存储结构
顺序存储结构
邻接矩阵表示法
建立一个顶点表（记录各个顶点信息）和一个邻接矩阵（表示各个顶点之间的关系）
设图G=(V,E)有n个顶点，则图的邻接矩阵是一个二维数组G.Edge[n][n]，定义为：
无向图的邻接矩阵表示法
分析1：无向图的邻接矩阵是对称的；
分析2：顶点i的度=第i行（列）中1的个数
特别：完全图的邻接矩阵中，对角元素为0，其余为1
有向图的邻接矩阵表示法
注：在有向图的邻接矩阵中，第i行含义：以结点为尾的弧（即出度边）；第i列含义：以结点为头的弧（即入度边）。
分析1：有向图的邻接矩阵可能是不对称的。
分析2：顶点的出度=第i行元素之和
顶点的入度=第i列元素之和
顶点的度=第i行元素之和+第i列元素之和
网的邻接矩阵表示法
邻接矩阵表示法的特点：
优点：
容易实现以下操作
求某顶点的度
判断顶点之间是否有边
找顶点的邻接点等等
缺点：
对稀疏图而言很浪费空间
邻接矩阵的存储表示
//用两个数组分别存储顶点表和邻接矩阵#defineMaxInt//表示极大值，即∞#defineMVNum//最大顶点数typedefcharVertexType;//假设顶点的数据类型为字符型typedefintArcType;//假设边的权值类型为整型typedefstruct{VertexTypevexs[MVNum];//顶点表ArcTypearcs[MVNum][MVNum];//邻接矩阵intvexnum,arcnum;//图的顶点数和边数}AMGraph;基于邻接矩阵表示法创建无向网算法思想输入总顶点数和总边数。依次输入顶点的信息存入顶点表中。初始化邻接矩阵，使每个权值初始化为极大值。构造邻接矩阵。StatusCreateUDN(AMGraphG){//采用邻接矩阵表示法，创建无向网GcinG.vexnumG.arcnum;//输入总顶点数，总边数for(i=0;iG.vexnum;++i)cinG.vexs;//依次输入顶点的信息for(i=0;iG.vexnum;++i)//初始化邻接矩阵，边的权值均为极大值for(j=0;jG.vexnum;++j)G.arcs[j]=MaxInt;for(k=0;kG.arcnum;++k){//构造邻接矩阵cinv1v2w;//输入一条边依附的顶点及权值i=LocateVex(G,v1);j=LocateVex(G,v2);//确定v1和v2在G中的位置G.arcs[j]=w;//边v1,v2的权值置为wG.arcs[j]=G.arcs[j];//置v1,v2的对称边v2,v1的权值为w}//forreturnOK;}//CreateUDNintLocateVex(AMGraphG,VertexTypeu){/*初始条件:图G存在,u和G中顶点有相同特征*//*操作结果:若G中存在顶点u,则返回该顶点在图中位置;否则返回-1*/inti;for(i=0;iG.vexnum;++i)if(u==G.vexs)returni;return-1;}
链式存储结构
邻接表表示法
为图中的每个顶点建立一个单链表，第i个单链表中的结点表示依附于顶点的边。（有向图中指以为尾的弧）
链表中的每个结点都设为三个域
无向图的邻接表表示
注：邻接表不唯一，因各个边结点的链入顺序是任意的
空间效率为O（n+2e）
若是稀疏图（en*n）,比邻接矩阵表示法省空间
有向图的邻接表表示
出度：OD(Vi)＝单链出边表中链接的结点数
入度：ID(Vi)＝邻接点域为Vi的弧个数
邻接表的存储表示
typedefstructArcNode{//边结构intadjvex;//该边所指向的顶点位置structArcNode*nextarc;//指向下一条边的指针OtherInfoinfo;//和边相关的信息}ArcNode；#defineMVNumtypedefstructVNode{//顶点结构VertexTypedata;//顶点信息ArcNode*firstarc;//指向依附该顶点的第一条弧的指针}VNode,AdjList[MVNum];typedefstruct{//图结构AdjListvertics;//邻接表intvexnum,arcnum;//顶点数和弧数intkind;//图的种类}ALGraph;StatusCreateUDG(ALGraphG){//采用邻接表表示法，创建无向图G cinG.vexnumG.arcnum;//输入总顶点数，总边数for(i=0;iG.vexnum;++i){//输入各点，构造头结点表cinG.vertices.data;//输入顶点值G.vertices.firstarc=NULL;//初始化表头结点的指针域为NULL}//forfor(k=0;kG.arcnum;++k){//输入各边，构造邻接表cinv1v2;//输入一条边依附的两个顶点i=LocateVex(G,v1);j=LocateVex(G,v2);p1=newArcNode;//生成一个新的边结点*p1
p1-adjvex=j;//邻接点序号为j p1-nextarc=G.vertices.firstarc;G.vertices.firstarc=p1;//将新结点*p1插入顶点vi的边表头部p2=newArcNode;//生成另一个对称的新的边结点*p2 p2-adjvex=i;//邻接点序号为i p2-nextarc=G.vertices[j].firstarc;G.vertices[j].firstarc=p2;//将新结点*p2插入顶点vj的边表头部}//forreturnOK;}//CreateUDG
邻接表表示法的特点
优点
便于增加和删除顶点
便于统计边的数目
空间效率高，容易寻找顶点的邻接点；
对于n个顶点e条表的无向图，邻接表中除了n个头结点外，只有2e个表结点，空间效率为O(n+2e)
缺点
判断两顶点间是否有边或弧，需搜索两结点对应的单链表，没有邻接矩阵方便。
不便于计算各个顶点的度。
讨论：邻接表与邻接矩阵有什么异同之处？
联系：邻接表中每个链表对应于邻接矩阵中的一行，链表中结点个数等于一行中非零元素的个数
区别：对于任一确定的无向图，邻接矩阵是唯一的（行列号与顶点编号一致），但邻接表不唯一（链接次序与顶点编号无关）。邻接矩阵的空间复杂度为O(n*n)，而邻接表的空间复杂度为O(n+e)
用途：邻接矩阵多用于稠密图，而邻接表多用于稀疏图。
十字链表
邻接多重表
6.3图的遍历
遍历定义：从图中某顶点出发遍历图中所有顶点，且每个顶点仅被访问一次，此过程称为图的遍历
遍历实质：找每个顶点的邻接点的过程
图的特点：图中可能存在回路，且图的任一顶点都可能与其他顶点相通，在访问完某个顶点之后可能会沿着某些边又回到了曾经访问过的顶点。
怎样避免重复访问？
设置辅助数组visited[n]，用来标记每个被访问过的顶点
初始状态为0
i被访问，改visited为1，防止被对此访问
图常用的遍历
深度优先搜索/遍历
基本思想：
从图的某一顶点v出发，访问此顶点；
然后依次从v的未被访问的邻接点出发，深度优先遍历图，直至图中所有和v相通的顶点都被访问到
若图中尚有顶点未被访问，则另选图中一个未被访问的顶点作起点，重复上述过程，直至图中所有顶点都被访问为止。
基于邻接矩阵进行DFS
基于邻接矩阵表示图的深度优先搜索voidDFS_AM(AMGraphG,intv){//图G为邻接矩阵类型coutv;visited[v]=true;//访问第v个顶点for(w=0;wG.vexnum;w++)//依次检查邻接矩阵v所在的行if((G.arcs[v][w]!=0)(!visited[w]))DFS_AM(G,w);//w是v的邻接点，如果w未访问，则递归调用DFS}
基于邻接表进行DFS
voidDFS_AL(ALGraphG,intv){//图G为邻接表类型coutv;visited[v]=true;//访问第v个顶点p=G.vertices[v].firstarc;//p指向v的边链表的第一个边结点while(p!=NULL)//边结点非空{w=p-adjvex;//表示w是v的邻接点if(!visited[w])DFS_AL(G,w);//如果w未访问，则递归调用DFSp=p-nextarc;//p指向下一个边结点}}
深度优先遍历算法
boolvisited[MVNum];//访问标志数组VoidDFSTraverse(GraphG){//对图G做深度优先遍历for(v=0;vG.vexnum;++v)//访问标志数组初始化visited[v]=false;for(v=0;vG.vexnum;++v)if(!visited[v])DFS_AM(G,v);//对尚未访问的顶点调用DFS}DFS算法效率分析用邻接矩阵来表示图，遍历图的每一个顶点都要从头扫描该顶点所在行，时间复杂度为O(n*n)用邻接表来表示图，找邻接点所需时间为O（e），加上访问n个头结点的时间，时间复杂度为O(n+e)。结论：稠密图适用于在邻接矩阵上进行深度遍历稀疏图适用于在邻接表上进行深度遍历
广度优先搜索/遍历
基本思想
访问顶点v
依次访问v的各个未被访问的邻接点v1,v2,...,vk
分别从v1,v2,...,vk出发，依次访问它们未被访问的邻接点，并使“先被访问顶点的邻接点”先于“后被访问顶点的邻接点”被访问。直至图中所有与顶点v有路径相通的顶点都被访问到
广度优先搜索是一种分层的搜索过程，每向前走一步可能访问一批顶点，不像深度优先搜索那样有回退的情况。因此，广度优先搜索不是一个递归的过程，其算法也不是递归的。
基本思想
从图中某个顶点v出发，访问v，并置visited[v]的值true，然后将v进队
只要队列不空，则重复下述过程
队头顶点u出队
依次检查u所有邻接点w，如果visited[w]的值为false，则访问w，并置visited[w]的值为true，然后将w进队
voidBFS(GraphG,intv){//按广度优先非递归遍历连通图Gcoutv;visited[v]=true;//访问第v个顶点InitQueue(Q);//辅助队列Q初始化，置空EnQueue(Q,v);//v进队while(!QueueEmpty(Q)){//队列非空DeQueue(Q,u);//队头元素出队并置为ufor(w=FirstAdjVex(G,u);w=0;w=NextAdjVex(G,u,w))if(!visited[w]){//w为u的尚未访问的邻接顶点coutw;visited[w]=true;EnQueue(Q,w);//w进队}//if}//while}//BFS
BFS算法效率分析
如果使用邻接矩阵，则BFS对于每一个被访问到的顶点，都要循环检测矩阵中的整整一行（n个元素），总的时间代价为O(n*n)。
如果用邻接表来表示图，虽然有2e个表结点，但只需扫描e个结点即可完成遍历，加上访问n个头结点的时间，时间复杂度为O(n+e)。
6.4图的应用
6.4.1最小生成树
生成树的特征：n个顶点连通图的生成树有n个顶点，n-1条边
求生成树的方法：DFS和BFS
连通图：仅需从图中任一顶点出发，进行DFS或BFS，便可访问到图中所有顶点。
非连通图：需从多个顶点出发进行搜索，而每一次从一个新的起始点出发进行搜索过程中得到的顶点访问序列恰为其对应连通分量中的顶点集。
一个连通图的生成树可能不唯一，由于不同的遍历次序，从不同顶点出发进行遍历都会得到不同的生成树。
生成树的代价：设G=(V,E)是一个无向连通网，生成树上各边的权值之和称为该生成树的代价。
最小生成树：在图G所有生成树中，代价最小的生成树称为最小生成树。
使用不同的遍历方法，可以得到不同的生成树。从不同的顶点出发，也可能得到不同的生成树。
求最小生成树算法
Kruskal（克鲁斯卡尔）算法
归并边，适用于稀疏网
时间复杂度O(eloge)
存储表示：邻接表
基本思想：
设有一个有n个顶点的连通网N=(V,E)
Prim（普里姆）算法
归并顶点，与边数无关，适用于稠密网
时间复杂度O(n*n)
存储表示：邻接矩阵
基本思想：
假设N=(V,E)是连通网，U为最小生成树的顶点集，TE为最小生成树的边集。
prim算法特点：将顶点归并，与边数无关，适用于稠密网。故采用邻接矩阵作为图册存储表示
设计思路
增设一辅助数组closeEdge[n]，每个数组分量都有两个域：
struct{VertexTypeadjvex;//最小边在U中的顶点序号ArcTypelowcost;//最小边上的权值}closeEdge[MVNum];voidMiniSpanTree_PRIM(AMGraphG,VertexTypeu){//用普里姆算法从顶点u出发构造网G的最小生成树k=LocateVex(G,u);for(j=0;jG.vexnum;++j)//辅助数组初始化if(j!=k)closeEdge[j]={u,G.arcs[k][j]};closeEdge[k].lowcost=0;//初始，U＝{u}for(i=1;iG.vexnum;++i)//选择其余G.vexnum-1个顶点{k=Min(closeEdge);//求出T的下一个结点：第k顶点//输出生成树上一条边coutcloseEdge[k].adjvex“”G.vexs[k]endl;closeEdge[k].lowcost=0;//第k顶点并入U集for(j=0;jG.vexnum;++j)//修改其它顶点的最小边if(G.arcs[k][j]closeEdge[j].lowcost)//新顶点并入U后重新选择最小边closeEdge[j]={G.vexs[k],G.arcs[k][j]};}//for}
6.4.2最短路径
典型用途：
交通问题。如：城市A到城市B有多条线路，但每条线路的交通费（或所需时间）不同，那么，如何选择一条线路使总费用（时间）最小？
问题抽象：在带权有向图中A点到达B点的多条路径中，寻找一条权值之和最小的路径，即最短路径。
两种常见的最短路径问题
单源最短路径
一顶点到其余各顶点
Dijkstra（迪杰斯特拉）算法
单源最短路径问题：
设有一有向图G=(V,E)，已知各边的权值，以某指定点v0为源点，求从v0到图的其余各点的最短路径。（限定各边上的权值大于或等于0）
Dijkstra算法思想：
先找出从源点v0到各终点vk的直达路径（v0,vk），即通过一条弧到达的路径。
从这些路径中找出一条长度最短的路径（v0,u），然后对其余各条路径进行适当调整：
?若在图中存在弧（u,vk），且（v0,u）+（u,vk）（v0,vk）,则以路径（v0,u,vk）代替（v0,vk）。
在调整后各条路径中，再找长度最短的路径，依次类推。
voidShortestPath_DIJ(AMGraphG,intv0){//用Dijkstra算法求有向网G的v0顶点到其余顶点的最短路径n=G.vexnum;//n为G中顶点的个数for(v=0;vn;++v){//n个顶点依次初始化S[v]=false;//S初始为空集D[v]=G.arcs[v0][v];//将v0到各个终点的最短路径长度初始化if(D[v]MaxInt)Path[v]=v0;//v0和v之间有弧，将v的前驱置为v0elsePath[v]=-1;//如果v0和v之间无弧，则将v的前驱置为-1}//forS[v0]=true;//将v0加入SD[v0]=0;//源点到源点的距离为0/*―开始主循环，每次求得v0到某个顶点v的最短路径，将v加到S集―*/for(i=1;in;++i){//对其余n?1个顶点，依次进行计算min=MaxInt;for(w=0;wn;++w)if(!S[w]D[w]min){v=w;min=D[w];}//选择一条当前的最短路径，终点为vS[v]=true;//将v加入Sfor(w=0;wn;++w)//更新从v0出发到集合V?S上所有顶点的最短路径长度if(!S[w](D[v]+G.arcs[v][w]D[w])){D[w]=D[v]+G.arcs[v][w];//更新D[w]Path[w]=v;//更改w的前驱为v}//if}//for}
所有顶点间的最短路径
任意两顶点直接
Floyd（弗洛伊德）算法
求每一对顶点之间的最短路径
方法一：每次以一个顶点为源点，重复执行Dijkstra算法n次——T(n)=O(n*n*n)
方法二：弗洛伊德(Floyd)算法
算法思想：逐个顶点试探法
初始时设置一个n阶方阵，令其对角元素为0，若存在弧，则对应元素为权值；否则为
逐步试着在原直接路径中增加中间顶点，若加入中间顶点后路径变短，则修改之；否则维持原值
所有顶点试探完毕，算法结束
引入辅助数据结构
二维数组Path[j]:最短路径上顶点Vj的前一顶点序号
二维数组D[j]:记录顶点Vi和Vj之间的最短路径长度
ShortestPath_Floyd(AdjMatrixg,WeightTypedist[MAX][MAX],VertexSetpath[MAX][MAX]){for(i=0;ig.vexnum;i++){for(j=0;jg.vexnum;j++){InitList(path[j]);/*初始化dist[j]和path[j]*/dist[j]=g.arcs[j];if(dist[j]MAX){AddTail(path[j],g.vexs);AddTail(path[j],g.vexs[j]);}for(k=0;kg.vexnum;k++)for(i=0;ig.vexnum;i++)for(j=0;jg.vexnum;j++)if(dist[k]+dist[k][j]dist[j]){dist[j]=dist[k]+dist[k][j];path[j]=JoinList(path[k],path[k][j]);}}}}
6.4.3拓扑排序
AOV网（ActivityOnVertexNetwork）
用顶点表示活动，用弧表示活动间的优先关系的有向图称为顶点表示活动的网，简称AOV网
在一个AOV网G中，如果存在一条从顶点i到顶点j的有向路径，则顶点i是顶点j的前驱，相应地，顶点j是顶点i的后继。如果i,j是G的一条弧，则顶点i是顶点j的直接前驱，相应地，顶点j是顶点i的直接后继。
拓扑序列
拓扑序列是图中所有顶点组成的一种线性序列，使得对于图中任意两个顶点j，如果i是j的前驱，则i在该线性序列中处于j的前面。
什么叫拓扑排序？
对一个有向图构造拓扑序列的过程。
拓扑排序的应用：
大学的课程之间存在先修关系，利用拓扑排序可以正确安排课程
一本教材的内容之间可能存在先后关系，利用拓扑排序可使教材逻辑性强，易于理解
房屋装修工程
拓扑排序算法
核心思想
重复选择没有直接前驱的顶点
算法步骤
在有向图中选一个没有直接前驱的顶点，并输出之
从图中删去该顶点和所有以它为尾的弧
重复上述过程，直到全部顶点均已输出，或剩余顶点都有前驱
剩余顶点都有前驱表明网络中存在环路，因而整个工程不可行
拓扑排序实现：
设计数据结构
1.图的存储结构：采用邻接表存储，在顶点表中增加一个入度域。
2.栈S：存储所有无前驱的顶点
算法实现：
以邻接表作存储结构
栈S初始化；累加器count初始化；
扫描顶点表，将所有入度为0的顶点进栈
栈非空时循环：
输出栈顶元素Vj并退栈，累加器加1；
在邻接表中查找Vj的直接后继Vk，把Vk的入度减1；若Vk的入度为0则进栈
重复上述操作直至栈空为止。若栈空时输出的顶点个数不是n，则有向图有环；否则，拓扑排序完毕。
typedefstructEdgeNode/*边表结点*/{intadjvex;//邻接点域，存储该顶点对应的下标intweight;structEdgeNode*next;}EdgeNode;typedefstructVertexNode/*顶点表结点*/{intin;//顶点的入度intdata;//数据域，存储顶点信息EdgeNode*firstedge;//边表头指针}VertexNode,AdjList[MAXVEX];typedefstruct{AdjListadjList;intnumVertexes,numEdges;}graphAdjList,*GraphAdjList;拓扑排序算法//拓扑排序，若GL无回路，则输出拓扑排序序列并返回OK，若有回路返回ERRORStatusTopologicalSort(GraphAdjListGL){EdgeNode*e;inti,k,gettop;inttop=0;//用于栈指针下标intcount=0;//用于统计输出顶点的个数int*stack;stack=(int*)malloc(GL-numVertexes*sizeof(int));for(i=0;iGL-numVertexes;i++)if(GL-adjList.in==0)stack[++top]=i;//将入度为0的顶点入栈while(top!=0){gettop=stack[top--];printf(“%d-”,GL-adjList[gettop].data);//打印此顶点count++;for(e=GL-adjList[gettop].firstedge;e;e=e-next){k=e-adjvex;if(!(--GL-adjList[k].in))//将k号顶点邻接点的入度减1stack[++top]=k;//若为0，则入栈}}if(countGL-numVertexes)returnERROR;elsereturnOK;}
6.4.4关键路径
AOE网（ActivityOnEdges）也称边表示活动。AOE网是一个带权的有向无环图图，其中顶点表示事件，弧表示活动，表示活动持续时间。
AOE网可用来估算工程的完成时间。
AOE网的性质：只有在某顶点所代表的事件发生后，从该顶点出发的各活动才能开始；只有在进入某顶点的各活动都结束，该顶点所代表的的事件才能发生。
路径长度：路径上各活动持续时间之和。
关键路径：路径长度最长的路径叫关键路径。
由于AOE网中的某些活动能够同时进行，故完成整个工程所必须花费的时间应该为始点到终点的最大路径长度。
关键路径长度是整个工程所需的最短工期。
如何确定关键路径？
事件Vj的最早发生时间:Ve(j)
从源点到vj的最长路径长度
其决定了所有以vj为尾的弧所表示的活动的最早开始时间
求法：从ve(0)=0开始向前递推
T是所有以第j个顶点为头的弧的集合
事件Vj的最迟发生时间:Vl(j)
从顶点i到终点的最短路径长度
求法：从vl(n-1)=ve(n-1)起向前递推
活动ai的最早开始时间:e(i)
若该活动在弧上，则活动ai的最早开始时间应等于事件vi的最早发生时间
活动ai的最迟开始时间:l(i)
在不推迟整个工程完成的前提下，活动ai最迟必须开始进行的时间
若ai由弧表示，则ai的最晚开始事件要保证事件vj的最迟发生时间不拖后。因此有
l(i)-e(i)——表示完成活动ai的时间余量
关键活动:l(i)=e(i)的活动，即关键路径上的活动
因为关键路径上的所有活动都是关键活动，所以提前完成非关键活动并不能加快工程的进度。
?求关键路径步骤
求Ve(i)
求Vl(j)
求e(i)
求l(i)
计算l(i)-e(i)
小结
习题
选择题
1.在一个图中，所有顶点的度数之和等于图的边数的()倍
A.1/2B.1C.2D.4
C
2.在一个有向图中，所有顶点的入度之和等于所有顶点的出度之和的()倍
A.1/2B.1C.2D.4
B
3.具有n个顶点的有向图最多有()条边
A．nB．n(n-1)C．n(n+1)D．n2
B
4.n个顶点的连通图用邻接矩阵表示时，该矩阵至少有()个非零元素
A．nB．2(n-1)C．n/2D．n2
B
所谓连通图一定是无向图,有向的叫做强连通图连通n个顶点,至少只需要n-1条边就可以了,或者说就是生成树由于无向图的每条边同时关联两个顶点,因此邻接矩阵中每条边被存储了两次（也就是说是对称矩阵）,因此至少有2(n-1)个非零元素
5.G是一个非连通无向图，共有28条边，则该图至少有（）个顶点。
A．7B．8C．9D．10
C
n个顶点最多拥有n(n-1)/2条边，所以8个顶点最多有28条边，要想28条边而且保持非连通，至少要9个节点，第九个节点是孤立的，不与任何节点连通。
6.若从无向图的任意一个顶点出发进行一次深度优先搜索可以访问图中所有的顶点，则该图一定是（）图。
A．非连通B．连通C．强连通D．有向
B
7.下面（ ）算法适合构造一个稀疏图G的最小生成树。
A.Prim算法B.Kruskal算法C.Floyd算法D.Dijkstra算法
B
8.用邻接表表示图进行广度优先遍历时，通常借助（）来实现算法。
A．栈B.队列C.树D．图
B
广度优先用队列，深度优先用栈
9.用邻接表表示图进行深度优先遍历时，通常借助（）来实现算法。
A．栈B.队列C.树D．图
A
10.深度优先遍历类似于二叉树的（）。
A.先序遍历B.中序遍历C.后序遍历D.层次遍历
A
11.广度优先遍历类似于二叉树的（）。
A.先序遍历B.中序遍历C.后序遍历D.层次遍历
D
12.图的BFS生成树的树高比DFS生成树的树高()
A.小B.相等C.小或相等D.大或相等
C
13.
14.
15.下面()方法可以判断出一个有向图是否有环
A.深度优先遍历B.拓扑排序C.求最短路径D.求关键路径
B
应用题
预览时标签不可点收录于话题#个上一篇下一篇