一、定义：

        在无向图中，如果从顶点vi到顶点vj有路径，则称vi和vj连通。如果图中任意两个顶点之间都连通，则称该图为连通图，否则，将其中的较大连通子图称为连通分量。
　　在有向图中，如果对于每一对顶点vi和vj，从vi到vj和从vj到vi都有路径，则称该图为强连通图；否则，将其中的极大连通子图称为强连通分量。
　　
上面有向图的连通分量个数为2

二、分析：

• 我们给图的每个结点设置一个访问标志，用visited[]数组来表示，0代表未访问，1代表已经访问
• 然后我们求从每个节点开始的深度优先遍历序列，每访问到一个结点，就将该结点对应的visited[]置1.
• 若当前结点已经被访问过(也就是visited[]数组中对应位置为1)，那这个结点就不用再深度优先遍历，
• 只有visited[]对应位置为0时才在当前结点进行深度优先遍历，深度优先遍历的次数就是该图的连通分量个数。

三、核心算法：

typedef struct {
	DataType list[MaxSize];
	int size;
}SeqList;
typedef struct {
	SeqList Vertices;   //存放顶点的顺序表
	int edge[MaxVertices][MaxVertices];//存放边的邻接矩阵
	int numOfEdges;            //边的条数
}AdjMGraph;        //图的结构体定义

//这里假设图的顶点信息为字母类型
//连通图的深度优先遍历函数
void DepthFSearch(AdjMGraph G, int v, int visited[], void Visit(DataType item)) {
	//连通图G以v为顶点的、访问操作为Visit()的深度优先遍历
	//数组visited标记相应顶点是否已访问过(0表示未访问，1表示已访问)
	int w;
	Visit(G.Vertices.list[v]);//访问顶点v
	visited[v] = 1;    //置已被访问标记
	w = GetFirstVex(G,v);//取第一个邻接顶点
	while (w != -1) {
		if (!visited[w])
			DepthFSearch(G, w, visited, Visit);  //递归
		w = GetNextVex(G, v, w);     //取下一个邻接顶点
	}
}
//非连通图的深度优先遍历函数（返回值为连通分量的个数）
int DepthFirstSearch(AdjMGraph G, void Visit(DataType item))
//非连通图G的访问操作为Visit()的深度优先遍历
{
	int i;
	int count = 0;
	int *visited = (int *)malloc(sizeof(int)*G.Vertices.size);
	for (i = 0; i < G.Vertices.size; i++) {
		visited[i] = 0;
	}
	for (i = 0; i < G.Vertices.size; i++) {
		if (!visited[i]){
			count++;//统计连通分量的个数
			DepthFSearch(G, i, visited, Visit);//以每个顶点为初始顶点进行调用
		}
	}
	free(visited);
	return count;
}

四、完整代码：

下面这个是有向图的代码，若要改为无向图，就将插入点和插入边的函数修改就行。
AdjMGraph.h:

