判断无向图是否联通

对于一个无向图来说，判断其是否联通的思路并不复杂。从任意点出发，利用深度优先搜索（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