9-13.c

这个是数据结构经典实现算法

#include "stdio.h"
#define MaxVertexNum 100
typedef enum{FALSE,TRUE}Boolean;/*FALSE为0,TRUE为1*/
Boolean visited[MaxVertexNum];
typedef int VertexType;
typedef struct node{/*边表结点*/
		int adjvex; /*邻接点域*/
		struct node *next; /*链域*/
		/*若要表示边上的权,则应增加一个数据域*/
}EdgeNode;
typedef struct vnode{ /*顶点表结点*/
		VertexType vertex; /*顶点域*/
		EdgeNode *firstedge;/*边表头指针*/
}VertexNode;
typedef VertexNode AdjList[MaxVertexNum];/*AdjList是邻接表类型*/
typedef struct ALGraph{
		AdjList adjlist;/*邻接表*/
		int n,e; /*图中当前顶点数和边数 */
}Graphic; /*对于简单的应用,无须定义此类型,可直接使用AdjList类型。*/
void CreateGraphic(Graphic *G)
{/*建立无向图的邻接表表示*/
     	int i,j,k;
      	EdgeNode *s;
      	scanf("%d%d",&G->n,&G->e); /*读人顶点数和边数*/
      	for(i=0;i<G->n;i++){/*建立顶点表*/
        	G->adjlist[i].vertex=getchar(); /*读入顶点信息*/
        	G->adjlist[i].firstedge=NULL;/*边表置为空表*/
       	}
      	for(k=0;k<G->e;k++){/*建立边表*/
         	scanf("%d%d",&i,&j);/*读入边(vi,vj)的顶点对序号*/
         	s=(EdgeNode *)malloc(sizeof(EdgeNode)); /*生成边表结点*/
         	s->adjvex=j; /*邻接点序号为j*/
         	s->next=G->adjlist[i].firstedge;
 	        G->adjlist[i].firstedge=s; /*将新结点*s插入顶点vi的边表头部*/
         	s=(EdgeNode *)malloc(sizeof(EdgeNode));
         	s->adjvex=i; /*邻接点序号为i*/
         	s->next=G->adjlist[j].firstedge;
         	G->adjlist[j].firstedge=s; /*将新结点*s插入顶点vj的边表头部*/
        }   
} 
void DFS(Graphic *G,int i)
{ /*以vi为出发点对邻接表表示的图G进行深度优先搜索*/
    EdgeNode *p;
    printf("visit vertex：%c",G->adjlist[i].vertex);/*访问顶点vi*/
    visited[i]=TRUE; /*标记vi已访问*/
    p=G->adjlist[i].firstedge; /*取vi边表的头指针*/
    while(p)
		{/*依次搜索vi的邻接点vj,这里j=p->adjvex*/
      	if (!visited[p->adjvex])/*若vi尚未被访问*/
        	DFS(G,p->adjvex);/*则以Vj为出发点向纵深搜索*/
      	p=p->next; //找vi的下一邻接点
     }
}
Boolean Connected(Graphic *G)
{/*当且仅当图是连通的，则返回True*/
	int n =G->n ;
	int i;
	/* 置所有顶点为未到达顶点*/
	for ( i= 1; i <= n; i++)
		visited[i] = 0;
	/* 对从顶点1出发可到达的顶点进行标记*/
	DFS(G, 1);
	/*检查是否所有顶点都已经被标记*/
	for (i = 1; i <= n; i++)
		if (!visited[i]) 
			return 0;
	return 1;
}
main()
{
	Graphic *G;
	CreateGraphic(G);
	if(Connected(G))
		printf("图连通");
	else
		printf("图不连通");
}