#pragma once
//图的邻接矩阵存储结构
#include "SeqList.h"
typedef struct {
	SeqList Vertices;   //存放顶点的顺序表
	int edge[MaxVertices][MaxVertices];//存放边的邻接矩阵
	int numOfEdges;            //边的条数
}AdjMGraph;        //图的结构体定义
//初始化
void Initiate(AdjMGraph *G, int n)
{
	int i, j;
	for(i=0;i<n;i++)
		for (j = 0; j < n; j++) {
			if (i == j) {
				G->edge[i][j] = 0;
			}
			else {
				G->edge[i][j] = MaxWeight;    //MaxWeight表示无穷大
			}
		}
	G->numOfEdges = 0;      //边的条数置零
	ListInitiate(&G->Vertices);   //顺序表初始化
}
//插入顶点
void InsertVertex(AdjMGraph *G, DataType vertex) {
	//在途中插入顶点Vertex
	ListInsert(&G->Vertices, G->Vertices.size, vertex);//在顺序表尾部插入
}
/*
插入边
在有向图中插入一条有向边。对于增加无向边的操作，可通过增加两条有向边完成。
*/
void InsertEdge(AdjMGraph *G, int v1, int v2, int weight) {
	//在图中插入边<v1,v2>,边<v1,v2>的权为weight
	if (v1 < 0 || v1 >= G->Vertices.size || v2 < 0 || v2 >= G->Vertices.size) {
		printf("参数v1或v2越界出错!\n");
		return;
	}
	G->edge[v1][v2] = weight;
	G->numOfEdges++;
}                                                                               
/*
删除边
在图中删除一条有向边。对于删除无向边的操作，可通过取消两条有向边完成
*/
void DeleteEdge(AdjMGraph *G, int v1, int v2) {
	//在图中删除边<v1,v2>
	if (v1 < 0 || v1 >= G->Vertices.size || v2 < 0 || v2 >= G->Vertices.size || v1 == v2) {
		printf("参数v1或者v2越界出错!\n");
		return;
	}
	if (G->edge[v1][v2] == MaxWeight || v1 == v2) {
		printf("该边不存在!\n");
		return;
	}
	G->edge[v1][v2] = MaxWeight;
	G->numOfEdges--;
}
/*
取第一个邻接顶点
对于邻接矩阵来说，顶点v的第一个邻接顶点，就是邻接矩阵的顶点v行中
从第一个矩阵元素开始的非0且非无穷大的顶点
*/
int GetFirstVex(AdjMGraph G, int v)
//在图G中寻找序号为v的顶点的第一个邻接顶点
//如果这样的邻接顶点存在，则返回该邻接顶点的序号，否则返回-1
{
	int col;
	if (v < 0 || v >= G.Vertices.size) {
		printf("参数v1越界出错");
		return -1;
	}
	else {
		for (col = 0; col < G.Vertices.size; col++) {
			if (G.edge[v][col] > 0 && G.edge[v][col] < MaxWeight)
				return col;
		}
		return -1;
	}
}
/*
取下一个邻接顶点
对于邻接矩阵存储结构来说，顶点v1的邻接顶点v2的下一个邻接顶点，就是邻接矩阵的顶点
v行中从第v2+1个矩阵元素开始的非0且非无穷大的顶点
*/
int GetNextVex(AdjMGraph G, int v1, int v2) {
	//在图中寻找v1的顶点的邻接顶点v2的下一个邻接顶点
	//如果这样的邻接顶点存在，则返回该邻接顶点的序号，否则返回-1
	//v1和v2都是相应顶点的序号
	int col;
	if (v1 < 0 || v1 >= G.Vertices.size || v2 < 0 || v2 >= G.Vertices.size) {
		printf("参数v1或v2越界出错!\n");
		return -1;
	}
	for (col = v2 + 1; col < G.Vertices.size; col++) {
		if (G.edge[v1][col] > 0 && G.edge[v1][col] < MaxWeight)
			return col;
	}
	return -1;
}

AdjMGraphCreate.h

#pragma once
#include "AdjMGraph.h"
typedef struct {
	int Row;   //行下标
	int col;   //列下标
	int weight;  //权值
}RowColWeight;   //边信息结构体定义
void CreateGraph(AdjMGraph *G, char V[], int n, RowColWeight E[], int e) {
	//在图G中插入n个顶点信息V和e条边信息E
	int i, k;
	Initiate(G, n);    //顶点顺序表初始化
	for (i = 0; i < n; i++)
		InsertVertex(G, V[i]);//插入顶点
	for (k = 0; k < e; k++)
		InsertEdge(G, E[k].Row, E[k].col, E[k].weight);//插入边
}

AdjMGraphTraverse.h

#pragma once
#include"AdjMGraph.h"
#include"SeqList.h"
//这里假设图的顶点信息为字母类型
//连通图的深度优先遍历函数
void DepthFSearch(AdjMGraph G, int v, int visited[], void Visit(DataType item)) {
	//连通图G以v为顶点的、访问操作为Visit()的深度优先遍历
	//数组visited标记相应顶点是否已访问过(0表示未访问，1表示已访问)
	int w;
	Visit(G.Vertices.list[v]);//访问顶点v
	visited[v] = 1;    //置已被访问标记
	w = GetFirstVex(G,v);//取第一个邻接顶点
	while (w != -1) {
		if (!visited[w])
			DepthFSearch(G, w, visited, Visit);  //递归
		w = GetNextVex(G, v, w);     //取下一个邻接顶点
	}
}
//非连通图的深度优先遍历函数（返回值为连通分量的个数）
int DepthFirstSearch(AdjMGraph G, void Visit(DataType item))
//非连通图G的访问操作为Visit()的深度优先遍历
{
	int i;
	int count = 0;
	int *visited = (int *)malloc(sizeof(int)*G.Vertices.size);
	for (i = 0; i < G.Vertices.size; i++) {
		visited[i] = 0;
	}
	for (i = 0; i < G.Vertices.size; i++) {
		if (!visited[i]){
			count++;//统计连通分量的个数
			DepthFSearch(G, i, visited, Visit);//以每个顶点为初始顶点进行调用
		}
	}
	free(visited);
	return count;
}

