三种方法求图中连通分量的个数(BFS、DFS、并查集)

这篇具有很好参考价值的文章主要介绍了三种方法求图中连通分量的个数(BFS、DFS、并查集)。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

1. 连通分量是什么

无向图G的极大连通子图称为G的连通分量( Connected Component)。任何连通图的连通分量只有一个,即是其自身,非连通的无向图有多个连通分量。

2. 案例

2.1.图极其数据结构初始化

连通分量个数怎么求,图,深度优先,宽度优先,算法

2.2.求连通分量的方法

从每个顶点出发,判断是否有连通分量
BFS[BFS](https://blog.csdn.net/qq_44423388/article/details/127591933?spm=1001.2014.3001.5501)
DFS[DFS](https://blog.csdn.net/qq_44423388/article/details/127583096?spm=1001.2014.3001.5501)
并查集(本篇主讲,实现步骤见下)

连通分量个数怎么求,图,深度优先,宽度优先,算法
连通分量个数怎么求,图,深度优先,宽度优先,算法

2.3 具体实现

/*
测试用例:
1 2
1 4
2 4
*/


#include <vector>
#include <iostream>
#include <queue>
#include <unordered_map>

using namespace std;

/*
如果节点是相互连通的(从一个节点可以到达另一个节点),那么他们在同一棵树里,或者说在同一个集合里,或者说他们的祖先是相同的。
*/
//并查集的数据结构
class UnionFind {

private:
    // 记录每一个节点的父节点father<当前节点下标,父节点下标>
    unordered_map<int, int> father;
    // 记录集合数量
    int num_of_sets = 0;

public:

    //找节点x的父节点
    int find(int x) 
    {
        int root = x;

        while (father[root] != -1) 
        {
            root = father[root];
        }
        //优化的点:如果我们树很深,那么每次查询的效率都会非常低。这一步把树的深度固定为二。
        while (x != root) 
        {
            int original_father = father[x];
            father[x] = root;
            x = original_father;
        }

        return root;
    }

    bool is_connected(int x, int y) 
    {
        return find(x) == find(y);
    }

    //将连通的两个节点合并为同一个祖先,同时并查集的数目--
    void merge(int x, int y) 
    {
        int root_x = find(x);
        int root_y = find(y);

        if (root_x != root_y)
        {
            father[root_y] = root_x;
            num_of_sets--;
        }
    }
    //将新节点添加到并查集中
    void add(int x) 
    {
        if (!father.count(x))
        {
            father[x] = -1;
            num_of_sets++;
        }
    }
    //返回并查集个数
    int get_num_of_sets()
    {
        auto it = father.begin();
        while (it != father.end())
        {
            cout << it->first<<" ->"<<it->second << endl;
            it++;
        }
        
        return num_of_sets;
    }
};

class Connectedcomponent:protected UnionFind
{
private:
    int vertice = 0;//顶点数
    int edge = 0;//边数
    vector<vector<int>> e;
    //因为dfs和bfs都会对其进行改变,所有设置两个book
    vector<bool> book;//判断顶点j是否扩展过
    vector<bool> book1;//判断顶点j是否扩展过
    queue<int> qu;

    //DFS求连通分量个数
    void DFS_Alg(int current, int sum)//current当前所在的节点编号
    {
        sum++;
        if (sum == vertice)//所有的节点均已被访问
        {
            cout << current << endl;
            return;
        }
        else
        {
            cout << current << " ->";
        }
        for (int k = 1; k <= vertice; k++)
        {
            if (e[current][k] != 0 && book[k] == 0)
            {
                book[k] = 1;
                DFS_Alg(k, sum);
            }
        }
    }
    
public:
    Connectedcomponent(int x, int y) :vertice(x), edge(y)
    {
        //图的初始化从下标1开始
        e.resize(vertice + 1);//初始化二维数组的行
        for (int i = 0; i <= vertice; i++)
        {
            e[i].resize(vertice + 1,0);//初始化二维数组的列
        }
        
        book.resize(vertice + 1);
        book1.resize(vertice + 1);
    }
    //图的初始化
    void Init_tu()
    {
        for (int i = 0; i <= vertice; i++)
        {
            for (int j = 0; j <= vertice; j++)
            {
                if (i == 0 || j == 0)
                {
                    e[i][j] = 0;
                }
                if (i == j)
                {
                    e[i][j] = 0;
                }
                else
                {
                    e[i][j] = INT_MAX;
                }
            }
        }
    }
    //读入图的边,并且根据边的信息初始化数组dis,数组book
    void GetEdgeInfo()
    {
        cout << "输入边的信息(节点1,节点2):" << endl;
        int e1 = 0, e2 = 0, weigth = 0;
        for (int i = 1; i <= edge; i++)//无向图
        {
            cin >> e1 >> e2;
            e[e1][e2] = 1;
            e[e2][e1] = 1;
        }        
    }

    //打印
    void Print()
    {
        for (int i = 1; i <= vertice; i++)
        {
            for (int j = 1; j <= vertice; j++)
            {
                cout << e[i][j] << "    ";
            }
            cout << endl;
        }
        cout << endl;
    }
    
    int DFS_Num()
    {
        int num = 0;
        for (int i = 1; i <= vertice; i++)
        {
            if (book[i] == false)
            {
                DFS_Alg(i,0);
                cout <<"end" <<endl;
                num++;
            }               
        }

        return num;
    }
    //BFS求连通分量个数
    int BFS_Num()
    {     
        int num = 0;
        for (int i = 1; i <= vertice; i++)//遍历每个节点,查看是否从该节点出发是否有连通分量
        {
            if (book1[i] == false)
            {
                qu.push(i);
                while (!qu.empty())
                {
                    int v = qu.front();
                    qu.pop();
                    book1[v] = true;
                    cout << v << "->";
                    for (int i = 1; i <= vertice; i++)//循坏找节点v的相邻节点
                    {
                        if (e[v][i] != 0 && book1[i] == false)
                        {
                            qu.push(i);
                            book1[i] = true;
                        }
                    }
                }
                num++;
            }            
            
            cout << "end" << endl;
        }
        return num;       

    }
    //并查集求连通分量的个数
    /*
    每个节点会记录它的父节点。
    */
    int UnionFindSet()
    {
        UnionFind uf;
        for (int i = 1; i <= vertice; i++)
        {
            uf.add(i);
            for (int j = 1; j < i; j++)
            {
                if (e[i][j] == 1)
                {
                    uf.merge(i, j);
                }
            }
        }

        return uf.get_num_of_sets();
    }
};

int main()
{
    int num1 = 0, num2 = 0,num3 = 0;
    Connectedcomponent Conn(5, 3);
    Conn.GetEdgeInfo();

    cout << "初始信息:" << endl;
    Conn.Print();
    
    cout << "DFS:::" << endl;
    num1 = Conn.DFS_Num();
    cout << "BFS:::" << endl;
    num2 = Conn.BFS_Num();


    cout << "Union Find Set:::" << endl;
    num3 = Conn.UnionFindSet();
    cout << num1 << "  " << num2 <<"   "<<num3<< endl;

    return 0;
}

连通分量个数怎么求,图,深度优先,宽度优先,算法文章来源地址https://www.toymoban.com/news/detail-554345.html

到了这里,关于三种方法求图中连通分量的个数(BFS、DFS、并查集)的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 图论——强连通分量详解!

    本篇主要内容: 强连通分量等概念 Tarjan算法的过程与实现 首先我们要明白上面是 连通 。 在一张图中 任意 两个点能 互相 到达。(举个例子) 所以我们称上面的这个图是一个 连通图 !  接着我们在来理解什么是 强连通 。 若一张 有向图 的节点两两互相可达,则称这张图

    2024年02月07日
    浏览(37)
  • 有向图的强连通分量

    对于一个有向图,连通分量:对于分量中任意两点u,v,必然可以从u走到v,且从v走到u. 强连通分量:极大连通分量。 求出强连通分量后,可以通过将强连通分量缩点的方式,将有向图转化成有向无环图。 求强连通分量的方法:tarjan O(n+m),时间复杂度是线性的 1 . 采用dfs来遍历整

    2024年02月10日
    浏览(39)
  • 图的基本概念辨析,包括连通图、极大连通子图、连通分量、强连通图、极大强连通子图等

    概念(1-4)都是针对无向图的   图中从一个顶点到达另一顶点,若存在至少一条路径,则称这两个顶点是连通着的。例如图 1 中,虽然 V1 和 V3 没有直接关联,但从 V1 到 V3 存在两条路径,分别是 V1-›V2-›V3 和 V1-›V4-›V3,因此称 V1 和 V3 之间是连通的。 图 1 顶点之间的连

    2024年02月15日
    浏览(59)
  • 有向图的强连通分量算法

    有向图的强连通分量算法 强连通分量定义 在有向图中,某个子集中的顶点可以直接或者间接互相可达,那么这个子集就是此有向图的一个强连通分量,值得注意的是,一旦某个节点划分为特定的强连通分量后,此顶点不能在其它子树中重复使用,隐含了图的遍历过程和极大

    2024年02月06日
    浏览(84)
  • 第三章 图论 No.9有向图的强连通与半连通分量

    连通分量是无向图的概念,yxc说错了,不要被误导 强连通分量:在一个有向图中,对于分量中的任意两点u,v,一定能从u走到v,且能从v走到u。强连通分量是一些点的集合,若加入其他点,强连通分量中的任意两点就不能互相递达 半连通分量:在一个有向图中,对于分量中

    2024年02月13日
    浏览(50)
  • 一图搞清楚(非)(强)连通图中的极大(小)(强)连通子图

    在学习图的过程中,常常搞不清楚下面这些概念: 连通图、非连通图、强连通图、非强连通图、极大连通子图与连通分量、极大强连通子图与强连通分量、极小连通子图与生成树、极小强连通子图(后面得知根本就没有这个概念)...... 现在决定用一张图(放大查看)对他们

    2024年02月04日
    浏览(42)
  • 团体程序设计天梯赛 L2-013 红色警报(连通分量)

    分数 25 战争中保持各个城市间的连通性非常重要。本题要求你编写一个报警程序,当失去一个城市导致国家被分裂为多个无法连通的区域时,就发出红色警报。注意:若该国本来就不完全连通,是分裂的k个区域,而失去一个城市并不改变其他城市之间的连通性,则不要发出

    2024年03月13日
    浏览(52)
  • 并查集模板的应用:连通块

    837. 连通块中点的数量 给定一个包含 nn 个点(编号为 1∼n1∼n)的 无向图 , 初始时图中没有边 。 现在要进行 mm 个操作,操作共有三种: C a b ,在点 aa 和点 bb 之间连一条边,aa 和 bb 可能相等; Q1 a b ,询问点 aa 和点 bb 是否在同一个连通块中,aa 和 bb 可能相

    2024年02月14日
    浏览(45)
  • (3)【全局路径规划】图搜索的路径探索方法--DFS\BFS\DFS-ID、贪心算法、Dijkstra和A*、JPS、.hybird A*、

    提示:这里可以添加系列文章的所有文章的目录,目录需要自己手动添加 TODO:写完再整理

    2024年02月15日
    浏览(43)
  • Acwing847 图中点的层次(bfs)

    这道题用的是bfs,一开始用了dfs搜出了答案为4 给定一个 n个点 m 条边的有向图,图中可能存在重边和自环。 所有边的长度都是 1,点的编号为 1∼n。 请你求出 1 号点到 n 号点的最短距离,如果从 1 号点无法走到 n 号点,输出 −1。 输入格式 第一行包含两个整数 

    2024年02月02日
    浏览(42)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包