数据结构算法复习3：图相关考点
在算法实现方面要求，熟练掌握图的两种遍历方法，并能够根据图的基本原理解决一些应用问题，如：判定图的连通性、判定是否有环、计算特定路径等。
1，一个连通图采用邻接表作为存储结构，设计一个算法实现从顶点v出发的深度优先遍历的非递归过程。
void DFS1(AGraph *G,int v)
{ int visited[MAXV],i,j;
int St[MAXV],top=-1;
ArcNode *p;
for (i=0;i<G->n;i++) //访问标志数置初值
visited[i]=0;
top++;
St[top]=v; //初始顶点进栈
visited[v]=1; //修改访问标志
while (top>-1) //栈不空时循环
{ j=St[top];top--; //出栈
printf("%d ",j); //访问节点j
p=G->adjlist[j].firstarc; //找第一个邻接点
while (p!=NULL)
{ if (visited[p->adjvex]==0) //将未访问过的邻接点进栈
{ top++;
St[top]=p->adjvex;
visited[p->adjvex]=1; //修改访问标志
}
p=p->nextarc; //找下一个邻接点
}
}
}2，设计一个算法，求无向图G（采用邻接表存储）的连通分量个数。
int visited[MAXV]={0};
int Getnum(AGraph *G) //求图G的连通分量
{ int i,n=0,visited[MAXVEX];
for (i=0;i<G->n;i++)
if (visited[i]==0)
{ DFS(G,i); //对图G从顶点i开始进行深度优先遍历
n++; //调用DFS的次数即为连通分量数
}
return n;
}int visited[MAXV]={0};
int Getnum1(AGraph *G) //求图G的连通分量
{ int i,n=0,visited[MAXVEX];
for (i=0;i<G->n;i++)
if (visited[i]==0)
{ BFS(G,i); //对图G从顶点i开始进行广度优先遍历
n++; //调用BFS的次数即为连通分量数
}
return n;
}2.1，假设一个无向图是非连通的，采用邻接表作为存储结构，试设计一个算法，输出图中各连通分量的节点序列。
int visited[MAXV]={0};
DFSGraph(AGraph *G)
{ int i,j=1; //用j记录连通分量的序号
for (i=0;i<G->n;i++)
if (visited[i]==0)
{ printf("第%d个连通分量节点序列:",j++);
DFS(G,i); //调用前面的深度优先遍历算法
}
}int visited[MAXV]={0};
BFSGraph(AGraph *G)
{ int i,j=1; //用j记录连通分量的序号
for (i=0;i<G->n;i++)
if (visited[i]==0)
{ printf("第%d个连通分量节点序列:",j++);
BFS(G,i); //调用前面的广度优先遍历算法
}
}3，假设无向图G采用邻接表存储，设计一个算法，判断图G是否为连通图。若为连通图返回1；否则返回0。
void DFS2(AGraph *G,int v,int &vn,int &en){ ArcNode *p;
visited[v]=1;vn++; //遍历过的顶点数增1
p=G->adjlist[v].firstarc;
while (p!=NULL)
{ en++; //遍历过的边数增1
if (visited[p->adjvex]==0)
DFS2(G,p->adjvex,vn,en);
p=p->nextarc;
}
}
int GIsTree(AGraph *G) //判断无向图G是否是一棵树
{ int vn=0,en=0,i;
for (i=0;i<G->n;i++)
visited[i]=0;
DFS2(G,1,vn,en);
if (vn==G->n && en==2*(G->n-1))
return 1; //遍历顶点为G->n个,边数为2(g->n-1),则为树
else
return 0;
}3.1，设计一个算法，判断一个无向图G是否是一棵树。若是树，返回1；否则返回0。
void DFS2(AGraph *G,int v,int &vn,int &en){ ArcNode *p;
visited[v]=1;vn++; //遍历过的顶点数增1
p=G->adjlist[v].firstarc;
while (p!=NULL)
{ en++; //遍历过的边数增1
if (visited[p->adjvex]==0)
DFS2(G,p->adjvex,vn,en);
p=p->nextarc;
}
}
int GIsTree(AGraph *G) //判断无向图G是否是一棵树
{ int vn=0,en=0,i;
for (i=0;i<G->n;i++)
visited[i]=0;
DFS2(G,1,vn,en);
if (vn==G->n && en==2*(G->n-1))
return 1; //遍历顶点为G->n个,边数为2(g->n-1),则为树
else
return 0;
}4,假设一个连通图采用邻接表作为存储结构，试设计一个算法，判断其中是否存在回路。
void Cycle(AGraph *G,int v,bool &has)
{ //调用时has置初值false
ArcNode *p;
int w;
visited[v]=1; //置已访问标记
p=G->adjlist[v].firstarc; //p指向顶点v的第一个邻接点
while (p!=NULL)
{ w= p->adjvex;
if (visited[i]==0) //若顶点w未访问,递归访问它
Cycle(G,w,has);
else //又找到了已访问过的顶点说明有回路
has=true;
p=p->nextarc; //找下一个邻接点
}
}5，假设图G采用邻接表存储，设计一个算法判断图G中顶点u到顶点v之间是否有简单路径。
void ExistPath(AGraph *G,int u,int v,int &has)
{ //has表示u到v是否有路径,初值为0
int w;
ArcNode *p;
visited[u]=1; //置已访问标记
if (u==v) //找到了一条路径
{ has=1;
return;
}
p=G->adjlist[u].firstarc; //p指向顶点u的第一个相邻点
while (p!=NULL)
{ w=p->adjvex; //w为顶点u的相邻顶点
if (visited[w]==0) //若w顶点未访问,递归访问它
ExistPath(G,w,v,has);
p=p->nextarc; //p指向顶点v的下一个相邻点
}
}6，假设图G采用邻接表存储，设计一个算法，输出图G中从顶点u到v的所有简单路径。
void FindPath(AGraph *G,int u,int v,int path[ ],int d)
//d是到当前为止已走过的路径长度,调用时初值为-1
{ int w,i;
ArcNode *p;
d++; //路径长度增1
path[d]=u; //将当前顶点添加到路径中</p>
visited[u]=1; //置已访问标记
if (u==v) //找到一条路径则输出
{ for (i=0;i<=d;i++)
printf("%2d",path[i]);
printf("\n");
}
p=G->adjlist[u].firstarc; //p指向v的第一个相邻点
while (p!=NULL)
{ w=p->adjvex; //w为顶点u的相邻顶点
if (visited[w]==0) //若w顶点未访问,递归访问它
FindPath(G,w,v,path,d);
p=p->nextarc; //p指向v的下一个相邻点
}
visited[u]=0; //恢复环境,使该顶点可重新使用
}7，假设不带权图G采用邻接表存储，设计一个算法，采用BFS方式输出图G中从顶点u到v的最短路径。
typedef struct
{ int data; //顶点编号
int parent; //前一个顶点的位置
} QUERE; //非循环队列类型
void ShortPath(AGraph *G,int u,int v)
{ //输出从顶点u到顶点v的最短逆路径
ArcNode *p;
int w,i;
QUERE qu[MAXV]; //非环形队列
int front=-1,rear=-1; //队列的头、尾指针
int visited[MAXV];
for (i=0;i<G->n;i++) //访问标记置初值0
visited[i]=0;
rear++; //顶点u进队
qu[rear].data=u;
qu[rear].parent=-1;
visited[u]=1;
while (front!=rear) //队不空循环
{ front++; //出队顶点w
w=qu[front].data;
if (w==v) //找到v时输出路径之逆并退出
{ i=front; //通过队列输出逆路径
while (qu[i].parent!=-1)
{ printf("%d<-",qu[i].data);
i=qu[i].parent;
}
printf("%2d\n",qu[i].data);
break;
}
p=G->adjlist[w].firstarc; //找w的第一个邻接点
while (p!=NULL)
{ if (visited[p->adjvex]==0)
{ visited[p->adjvex]=1;
rear++; //将w的未访问过的邻接点进队
qu[rear].data=p->adjvex;
qu[rear].parent=front;
}
p=p->nextarc; //找w的下一个邻接点
}
}
}