SeqList.h

#pragma once
typedef struct {
	DataType list[MaxSize];
	int size;
}SeqList;
//初始化
void ListInitiate(SeqList *L) {
	L->size = 0;
}
//求当前数据元素个数
int ListLength(SeqList L) {
	return L.size;
}
//插入数据元素
int ListInsert(SeqList *L, int i, DataType x) {
	//在顺序表的第i个位置(0<=i<=size)个位置前插入数据元素值x
	//插入成功返回1，插入失败返回0
	int j;
	if (L->size >= MaxSize) {
		printf("顺序表已满无法插入!");
		return 0;
	}
	else if (i<0 || i>L->size) {
		printf("参数i不合法!\n");
		return 0;
	}
	else {
		//从后向前依次后移数据，为插入做准备
		for (j = L->size; j > i; j--) {
			L->list[j] = L->list[j - 1];
		}
		L->list[i] = x;
		L->size++;
		return 1;
	}
}
//删除数据元素
int ListDelete(SeqList *L, int i, DataType *x) {
	//删除顺序表L中第i(0<=i<=size-1)个位置处的数据元素并保存到x中
	//删除成功返回1，删除失败返回0
	int j;
	if (L->size <= 0) {
		printf("顺序表已空无法删除!\n");
		return 0;
	}
	else if (i<0 || i>L->size - 1) {
		printf("参数i不合法");
		return 0;
	}
	else {
		*x = L->list[i];//保存删除的元素到x中
		//从前向后依次前移
		for (j = i + 1; j <= L->size - 1; j++) {
			L->list[j - 1] = L->list[j];
		}
		L->size--;
		return 1;
	}
}
//取数据元素
int ListGet(SeqList L, int i, DataType *x) {
	//取顺序表的第i个数据元素存于x中，成功返回1，失败返回0
	if (i<0 || i>L.size - 1) {
		printf("参数i不合法!");
		return 0;
	}
	else {
		*x = L.list[i];
		return 1;
	}
}

test.cpp:

#pragma once
#include<stdio.h>
#include<stdlib.h>
typedef char DataType;
#define MaxSize 10
#define MaxVertices 10
#define MaxWeight 10000
#include "SeqList.h"
#include "AdjMGraph.h"
#include "AdjMGraphCreate.h"
#include"AdjMGraphTraverse.h"
void Visit(DataType item) {//定义访问操作函数
	printf("%c  ", item);
}
int main() {
	AdjMGraph g1;
	DataType a[] = { 'A','B','C','D','E' };
	RowColWeight rcw[] = { {0,1,10},{0,4,20},{1,3,30},{2,1,40},{3,2,50} };
	int n = 5, e = 5;
	int i, j;
	CreateGraph(&g1, a, n, rcw, e);
	//DeleteEdge(&g1, 0, 4);//删除边<0,4>
	printf("顶点集合为:");
	for (i = 0; i < g1.Vertices.size; i++) {
		printf("%c  ", g1.Vertices.list[i]);
	}
	printf("\n");
	printf("权值集合为:\n");
	for (i = 0; i < g1.Vertices.size; i++) {
		for (j = 0; j < g1.Vertices.size; j++) {
			printf("%5d  ", g1.edge[i][j]);
		}
		printf("\n");
	}
	printf("***********************\n");
	printf("深度优先遍历序列为:\n");
	int count=DepthFirstSearch(g1,Visit);
	printf("连通分量的个数为:%d\n", count);
	system("pause");
}

五、运行结果：

如图所示：

要求该图中连通分量个数，该图可以简化为两个节点之间的连线（整数对 p , q ）

quick-find算法(O(N^2))，也是一般人最容易想到的算法

1. 用一个id数组来确定两个节点之间是否存在于相同的连通分量中 ， 保证同一个连通分量的所有节点的在id数组中的值全部相同（id数组记录的是p点所在连通分量的标号）

2. 先用 find函数 判断p , q是否在同一个相同分量，如果是，则不做任何操作，如果不在，将p , q所在的连通分量用  union 函数连接起来

int count = id.length;        //记录连通分量个数


public int find(int p)
{
    return id[p];
}


public void union (int p,int q)  //将p，q归并到相同的分量
{
    int pID = find(p);
    int qID = find(q);

    if(pID == qID)   //如果已经是在同一个分量，不做任何操作
         return;  
    for(int i = 0; i < id.length; i++)
        if(id[i] == pID)
            id[i] = qID;
    
    count--;    //分量个数减1    
}

但是上述算法必须每次扫描原来的id数组，再改变 p , q的对应id值，这样太过于复杂，所以有了下面算法

