用python实现无向图的连通性判断

import numpy as np
import networkx as nx
import matplotlib.pyplot as plt
from random import random,choice
'''
算法描述：
在用Fleury方法寻找欧拉回路的时候需要判断一条边删除之后余下的部分是否为连通图
这个程序用来判断一个图形是否为连通图
1.如果邻接矩阵中有零行，则可直接判断此图不联通
2.如果不联通就收缩一条边，将两个端点合并
3.持续进行2操作，如果最后所有的点都能收缩到一起，说明连通，如果不能收缩到一起，说明不联通

程序会按照你的输入生成一个随机的图形，并打印判断结果和画出图像

算法来自《关于Fleury算法的一点注记》（吕义忠）
'''

n=int(input('input node number: ')) #输入节点数目
m=int(input('input edge number: ')) #输入边数

while m>((n-1)*n/2):
print ('too many edges,input again')
n=int(input('input node number: ')) #输入节点数目
m=int(input('input edge number: ')) #输入边数

G = nx.Graph() #实例化nx

for i in range(n): #添加点
G.add_node(i)

counter=0

while counter < m: #添加9条边
a=choice(range(n))
b=choice(range(n))
if ((a,b) not in G.edges()) and (a!=b) and ((b,a) not in G.edges()):
G.add_edge(a,b)
counter+=1



def drawit(): #画图方法
pos=nx.spring_layout(G) #散点的排列模式为spring模式
nx.draw(G,pos)
plt.show()


def xor(a,b): #定义一个向量的亦或方法，返回异或运算后的向量
la=len(a)
lb=len(b)
c=zip(a,b)
L=[]
try:
for ai,bi in c:
if ai==bi:
L.append(0)
else:
L.append(1)
return L
except Exception as e:
print(e)
return

M=np.zeros((n,m)) #创建邻接矩阵的雏形
eds=G.edges()
eds=dict(map(lambda i,j:[i,j],list(range(m)),eds)) #将边编号，用字典表示

def connA(): #建立邻接矩阵
for i in range(m):
for j in range(n):
if (eds[i][0]==j) or (eds[i][1])==j:
M[j][i]=1

def inspectzeros(): #检查是否有零行
for i in range(len(M)):
if sum(M[i])==0:
flag=False
return i
return

def delline(Flag): #删除一行
M1=M[:Flag]
M2=M[Flag+1:]
Mc=np.vstack((M1,M2))
return Mc

if __name__=='__main__': #主函数
try:

connA()
Flag=inspectzeros()
#print(M)
if Flag is not None:
#delline(Flag)
print('it has at least two parts')
else:
while len(M)>1:
for j in range(m):
if M[0][j]!=0:
for i in range (1,n):
if M[i][j]!=0:
#print (i,j)
M[0]=xor(M[0],M[i])

M=delline(i)
break
break
if sum(M[0])==0 and len(M)>1:
print ('it has at least two parts')
break
else:
print('it is connected')
drawit()
except Exception as e:
print(e)