数据结构算法—邻接表存储的无向图求连通分量个数
邻接表存储结构
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 。
tips：
顶点的信息保存在Adjlist 数组中，，输入的顶点值 和 数组中保存的索引值 可能会不同，要统一使用 索引值 所以我写了一个 LocateVex 函数 ，用来寻找 顶点值 对应的 索引值 ，并返回索引值！
完整代码
#include<stdio.h>
#include<stdlib.h>
#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;i<G->vexnum;i++){
scanf("%d",&G->vertices[i].data);
getchar();
}
for(i=0;i<G->vexnum;i++)
G->vertices[i].fristarc=NULL;
for(k=0;k<G->arcnum;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;i<G.vexnum;i++){
printf("%d : ",G.vertices[i].data);// 结点信息保存在 data 域中
for(p=G.vertices[i].fristarc;p;p=p->nextarc)
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<G.vexnum;i++)
vis[i]=0;
ArcNode *p;
for(int i=0;i<G.vexnum;i++){
p = G.vertices[i].fristarc;
if(!vis[i]){
DFS(i,p,&G);
count++; // 每当深度调用完毕，意味着：走到头了。是一个连通分量，再判断 有没有未被访问的结点，如果有继续，没有循环结束。count即为连通分量个数
}
}
printf("连通分量个数为：%d",count);
}
运行结果实例：
请输入图的顶点数和边数：6 3
请依次输入顶点集
1 2 3 4 5 6
请输入一条边的两个结点：1 3
请输入一条边的两个结点：2 4
请输入一条边的两个结点：4 6
1 : 3
2 : 4
3 : 1
4 : 6 2
5 :
6 : 4
连通分量个数为：4
--------------------------------
Process exited after 11.75 seconds with return value 0
请按任意键继续. . .