quick-union算法（O(N^2)）

为了提高union函数的速度，可以在实现find方法时，从给定的节点开始，由它的链接得到另一个节点(id数组不再是记录p点所在的连通分量标号，而是记录p点的上一个节点，类似于链表)，一直下去，直到找到根节点，将两个根节点直接连接在一起即可

int count = id.length;             //  记录连通分量个数


for(int i = 0; i < id.length; i++)      //  初始化所有节点的根节点为自身
{
    id[i] = i;
}


int find(int p)              //  类似链表，直到找到根节点为止
{
    while(p != id[p])
        p = id[p];
    return p;
}


void union(int p, int q)
{
    int pRoot = find(p);
    int qRoot = find(q);
    if(pRoot == qRoot)
        return ;
    id[pRoot] = qRoot;       //  将两个根节点连接
    count--;                 //  连通分量个数减1
}

quick-union算法看上去比quick-find算法快，因为它不需要对每个输入都遍历id数组，在最好的情况下，find()只需要访问一次数组即可找到根节点，但是最坏情况下需要访问2*N + 1次，所以需要的复杂度也是O(N^2) , 但是比quick-find要快

union-find(加权quick-union算法  , O(n * logn) , 目前较好的算法)

在quick-union算法中，较坏情况下是在一条较长的链中寻找根节点，所以在该算法中，手动将较小的链加到较大的链中，而不是像上面算法一样无脑的连接起来，以达到平衡每个树的节点个数尽可能相等

public class WeightedQuickUnionUF
{
    private int [] id;          //  记录该节点的根节点信息
    private int [] sz;          //  记录各个节点所对应的分量大小，即每条链的节点数
    private int count;

    public WeightedQuickUnionUF(int N)
	{
	    count = N;
	    id = new int [N];
	    for(int i = 0; i < N; i++)       //  初始化节点的根节点为自身
	        id[i] = i;
	    for(int i = 0; i < N; i++)       //  初始化每个链的节点个数为1
	        sz[i] = 1;
	}

    public int find(int p)
	{
		while(p != id[p])
			p = id[p];
		return p;
	}
		
	public void union(int p,int q)
	{
		int i = find(p);
		int j = find(q);
		if(i == j)
			return;
		if(sz[i] < sz[j])
		{
			id[i] = j;            //  将较小的链连接到较大的链上(更新小链的根节点的id值为
                                  //  较大链的根节点)
			sz[j] += sz[i];       //  更新链的长度，即节点个数
		}
		else
		{
			id[j] = i;
			sz[i] += sz[j];
		}
			
		count--;                  //  连通分量个数减1
			
	}
}

带路径压缩的加权quick-union算法（O(n*logn) , 目前最优的算法）

基于上述加权quick-union算法 ， 在理想情况下，我们希望每个节点都直接连接到它的根节点，但是又不像quick-find算法那样通过修改大量连接达到该目的，所以只需在find()方法中添加一个循环，让在路径上遇到的所有节点的id值变成所在链的根节点，这样得到的一棵树是一颗几乎完全扁平化的树

public int find(int p)
{
    int root = id[p];
    while(root != id[root])
        root = id[root];

    while(p != root)
    {
        int q = id[p];
        id[p] = root;
        p = q;
    }
        
    return root;
}

\quad 求图连通分量个数方法很多，这里主要讨论两种方法，一种是通过dfs、bfs等遍历手段求得，一种是并查集。

一、利用dfs求图连通分量

\quad 算法流程：

• 初始化连通分量个数为ccount=0；
• 从图中任一顶点开始进行dfs，通过该顶点遍历到的所有顶点属于同一连通分量，这些遍历到的顶点做好标记，表示已经被访问。ccount+=1；
• 从未访问过的顶点中取出一个顶点重复第二步，遍历完后ccount+=1；
• 重复上述过程，直到所有顶点均被标记；
• 输出ccount，ccount即为图连通分量个数。
  \quad 我们还可以通过一个变量id记录每个顶点具体属于某个连通分量。在具体实现中，我实现了三个方法——1、查询图中连通分量个数；2、查询任意两点是否连通，即是否属于同一个连通分量；3、具体打印出每个连通分量包含的顶点情况。
  \quad 首先，我们先建立一个图，用邻接表存放与每个顶点相邻的顶点。

#include<bits/stdc++.h>
using namespace std;

