int visited[MAX_VERTEX_NUM]; int found;
void DFSpath(ALGraph *G,int u,int v){ int i;
for(i=1;i<=G->vexnum;i++)visited[i]=0; found=0; DFS(G,u,v); }
int path[MAX_VERTEX_NUM]; void DFS(ALGraph *G,int u,int v)
{ /*用深度优先遍历算法实现简单路径的求解*/ ArcPtr p;
if(found) return;
if(G->ag[u].firstarc==NULL){printf(“no path\\n”);return;} visited[u]=1;
for(p=G->ag[u].firstarc;p;p=p->nextarc) {
if (v==p->adjvex)
{path[u]=v; found=1; Print(u,v); return;} else if(!visited[p->adjvex])
{path[u]=p->adjvex; DFS(G,p->adjvex,v);} }
}/*DFS*/
void Print(int u,int v){ int m;
printf(\
for(m=path[u];m!=v;m=path[m]) printf(\ printf(\ }
4．设计一个深度优先遍历图的非递归算法。（图用邻接矩阵存储） 【算法分析】
在相应的深度优先遍历的非递归算法中，使用一个辅助数组visited[ ]，在visited[i]中记忆第i个顶点是否访问过。使用了一个栈s，存储回退的路径。 【算法源代码】
void DFS ( int v ,Mgraph *G) {/*从顶点v开始进行深度优先搜索*/ int visited[MAX_VERTEX_NUM]; int s[MAX_VERTEX_NUM]; int i, j, k,top; top=0;s[++top]=v;
for ( i = 0; i < G->vexnum; i++ ) visited[i] = 0; while (!top ) { k = s[top]; top--; /*栈中退出一个顶点*/ if (!visited[k] ) { printf(“%d”,k); visited[k] = 1; /*访问，并作访问标记*/ for ( j =Vertex_num-1; j >= 0; j-- ) /*检查k的所有邻接顶点*/ if ( k!= j &&!G->arcs[k][j]) s[++top]=j;/*所有邻接顶点进栈*/ } } }
5．设计一个算法，输出距离顶点v0的最短路径长度为k的所有顶点，其中路径长度指的是弧或边的数目。 【算法分析】
本题用广度优先遍历的层次遍历法求解比较简单，要输出到v0的路径长度为k的所有顶点，也就是由v0开始作为第一层，它的邻接点作为第二层，依次?，输出第k+1层上的所有元素。故在访问每一个顶点的同时，记录下它所在的层次数。为此需设置两个队列分别存放被访问的顶点及层次，且两个队列要同步操作。 【算法源代码】
#define MAX_VERTEX_NUM 20 int visited[MAX_VERTEX_NUM];
/*visited[i]=0表示i未被访问, visited[i]=1表示i已被访问*/ /**************************************/
41
void Init(SqQueue *q){ q->front=q->rear=0; }
/**************************************/ int Empty(SqQueue *q){ if (q->rear==q->front) return 1; return 0; }
/**************************************/ void Inqueue(SqQueue *q,int x){
if((q->rear+1) % MAX_VERTEX_NUM==q->front) {printf(\ return; } else{ q->rear=(q->rear+1) %MAX_VERTEX_NUM; q->data[q->rear]=x; } }
/**************************************/ int Outqueue(SqQueue *q){ if(Empty(q)){
printf(\ return -1; } else{ q->front=(q->front+1) % MAX_VERTEX_NUM; return(q->data[q->front]); } }
/**************************************/ void bfsk(int v0,int k,ALGraph *G){
/*在图G中查找距离v0的路径长度为k的所有顶点*/
int i,level,v,visited[MAX_VERTEX_NUM]; /*定义访问数组*/ ArcPtr w;
SqQueue Q1,Q2;/*定义两个队列*/ Init(&Q1);
Init(&Q2);/*两个队列初始化*/ for(i=1;i<=G->vexnum;i++) visited[i]=0; visited[v0]=1; level=1;
Inqueue(&Q1,v0);
Inqueue(&Q2,level); /*v0及层次入队列*/ while(!Empty(&Q1)&&(level w=G->ag[v].firstarc;/*取v的第一个邻接点*/ while(w){ if(!visited[w->adjvex]){ if(level==k) printf(\输出满足条件的邻接点*/ visited[w->adjvex]=1; Inqueue(&Q1,w->adjvex); Inqueue(&Q2,level+1); } w=w->nextarc; /*取v的下一个邻接点*/ } } } 6．设计一个算法，用深度优先遍历法对AOV网进行拓扑排序，检测其中是否存在环。 【算法分析】 如果从有向图中的某个顶点v出发开始遍历，在dfs(v)结束之前出现一条从顶点u到顶点v的回边，由于u在生 42 成树上是v的子孙，则有向图中必定存在包含顶点v和u的环。本算法以邻接表作为存储结构，函数返回１表示无环，返回０表示有环． 【算法源代码】 #define MAX_VERTEX_NUM 20 int visited[MAX_VERTEX_NUM]; /*visited[i]=0表示i未被访问, visited[i]=1表示i已被访问*/ int finished[MAX_VERTEX_NUM]; /*finished[i]=1表示i已被访问，finished[i]=０表示i未被访问*/ int flag=1; void dfs(ALGraph *G,VertexType v){ /*遍历时若不存在环，输出的全部顶点序列即为拓扑序列，*/ /*否则flag置为0,表示存在环*/ ArcPtr p; finished[v]=0; visited[v]=1; p=G->ag[v].firstarc; while(p){ if(visited[p->adjvex]&&(!finished[p->adjvex])) flag=0; else if(!finished[p->adjvex]){ dfs(G,p->adjvex); finished[p->adjvex]=1; } p=p->nextarc; } } void dfs_sort(ALGraph *G){ int i; for(i=0;i for(i=0;i while(flag&&i 第7章 图 7.1 选择题 1．对于一个具有n个顶点和e条边的有向图，在用邻接表表示图时，拓扑排序算法时间复杂度为（A） O(n) B） O(n+e) C） O(n*n) D） O(n*n*n) 【答案】B 2．设无向图的顶点个数为n，则该图最多有（ ）条边。 A）n-1 B）n(n-1)/2 C） n(n+1)/2 D）n2 【答案】B 3．连通分量指的是（ ） A） 无向图中的极小连通子图 B） 无向图中的极大连通子图 C） 有向图中的极小连通子图 D） 有向图中的极大连通子图 【答案】B 4．n个结点的完全有向图含有边的数目（ ） A）n*n B）n（n+1） C）n/2 D）n*（n-1） 43 ）【答案】D 5．关键路径是（ ） A） AOE网中从源点到汇点的最长路径 B） AOE网中从源点到汇点的最短路径 C） AOV网中从源点到汇点的最长路径 D） AOV网中从源点到汇点的最短路径 【答案】A 6．有向图中一个顶点的度是该顶点的（ ） A）入度 B） 出度 C） 入度与出度之和 D） （入度+出度）/2 【答案】C 7．有e条边的无向图，若用邻接表存储，表中有（ ）边结点。 A） e B） 2e C） e-1 D） 2(e-1) 【答案】B 8．实现图的广度优先搜索算法需使用的辅助数据结构为（ ） A） 栈 B） 队列 C） 二叉树 D） 树 【答案】B 9．实现图的非递归深度优先搜索算法需使用的辅助数据结构为（ ） A） 栈 B） 队列 C） 二叉树 D） 树 【答案】A 10．存储无向图的邻接矩阵一定是一个（ ） A） 上三角矩阵 B）稀疏矩阵 C） 对称矩阵 D） 对角矩阵 【答案】C 11．在一个有向图中所有顶点的入度之和等于出度之和的（ ）倍 A） 1/2 B）1 C） 2 D） 4 【答案】B 12．在图采用邻接表存储时，求最小生成树的 Prim 算法的时间复杂度为（ ） 23 A） O(n) B） O(n+e) C） O(n) D） O(n) 【答案】B 13．下列关于AOE网的叙述中，不正确的是（ ） A）关键活动不按期完成就会影响整个工程的完成时间 B）任何一个关键活动提前完成，那么整个工程将会提前完成 C）所有的关键活动提前完成，那么整个工程将会提前完成 D）某些关键活动提前完成，那么整个工程将会提前完成 【答案】B 14．具有10个顶点的无向图至少有多少条边才能保证连通（ ） A） 9 B）10 C） 11 D） 12 【答案】A 15．在含n个顶点和e条边的无向图的邻接矩阵中，零元素的个数为（ ） 22 A） e B）2e C） n-e D）n-2e 【答案】D 7.2 填空题 1．无向图中所有顶点的度数之和等于所有边数的_____________倍。 【答案】2 2．具有n个顶点的无向完全图中包含有_____________条边，具有n个顶点的有向完全图中包含有_____________条边。 【答案】（1）n(n-1)/2 （2） n(n-1) 44