目录
1.无向图的连通分量
2.求解连通分量算法的实现
3.有向图的强连通分量
4.求解有向图的强连通分量
使用C语言实现并查集
有向图和无向图
1.无向图的连通分量
无向图G中，如果存在从顶点v1到顶点v2有路径，那么v1和v2是连通的。
如果对于无向图中的任意两个顶点vi和vj之间都是连通的，那么无向图G是连通图。
连通分量：是无向图中的极大连通子图。
如图一所示为连通图：
如图二所示不是连通图（有是两个连通分量）：
注：由于图二中存在v6,v7和v1,v2,v3,v4,v5是不完全连通的，所以属于两个不同的连通分量，这对于无向图来说是这样，而对于有向图来说的话，判断更加的复杂。
2.求解连通分量算法的实现
思路：首先读者需要对并查集 进行了解，其中主要是查找和合并操作以及路径压缩的方法。由于开始的时候对parent数组初始化都为节点自身，使用rank数组记录每一个集合中合并成的树的高度，将高度矮的合并到高度高的树上；判断无向图的连通分量，就是通过并查集的查找操作，查找到一个节点的根节点，判断这两个节点的根节点是否相同，不同的话表示属于两个集合，也就是两个不同的连通分量。最后就是输出每一个连通分量的集合。
#include
#include
#define MAXSIZE 15
typedef int ElemType;
int parent[MAXSIZE];
int rank[MAXSIZE];
void init(){
for(int i=0;i parent[i]=i; rank[i]=0; } } //并查集查找操作(包含路径压缩) int find(int x){ if(parent[x]==x){ return x; } return parent[x]=find(parent[x]); } //合并操作 void Union(int x,int y){ int fx=find(x); int fy=find(y); //当x和y属于不同的集合时，进行合并操作 if(fx!=fy){ if(rank[fx]>rank[fy]){ parent[fy]=fx; }else{ parent[fx]=fy; if(rank[fx]==rank[fy]){ rank[fx]++; } } } } int main(){ int n,m; init(); printf("请输入无向图的顶点数: "); scanf("%d",&n); printf("请输入无向图的边数: "); scanf("%d",&m); printf("请输入无向图的边: \n"); for(int i=1;i<=m;i++){ int u,v; scanf("%d %d",&u,&v); Union(u,v); } int count=0; //note用来记录每个连通分量的根节点 int note[MAXSIZE]; for(int i=1;i<=n;i++){ int fx=find(i); if(fx==i){ count++; note[count]=fx; } } printf("无向连通图的连通分量: %d\n",count); for(int i=1;i<=count;i++){ printf("连通分量[%d]: ",i); for(int j=1;j<=n;j++){ int fx=find(j); if(fx==note[i]){ printf("%d\t",j); } } printf("\n"); } return 0; } /* 7 6 1 2 1 4 2 3 3 4 2 5 6 7 */ 3.有向图的强连通分量 有向图G中，如果对于每一对,从vi到vj和vj到vi都存在路径，则图G为强连通图。 强连通分量：有向图中的极大连通子图。 如下图所示，虽然原图不是一个强连通图，但是有两个强连通分量： 4.求解有向图的强连通分量 关于深度优先搜索和广度优先搜索请看上面给出的链接。 思路：首先是进行深度优先遍历，并将遍历的结果存储在finish数组中；正向遍历完成之后就是进行逆向深度优先遍历，正向边使用edge二维数组存储，逆向边使用redge二维数组存储；逆向深度优先遍历的时候使用正向遍历的结果finish，从finish[n]到finish[1]进行遍历，并且使用k来记录强连通分量的个数，Set数组记录强连通分量的集合。 #include #include #define MAXSIZE 15 typedef int ElemType; //用于记录深度优先搜索过程中访问的节点 int finish[MAXSIZE]; //用于记录节点是否被访问 int visit[MAXSIZE]; //记录正向边 int edge[MAXSIZE][MAXSIZE]; //记录反向边 int redge[MAXSIZE][MAXSIZE]; //图的顶点数和边数 int n,m; //记录强连通分量的集合 int Set[MAXSIZE]; //k用来记录强连通分量的个数 int k=0; //记录访问的顶点数 int cnt=0; //初始化 void init(){ for(int i=0;i visit[i]=0; finish[i]=0; Set[i]=0; for(int j=0;j edge[i][j]=0; redge[i][j]=0; } } } //深度优先搜索 void dfs(int v){ visit[v]=1; for(int i=1;i<=n;i++){ if(visit[i]==0&&edge[v][i]==1){ dfs(i); } } //记录访问的节点 finish[++cnt]=v; } //反向深度优先搜索 void rdfs(int v,int k){ visit[v]=1; Set[v]=k; for(int i=1;i<=n;i++){ if(visit[i]==0&&redge[v][i]==1){ rdfs(i,k); } } } //求解强连通分量 void Solve(){ //首先进行正向的深度优先搜索 for(int i=1;i<=n;i++){ if(visit[i]==0){ dfs(i); } } //对visit重新进行初始化 for(int i=0;i visit[i]=0; } //进行逆向的深度优先搜索 for(int i=n;i>=1;i--){ int v=finish[i]; if(visit[v]==0){ k++; rdfs(v,k); } } } //输出强连通分量集合 void display(){ //打印深度优先访问的结果 printf("cnt = %d\n",cnt); for(int i=1;i<=cnt;i++){ printf("%d\t",finish[i]); } printf("\n"); printf("强连通分量的个数: %d\n",k); for(int i=1;i<=k;i++){ printf("强连通分量[%d]: ",i); for(int j=1;j<=n;j++){ if(Set[j]==i){ printf("%d\t",j); } } printf("\n"); } } int main(){ init(); printf("请输入无向图的顶点数: "); scanf("%d",&n); printf("请输入无向图的边数: "); scanf("%d",&m); printf("请输入无向图的边: \n"); for(int i=1;i<=m;i++){ int u,v; scanf("%d %d",&u,&v); edge[u][v]=1; redge[v][u]=1; } Solve(); display(); return 0; } /* 4 4 1 3 1 2 3 4 4 1 4 7 1 2 1 3 3 1 3 4 4 3 4 2 4 1 7 9 1 2 1 3 1 4 2 1 2 4 5 2 4 5 6 7 7 6 */