class graph {
public:
    vector<vector<int> > g;  // 图的领接表
    graph(int V, bool directed=false){
        this->V=V;  // 需传入图的顶点数
        this->directed = directed;  // 是否为有向图
        // g初始化为V个空的vector, 表示每一个g[i]都为空, 即没有任和边
        g = vector<vector<int> >(V, vector<int>());
    }
    ~graph(){};
    void addEdge(int v, int w);  // 顶点v与w有一条边
    int getV() { return V; }  // 取出顶点数
    int getE() { return E; }  // 取出边数

private:
    int V = 0;  // 顶点数
    int E = 0;  // 边数
    bool directed;  // 是否为有向图

};

void graph::addEdge(int v, int w) {
    assert(v>=0 && v<V);
    assert(w>=0 && w<V);
    g[v].push_back(w);
    if(!directed) g[w].push_back(v);  // 若不是有向图则w与v也有一条边
    E++;
}

\quad 接下来具体实现求取图连通分量的类Component。

class Component {
private:
    graph &G;  // 图的引用
    bool *visited;  // 记录节点是否被访问
    int ccount;  // 连通分量个数
    int *id;  // 给每个顶点所属的连通分量标号

    void dfs(int v);  // 从顶点v开始进行dfs
public:
    Component(graph &graph): G(graph)
    {
        visited = new bool[G.getV()];
        id = new int[G.getV()];
        ccount = 0;
        for (int i = 0; i < G.getV(); ++i) {
            visited[i] = false;
            id[i] = -1;
        }

        for (int i = 0; i < G.getV(); ++i) {
            if(!visited[i])
            {
                dfs(i);
                ccount++;
            }
        }
    }

    ~Component(){
        delete[] visited;
        delete[] id;
    }

    // 返回连通分量个数
    int count()
    {
        return ccount;
    }

    // 查询v和w是否连通
    bool isConnected(int v, int w)
    {
        return id[v]==id[w];
    }

    // 以文字形式显示图的连通分量具体情况
    void verbose()
    {
        for (int i = 1; i <= ccount; ++i) {
            cout << "Component " << i << " Vertex:";
            for (int j = 0; j < G.getV(); ++j) {
                if(id[j] == i-1) cout << " " << j;
            }
            cout << endl;
        }
    }
};

void Component::dfs(int v) {
    visited[v] = true;
    id[v] = ccount;
    // 遍历图G的顶点v的领接表
    for (int i = 0; i < G.g[v].size(); ++i) {
        if(!visited[G.g[v][i]])
            dfs(G.g[v][i]);
    }
}

\quad 在主函数中建立一个6个顶点，4条边的图。

int main()
{
    graph G(6, false); // 建立顶点个数为6的图
    G.addEdge(0, 1);
    G.addEdge(0, 2);
    G.addEdge(1, 2);
    G.addEdge(3, 4);

    Component component(G);
    cout << "连通分量个数：" << component.count() << endl;  // 打印连通分量个数
    cout << "1，2点是否连通：" << component.isConnected(1, 2) << endl;  // 判断两点是否连通
    cout << "1，3点是否连通：" <<component.isConnected(1, 3) << endl;
    component.verbose();  // 显示具体信息
    return 0;
}

\quad 运行结果如下：

二、并查集求连通分量个数

\quad 并查集操作分为两个，并Union和查Find。Union可以将两个顶点合在一个集合里面，拥有相同的“祖先”。查可以获得当前顶点所在集合的“祖先”。若两个顶点a，b在一个集合里，则Find(a)=Find(b)。因为这个在刷一些oj上刷题时经常用到，这里就直接给出常见写法：

//
// Created by 程勇 on 2019/3/7.
//

/*
 * 并查集可用来求图连通分类和最小生成树
 */
#include<bits/stdc++.h>
using namespace std;

const int maxn = 1e+6+10;
int parent[maxn];

int Find(int p)
{
    while(p != parent[p])
    {
        p = parent[p];
    }
    return p;
}

void Union(int p, int q)
{
    if(Find(p) != Find(q))
        parent[p] = q;
}

int main()
{
    int n, m;  // 顶点数和边数
    cin >> n >> m;
    for (int i = 1; i <= n; ++i) {
        parent[i] = i;  // 初始化每个顶点指向自己
    }
    for (int j = 0; j < m; ++j) {
        int v, w;
        cin >> v >> w;  // 依次读入边
        v = Find(v);
        w = Find(w);
        Union(v, w);
    }

    int res = 0;
    for (int i = 1; i <= n; ++i) {
        if(parent[i] == i) res++;
    }

    cout << "连通分量数：" << res-1 << endl;
    system("pause");
    return 0;
}

\quad 输入之前那个图信息，运行结果：