美文网首页
判断无向图是否联通

判断无向图是否联通

作者: 坐看云起时zym | 来源:发表于2019-04-26 21:16 被阅读0次

对于一个无向图来说,判断其是否联通的思路并不复杂。从任意点出发,利用深度优先搜索(DFS),若是能遍历所有的点,则该图联通;若只能遍历部分点,则该图不联通。

程序说明:
Input:无向图的邻接矩阵
visited:用来记录某点是否被访问过,'1'代表访问过,'0'代表未访问过。

import numpy as np
class Graph(object):
    def __init__(self,G):
      self.G = G
      self.visited = [0] * len(G)
      
    def DF_S(self,v):
        self.visited[v]= 1
        #print("We are visiting node " + str(v)) 
        for i in range(len(self.G)):
            if self.G[v][i] == 1 and self.visited[i] == 0:
                self.DF_S(i)
                
    def link(self,i):
        self.visited[i] = 1
        for j in range(len(self.G)):
            if self.G[i][j] == 1 and self.visited[j] == 0:
                self.DF_S(j)
                
        if np.sum(self.visited) == len(self.G):
            print("yes")
            return True
        else:
            return False

在这里,本文分别用一个联通无向图和一个不连通无向图进行测试:


unlinked_undirected_graph.png
G = [[0,0,1,0,0],[0,0,1,0,0],[1,1,0,1,0],[0,0,1,0,0],[0,0,0,0,0]]
G1 = Graph(G)
G1.link(0)
unlinked.png linked_undirected_graph.png
G = [[0,0,1,0,0],[0,0,1,0,0],[1,1,0,1,0],[0,1,1,0,1],[0,0,0,1,0]]
G2 = Graph(G)
G2.link(0)
linked.png

相关文章

  • 判断无向图是否联通

    对于一个无向图来说,判断其是否联通的思路并不复杂。从任意点出发,利用深度优先搜索(DFS),若是能遍历所有的点,则...

  • 数据结构之图的基本操作

    一、判断图G是否存在边 或 (x, y) 1.1 如何判断无向图是否存在边 (C, D) ? 1.1...

  • 如何判断无向图是否连通

    任取两个顶点,我们都能找到一条路径从一点到达另一个点,这个图就是连通的 1.DFS法: 把一个图的所有顶点都进行一...

  • 几个概念:有向图、无向图、加权图、简单图、联通、联通分量、生成树、强连通分量、强联通图图的存储:邻接矩阵(二维、一...

  • 判断无向图和有向图是否有环

    无向图 方法1(数学方法): 图的顶点数为n,边数为m,若n>=m+1,则无环;否则有环。方法2:使用并查集进行判...

  • 如何判断无向图是否无环

    当只有一棵树的时候,节点数==边数+1时肯定无环,但是如果有多个树的时候。就要对该树单独计算节点与边数了。 使用交...

  • 图的相关算法

    深度优先搜索非递归形式 DFS 深度优先搜索非递归形式 广度优先搜索 BFS 判断无向图是否是树 判断有向图中两...

  • MST——最小生成树系列

    什么是树? 树是一个联通的,无环的无向图,称一个不可能联通的无向图为森林;如果一个图是树,则其边数等于点数减一,两...

  • 10.图的深度优先遍历、联通分量与寻路

    图的深度优先遍历、联通分量与寻路 点击这里,前提知晓... 深度优先遍历对有向图和无向图都可以使用 一、图的深度优...

  • 无/有向图判环

    无向图寻找环的方法:(一) DFSDFS搜索图,图中的边只可能是树边或反向边,一旦发现反向边,则表明存在环。该算法...

网友评论

      本文标题:判断无向图是否联通

      本文链接:https://www.haomeiwen.com/subject/rhxcnqtx.html