第七章 图：图的逻辑结构特征就是其结点（顶点）的前趋和后继的个数都是没有限制的，即任意两个结点之间之间都可能相关。7.1图的定义和术语:图GraphG=（V，E），V是顶点的有穷非空集合，E是顶点偶对的有穷集。有向图Digraph：每条边有方向；无向图Undigraph：每条边没有方向。 有向完全图：具有n*（n-1）条边的有向图；无向完全图：具有n*（n-1）/2条边的无向图； 有根图：有一个顶点有路径到达其它顶点的有向图；简单路径：是经过顶点不同的路径；简单回路是开始和终端重 的简单路径； 网络：是带权的图。[单选题]
7.2图的存储结构:介绍图的4种存储结构,包括数组表示法、邻接表、十字链表、邻接多重表。
7.3图的遍历:介绍图的两种遍历算法：深度优先搜索和广度优先搜索，并结合上节的存储结构给出算法描述。
7.4图的连通性问题:首先介绍无向图的连通分量的定义，然后描述最小生成树的定义及其应用，最后重点介绍了生成最小生成树的普里姆算法及克鲁斯卡尔算法。
7.5有向无环图及其应用:首先描述了有向无环图的定义，然后定义了图的拓扑排序及如何进行拓扑排序的算法，最后定义了AOE网及求取关键路径的算法。
7.6最短路径:首先讲解了最短路径的概念及其应用，然后讲解了求解单源最短路径的Dijsktra算法，最后讲解了Floyd算法求解每一对定点之间的最短路径。
7.1图的定义和术语:图GraphG=（V，E），V是顶点的有穷非空集合，E是顶点偶对的有穷集。有向图Digraph：每条边有方向；无向图Undigraph：每条边没有方向。 有向完全图：具有n*（n-1）条边的有向图；无向完全图：具有n*（n-1）/2条边的无向图； 有根图：有一个顶点有路径到达其它顶点的有向图；简单路径：是经过顶点不同的路径；简单回路是开始和终端重 的简单路径； 网络：是带权的图。
7.2图的存储结构:介绍图的4种存储结构,包括数组表示法、邻接表、十字链表、邻接多重表。
7.3图的遍历:介绍图的两种遍历算法：深度优先搜索和广度优先搜索，并结合上节的存储结构给出算法描述。
7.4图的连通性问题:首先介绍无向图的连通分量的定义，然后描述最小生成树的定义及其应用，最后重点介绍了生成最小生成树的普里姆算法及克鲁斯卡尔算法。
7.5有向无环图及其应用:首先描述了有向无环图的定义，然后定义了图的拓扑排序及如何进行拓扑排序的算法，最后定义了AOE网及求取关键路径的算法。
7.6最短路径:首先讲解了最短路径的概念及其应用，然后讲解了求解单源最短路径的Dijsktra算法，最后讲解了Floyd算法求解每一对定点之间的最短路径。
下图中结点B的出度为( )
选项:[0, 3, 2, 1]
[单选题]
对于一个具有n个顶点的无向图,若采用邻接矩阵表示,则该矩阵的大小为（ ） ；
选项:[(n-1)× (n-1), n×(n+1), n ×n, (n-1)×n]
[单选题]采用邻接表存储的图的宽度优先遍历算法类似于二叉树的（ ）。 选项:[后序遍历, 层次遍历 , 先序遍历, 中序遍历]
[单选题]
下面的无向带权图的最小生成树包含的边有( )
选项:[ae ed dc cb eg df , ae ge gf eb bc cd , ag gf fd dc cb be, ae eb bc cd df eg]
[单选题]
判定一个有向图是否存在回路除了可以利用拓扑排序方法外,还可以利用（ ）；
选项:[深度优先遍历算法 , 求最短路径的Dijkstm方法, 求关键路径的方法, 宽度优先遍历算法][单选题]
编写算法实现建立图的邻接表
StatusCreateAG(ALGraph &G){
int n,e,k,i,j;
cout<<请输入顶点数：;
cin>>n;
cout<<请输入边数：;
cin>>e;
G.vernum=n;
G.arcnum=e;
// 建立顶点数组
for(k=0;k<G.vernum;k++){
cout<<请输入顶点信息：;
cin>>G.vertices[k].data;
G.vertices[k].firstarc=NULL;
}
// 建立邻接表
VertexType v1,v2;
ArcNode *p,*q;
for(k=0;k<G.arcnum;k++){
cout<<请输入弧的始点和终点信息，中间用空格分开:;
cin>>v1>>v2;
i=LocateVex(G,v1);
if(i<0|| i>G.vernum-1) return ERROR; j=LocateVex(G,v2);
if(j<0|| j>G.vernum-1) return ERROR; if(i==j)return ERROR; p=newArcNode; if(!p)return ERROR; p->adjvex=j;
p->nextarc=NULL;
q=G.vertices[i].firstarc;
if(!q)G.vertices[i].firstarc=p; else{
while(q->nextarc) __________ // 指针定位于邻接表的尾结点
q->nextarc=p;
}
}
return OK;
}
选项:[q->nextarc=p->nextarc, q->nextarc=NULL;, p=p->nextarc;, q=q->nextarc][单选题]
编写算法实现从邻接表中取出某个顶点V的存储位置。
intLocateVex(ALGraph& G,VertexType v){
int i=0;
while(______&&i<G.vernum) i++;
if(G.vertices[i].data==v) return i;
else return -1;
}
选项:[A.G.vertices[i++].data!=v , G.vertices[i].data!=v , G.vertices[++i].data!=v , G.vertices[i].data==v][单选题]
下面的无向带权图的最小生成树包含的边有( )
选项:[ae ed dc cb eg df , ae eb bc cd df eg, ae ge gf eb bc cd , ag gf fd dc cb be]
[单选题]
编写算法实现从邻接表中取出某个顶点V的存储位置。
intLocateVex(ALGraph& G,VertexType v){
int i=0;
while(______&&i<G.vernum) i++;
if(G.vertices[i].data==v) return i;
else return -1;
}
选项:[G.vertices[i].data!=v , G.vertices[++i].data!=v , G.vertices[i].data==v, A.G.vertices[i++].data!=v ][单选题]
对于一个具有n个顶点的无向图,若采用邻接矩阵表示,则该矩阵的大小为（ ） ；
选项:[n×(n+1), n ×n, (n-1)×n, (n-1)× (n-1)]
[单选题]
判定一个有向图是否存在回路除了可以利用拓扑排序方法外,还可以利用（ ）；
选项:[深度优先遍历算法 , 宽度优先遍历算法, 求关键路径的方法, 求最短路径的Dijkstm方法][单选题]
下图中结点B的出度为( )
选项:[3, 1, 2, 0]
[单选题]采用邻接表存储的图的宽度优先遍历算法类似于二叉树的（ ）。 选项:[层次遍历 , 先序遍历, 后序遍历, 中序遍历]
[单选题]
编写算法实现建立图的邻接表
StatusCreateAG(ALGraph &G){
int n,e,k,i,j;
cout<<请输入顶点数：;
cin>>n;
cout<<请输入边数：;
cin>>e;
G.vernum=n;
G.arcnum=e;
// 建立顶点数组
for(k=0;k<G.vernum;k++){
cout<<请输入顶点信息：;
cin>>G.vertices[k].data;
G.vertices[k].firstarc=NULL;
}
// 建立邻接表
VertexType v1,v2;
ArcNode *p,*q;
for(k=0;k<G.arcnum;k++){
cout<<请输入弧的始点和终点信息，中间用空格分开:;
cin>>v1>>v2;
i=LocateVex(G,v1);
if(i<0|| i>G.vernum-1) return ERROR; j=LocateVex(G,v2);
if(j<0|| j>G.vernum-1) return ERROR; if(i==j)return ERROR; p=newArcNode; if(!p)return ERROR; p->adjvex=j;
p->nextarc=NULL;
q=G.vertices[i].firstarc;
if(!q)G.vertices[i].firstarc=p; else{
while(q->nextarc) __________ // 指针定位于邻接表的尾结点
q->nextarc=p;
}
}
return OK;
}
选项:[q->nextarc=NULL;, q=q->nextarc, q->nextarc=p->nextarc, p=p->nextarc;]
