Python求解：利用邻接矩阵判断有向图的连通性WoW，让我们先来看看我们要解决的小问题：
——将任意一个有向图g在行列输入中以图形g输出，利用可到达矩阵判定图形g是否连接：
(PS )确定图的连接性至少有三种方法： [1] .并行检查组[2].DFS [3].BFS。 有关其它解决方案的详细信息，请参阅https://blog.csdn.net/weixin _ 44646116/article/deteticle
当然，今天我们主要从数学角度探讨如何利用邻接矩阵来判断图的连通性：
首先，需要一点数学知识。 http://www.Sina.com/(adjacency matrix )是表示顶点之间相邻关系的矩阵。 设g=(v，e )为图表，其中V={v1，v2，…，vn}
v和e的集合。 其中，v是顶点，e是边。 因此，用一维排列收纳图中的所有顶点数据；
二维数组存储顶点之间关系(边或圆弧)的数据，称为相邻矩阵。 邻接矩阵分为有向图邻接矩阵和有向图邻接矩阵；
3358 www.Sina.com/http://www.Sina.com/http://www.Sina.com /
用邻接矩阵表示顶点间的邻接关系
用一个顺序表存储顶点信息
（一）邻接矩阵
在图的邻接
33558 www.Sina.com/(reachability matrix )是指用矩阵形式记述了有向图的各节点之间经过一定长度的路径能够到达的程度。 可达矩阵的计算方法利用布尔矩阵的运算性质。
中的布尔矩阵指的是方阵，矩阵中的第I行对应于与第I列相同的元素。
矩阵
表示法中：
#用于确定有向图连接性的编程要部署importnumpyasNP#numpy模块，必须先安装import networkx as nx#部署numpy模块，然后再进行安装它用于绘制图表import matplotlib.pyplot as plt#引入matplotlilib.plot#。同样绘制了有向图importpylab-------------------------- for_inrange(n ) :a.append(list ) map(int，input ().RS trip (.split ) ) ) for i in range(n ) 333330 a (n ) (在这里写代码很恶心) y=xx.t-----------------------)。 n ) :#可计算矩阵-这里是上图中所示的可计算矩阵的数学解法value _1=NP.mat mul (参见value _ 1，x ) sum _1=sum _1value _1sum _ 2 sum_2矩阵中所有更大的剩余元素(所有0 )变为Falseprint (这个有向图的可到达矩阵是() print ) reachability_matrix.astype(int ) )
lity_matrix+reachability_matrix.Tfor i in range(1,n):同上，其实应该编个函数 value_2=np.matmul(value_2, y) sum_3=sum_3+value_2sum_4 = sum_3 + np.identity(n)reachability_matrix_1=sum_4>0.5#---------------------------------------------------------------------#给出判断结果if ((reachability_matrix.astype(int)==np.ones((n,n)).astype(int)).all()): print("此有向线图G为强连通图或其为无向连通图") # print(np.ones((n,n)).astype(int))默认生成全1矩阵其中元素为float型，要多加注意elif ((final.astype(int)==np.ones((n,n)).astype(int)).all()): print("此有向线图G是单向连通图")elif ((reachability_matrix_1.astype(int)==np.ones((n,n)).astype(int)).all()): print("此有向线图G是弱连通图")else: print("此有向图不连通")#---------------------------------------------------------------------#下面展示图形化输出有向图GG = nx.DiGraph()for i in range(0, n):#标记出标签 G.add_node(i, desc='v'+str(i))#依次为标签命名for p in range(0,n):#双重循环扫描并输出所有元素为1的位置 for q in range(0,n): if(x[p,q]==1): G.add_edges_from([(p, q)],weight='1')edge_labels=dict([((u,v,),d['weight']) for u,v,d in G.edges(data=True)])edge_colors = ['black']pos=nx.spring_layout(G)#按pos标出结点node_labels = nx.get_node_attributes(G, 'desc')nx.draw_networkx_labels(G, pos, labels=node_labels)#画出标签nx.draw_networkx_edge_labels(G,pos,edge_labels=edge_labels)nx.draw(G,pos, node_size=1500,edge_color=edge_colors,edge_cmap=plt.cm.Reds)#有向图属性plt.title('Directed Graph', fontsize=10)#有向图名称pylab.show() #嗯嗯嗯，我知道我代码风格不好，别骂了别骂了给出相应代码实现结果：
注意相关输入格式：
[1].第一行输入矩阵的阶数
[2].后面将相关数据依次按顺序输入矩阵
生成的图形化有向图G(Directed Graph)：
最终页面展示：
针对编写中容易出现错误的部分，给出相关链接：
[1].如何安装相应模块： https://blog.csdn.net/qq_43201403/article/details/102336114
[2].关于numpy模块使用的相关文档： https://www.cnblogs.com/pythonfl/p/12257698.html
[3].networkx模块使用的相关文档： 1.https://blog.csdn.net/your_answer/article/details/79189660 2.https://zhuanlan.zhihu.com/p/40852672
[4].利用netwokx绘图: https://blog.csdn.net/qq_32284189/article/details/80134768?utm_medium=distribute.pc_relevant.none-task-blog-2%7Edefault%7EBlogCommendFromMachineLearnPai2%7Edefault-2.control&depth_1-utm_source=distribute.pc_relevant.none-task-blog-2%7Edefault%7EBlogCommendFromMachineLearnPai2%7Edefault-2.control
[5].Python中 all() 与 any() 的区别：https://blog.csdn.net/cython22/article/details/78829288?utm_medium=distribute.pc_relevant.none-task-blog-2%7Edefault%7EBlogCommendFromBaidu%7Edefault-5.control&depth_1-utm_source=distribute.pc_relevant.none-task-blog-2%7Edefault%7EBlogCommendFromBaidu%7Edefault-5.control
最后，如果有相应错误，还请在评论区内多多指出。（代码太渣，轻喷）
来都来了，点个赞再走嘛QWQ