数据结构算法—邻接表存储的无向图求连通分量个数

typedef struct ArcNode{
	int adjvex;//边指向的顶点
	struct ArcNode *nextarc; // 下一条边的指针 
}ArcNode;
typedef struct VNode{
	int data;//顶点信息 
	ArcNode *fristarc;//该结点的第一条边 
}VNode,AdjList[MAX];
typedef struct {
	AdjList vertices;//头结点数组
	int vexnum,arcnum; // 图的当前顶点数和边数 
}ALGraph;

无向图的连通分量： 在离散数学中，几个顶点连在一起，不和其他的顶点互通有无。即构成一个连通分量。 单个顶点也是一个连通分量。
在数据结构中，使用图的遍历算法，从某一个顶点出发，一直寻找与他邻接的顶点。访问过得顶点就标记出来（使用vis[] 数组）。直到 没有邻接的顶点 或者 所有的顶点都访问过了。每结束一次深度遍历就 count（连通分量个数） 加 1 。

顶点的信息保存在Adjlist 数组中，，输入的顶点值 和 数组中保存的索引值 可能会不同，要统一使用 索引值 所以我写了一个 LocateVex 函数 ，用来寻找 顶点值 对应的 索引值 ，并返回索引值！

#include
#include
#define MAX 100
int vis[100];
typedef struct ArcNode{
	int adjvex;//边指向的顶点
	struct ArcNode *nextarc; // 下一条边的指针 
}ArcNode;
typedef struct VNode{
	int data;//顶点信息 
	ArcNode *fristarc;//该结点的第一条边 
}VNode,AdjList[MAX];
typedef struct {
	AdjList vertices;//头结点数组
	int vexnum,arcnum; // 图的当前顶点数和边数 
}ALGraph;
//寻找v1，v2在G中的位置
int LocateVex(ALGraph *G,int v){
	int i;
	for(i=0;i<=G->vexnum;i++)
		if(G->vertices[i].data==v)
			return i;
} 
//创建图
void creatGraph(ALGraph *G){
	int i,j,k,m,n;
	ArcNode *s;
	printf("请输入图的顶点数和边数：");
	scanf("%d%d",&G->vexnum,&G->arcnum);
	getchar();//吃掉回车
	printf("请依次输入顶点集");
	for(i=0;ivexnum;i++){
		scanf("%d",&G->vertices[i].data);
		getchar();
	}
	for(i=0;ivexnum;i++)
		G->vertices[i].fristarc=NULL;
	for(k=0;karcnum;k++){
		printf("请输入一条边的两个结点：");
		scanf("%d%d",&i,&j);
		m=LocateVex(G,i);// 不能用输入的结点信息，这里要使用 结点信息数组中的 索引值，不然会出错 
		n=LocateVex(G,j);
		s=(ArcNode*)malloc(sizeof(ArcNode));// 头插法 建立链表 
		s->adjvex=j;
		s->nextarc=G->vertices[m].fristarc;
		G->vertices[m].fristarc=s;
		//生成对称结点   无向图  
		s=(ArcNode*)malloc(sizeof(ArcNode));
		s->adjvex=i;
		s->nextarc=G->vertices[n].fristarc;
		G->vertices[n].fristarc=s;
	}
}
void readGraph(ALGraph G){ //深度递归 
	int i,j;
	ArcNode *p;
	for(i=0;inextarc)
			printf(" %d",p->adjvex);
		printf("n");
	}
}
// 求连通个数   深度优先算法 
void DFS(int x,ArcNode *p,ALGraph *G){
	vis[x]=1;  // 将 x 标记已访问   
	for(p = G->vertices[x].fristarc;p;p=p->nextarc){ //找到 链表  依次访问    和 readGraph 的for循环一样  深度递归算法 
		if(!vis[LocateVex(G,p->adjvex)]){ // p->adjvex 当前结点未访问  
			int i=LocateVex(G,p->adjvex); 
			DFS(i,p,G); 
		}
	}
}
int main(){
	ALGraph G;
	creatGraph(&G);
	readGraph(G);
	int count=0;
	for(int i=0;i