（1）假设图G采用邻接表存储，设计一个程序，判断无向图G是否连通。若连通则返回1；否则返回0。
（2）假设图G采用邻接表存储，设计一个程序，判断G中顶点i到顶点j是否有路径。若有返回1；否则返回0。
（3）编写对邻接表存储的从顶点vi出发的深度优先遍历图的非递归算法并上机实现。
（1）采用图的遍历方式判断无向图G是否连通。这里用深度优先遍历方法，先给visited[ ]数组置初值0，然后从0顶点开始遍历该图。在一次遍历之后，若所有顶点i的visited[i]均为1，则该图是连通的；否则不连通。对应的算法如下：
int visited[MAXVEX]; /*全局变量*/
int Connect(MyGraph *G) /*判断无向图G的连通性*/
{
int i,flag=1;
for(i=0;i<G->n;i++) /*visited数组置初值*/
visited[i]=0;
DFS(G,0); /*调用前面的DFS算法，从顶点0开始深度优先遍历*/
for(i=0;i<G->n;i++)
if(visited[i]==0)
{
flag=0;
break;
}
return flag;
}
注意：本例也可以采用广度优先遍历算法求解，只需将调用DFS(G,0)改为调用BFS(G,0)。
（2）采用图的遍历方式判断图G是否连通。这里用深度优先遍历方法，先给visited[ ]数组置初值0，然后从i顶点开始遍历该图，在遍历完成后，若顶点j已访问，说明顶点i到顶点j存在路径，否则说明顶点i到顶点j不存在路径。对应的算法如下：
int visited[MAXVEX]; /*全局变量*/
int Connect(MyGraph *G,int i,int j) /*判断顶点i到顶点j是否有路径*/
{
int k;
for(k=0;k<G->n;k++) /*visited数组置初值*/
visited[k]=0;
DFS(g,i); /*调用前面的DFS算法,从顶点i开始深度优先遍历*/
if(visited[j]==1)
return(1);
else
return(0);
}
注意：本例也可以采用广度优先遍历算法求解，只需将调用DFS(G,i)改为调用BFS (G,i)。
（3）在非递归算法中另设一个顺序栈s[MaxV]，保存当前访问顶点的邻接顶点的指针，就可以由这个指针依次找到当前访问顶点的所有邻接顶点。退栈元素的某个邻接顶点进行访问时，首先将下一个邻接顶点的指针进栈，再将这个邻接顶点作为当前顶点，重复该过程，直到栈为空，将所有与出栈顶点有路径的顶点全访问完。按深度优先遍历图的算法描述如下：
#define MaxV 100
void bfsl (ALGraph *G)
{
int i,j,top,visited[MaxV];
Enode *p,*s[MaxV];
for(i=0;i<G->n;i++)
visited[i]=0;
for(i=0;i<G->n;i++)
if(visited[i]==0)
{
top=0;
visited[i]=1;
printf("%c",G->adjlist[i].data);
s[top++]=G->adjlist[i].firste;
while(top>0)
{
p=s[--top;
if(p)
{
s[top++]=p->next;
j=p->adjivex;
if(Visited[j]==0)
{
visited[j]=1;
printf("%c",G->adjlist[j].data);
s[top++]=G->adjlist[j].firste;
}
}
}
}
}