Python小白的数学建模课-图论的基本概念
. w* G1 z9 k( Y3 r2 X1 g5 L' G8 d2 l/ z( n5 A. Z
- 图论中所说的图,不是图形图像或地图,而是指由顶点和边所构成的图形结构。
- 图论不仅与拓扑学、计算机数据结构和算法密切相关,而且正在成为机器学习的关键技术。
- 本系列结合数学建模的应用需求,来介绍 NetworkX 图论与复杂网络工具包的基本功能和典型算法。3 o; o" g0 N6 e
. H6 g/ M0 s- u1. 图论1.1 图论是什么
0 v0 x1 X8 z& x图论〔Graph Theory〕以图为研究对象,是离散数学的重要内容。图论不仅与拓扑学、计算机数据结构和算法密切相关,而且正在成为机器学习的关键技术。
& b6 _8 z: N0 _) P" @; g- }, J" X' b2 R+ @7 z0 r9 C- i# d
图论中所说的图,不是指图形图像(image)或地图(map),而是指由顶点(vertex)和连接顶点的边(edge)所构成的关系结构。 g# k+ I& w) o9 g5 d+ }
+ [ J) L" T4 ? \/ X$ l% J& F/ L
图提供了一种处理关系和交互等抽象概念的更好的方法,它还提供了直观的视觉方式来思考这些概念。
) V" d0 }) [2 N; @3 @! ]* a$ D3 T+ b0 V) {9 u+ m' J
1.2 NetworkX 工具包5 v" v9 c8 T$ x9 {9 V
NetworkX 是基于 Python 语言的图论与复杂网络工具包,用于创建、操作和研究复杂网络的结构、动力学和功能。
: I- N2 t( a6 ?( A
+ f( X9 {7 P( e; Z; L6 L# }NetworkX 可以以标准和非标准的数据格式描述图与网络,生成图与网络,分析网络结构,构建网络模型,设计网络算法,绘制网络图形。
" |) a0 T6 W7 o) Z! J9 Z1 y/ @3 M: M7 u' [! I! P$ R. G
NetworkX 提供了图形的类、对象、图形生成器、网络生成器、绘图工具,内置了常用的图论和网络分析算法,可以进行图和网络的建模、分析和仿真。
5 u' ?, [' C# |, e1 `
, g9 _! m6 K8 b6 A% ]# xNetworkX 的功能非常强大和庞杂,所涉及内容远远、远远地超出了数学建模的范围,甚至于很难进行系统的概括。本系列结合数学建模的应用需求,来介绍 NetworkX 图论与复杂网络工具包的基本功能和典型算法。
0 b- A8 O' e, R+ o& ?
- S6 x9 ~+ ?4 @! ~. K4 s
- ] J% N% R( G) C- C9 y- r; H2、图、顶点和边的创建与基本操作0 \4 d( \) k3 j% I% i
图由顶点和连接顶点的边构成,但与顶点的位置、边的曲直长短无关。 Networkx 支持创建简单无向图、有向图和多重图;内置许多标准的图论算法,节点可为任意数据;支持任意的边值维度,功能丰富,简单易用。 2.1 图的基本概念8 i9 b7 U2 d" Q% E
图(Graph):图是由若干顶点和连接顶点的边所构成关系结构。
1 j* I7 Q( x) Q5 U s顶点(Node):图中的点称为顶点,也称节点。2 T: v( m, K' }/ U
边(Edge):顶点之间的连线,称为边。
/ ?# X0 A6 N J( ~平行边(Parallel edge):起点相同、终点也相同的两条边称为平行边。/ w. J$ M" R5 ?( w5 e/ g
循环(Cycle):起点和终点重合的边称为循环。
# A8 [2 z* i* j6 a0 k i5 y有向图(Digraph):图中的每条边都带有方向,称为有向图。# {1 \: L9 h. ?' X- R# t8 D1 }1 ^
无向图(Undirected graph):图中的每条边都没有方向,称为无向图。
3 U, E" ^( ?4 P+ D赋权图(Weighted graph):图中的每条边都有一个或多个对应的参数,称为赋权图。该参数称为这条边的权,权可以用来表示两点间的距离、时间、费用。
" V& t6 I* ?% _# N度(Degree):与顶点相连的边的数量,称为该顶点的度。" U+ @! _; n& E+ G1 L2 m* S
c. ~4 g6 @' r) N3 M0 F3 T2.2 图、顶点和边的操作
0 b; O- Y C' c1 h( K/ G' WNetworkx很容易创建图、向图中添加顶点和边、从图中删除顶点和边,也可以查看、删除顶点和边的属性。" ?/ A# |. C; R6 E: ^
+ r; ^7 i- z' |- @; ?+ @' e
2.2.1 图的创建Graph() 类、DiGraph() 类、MultiGraph() 类和 MultiDiGraph() 类分别用来创建:无向图、有向图、多图和有向多图。定义和例程如下:
4 V' y& `, |4 b+ {9 E8 B7 ^& `
# T! ]+ t( ^) aclass Graph(incoming_graph_data=None, **attr)$ {5 I5 c3 S+ g: L& Z% i" Z
import networkx as nx # 导入 NetworkX 工具包/ f# q. w9 k8 o1 y1 \, d, |
0 [0 H# c1 z, W9 C5 `
# 创建 图
2 f5 f/ [8 F5 r) T; @2 SG1 = nx.Graph() # 创建:空的 无向图
, U' ~3 E. m8 c: U) _ TG2 = nx.DiGraph() #创建:空的 有向图. g9 J# |% O$ `7 y5 p4 _
G3 = nx.MultiGraph() #创建:空的 多图
; c8 {$ ^6 R8 U: y! V. t& C& HG4 = nx.MultiDiGraph() #创建:空的 有向多图
" H. X4 u# [7 H8 v6 x& O2 d* E+ j5 o. Z1 o' B
% @$ h9 a) R- N5 K+ F; W
2.2.2 顶点的添加、删除和查看
; X) C1 P! I( D- S+ e2 l图的每个顶点都有唯一的标签属性(label),可以用整数或字符类型表示,顶点还可以自定义任意属性。 顶点的常用操作:添加顶点,删除顶点,定义顶点属性,查看顶点和顶点属性。定义和例程如下: & h, n/ X7 n% j; l6 L: ?
Graph.add_node(node_for_adding, **attr)
5 \& n2 |( }( A3 A& [; YGraph.add_nodes_from(nodes_for_adding, **attr)
; \8 x5 j" H8 ~4 F' @* dGraph.remove_node(n)0 Q7 o; u" j' B/ W: y9 K' q2 U
Graph.remove_nodes_from(nodes)
/ |! b3 k% m( s& R
/ q5 E% z, D5 @7 k3 P9 A5 b( s: y8 h# 顶点(node)的操作
+ ?3 O) P4 A6 ?" \* k, d* \& w# 向图中添加顶点
+ u. R& F. G8 a* q$ {G1.add_node(1) # 向 G1 添加顶点 1# P4 x' y# u3 W; j
G1.add_node(1, name='n1', weight=1.0) # 添加顶点 1,定义 name, weight 属性
% f' q, v: ^$ T8 g" y+ h- JG1.add_node(2, date='May-16') # 添加顶点 2,定义 time 属性3 `# J' h P% R. l' n, w9 [
G1.add_nodes_from([3, 0, 6], dist=1) # 添加多个顶点,并定义属性
3 w/ p1 d7 @7 ?: A/ b3 @G1.add_nodes_from(range(10, 15)) # 向图 G1 添加顶点 10~14
" }' ~. w, Q5 q8 q, g0 R) t! D9 N% J Z. D
# 查看顶点和顶点属性+ p& f% m; W. I% H1 l2 P0 M6 ^. U8 R
print(G1.nodes()) # 查看顶点列表 A' H1 p9 K! s# Y. Z
# [1, 2, 3, 0, 6, 10, 11, 12, 13, 14]
! H6 h+ q' m/ B9 O9 d, vprint(G1._node) # 查看顶点属性
9 B6 s9 V& V" q; L# {1: {'name': 'n1', 'weight': 1.0}, 2: {'date': 'May-16'}, 3: {'dist': 1}, 0: {'dist': 1}, 6: {'dist': 1}, 10: {}, 11: {}, 12: {}, 13: {}, 14: {}}
! D" O5 B- J& p/ j- v, y% u
4 M9 J f& T/ B/ h# Y* v4 u5 W7 j# 从图中删除顶点& `4 u# E' ?% J% R- C
G1.remove_node(1) # 删除顶点2 q; F$ L# Z3 U F- J
G1.remove_nodes_from([1, 11, 13, 14]) # 通过顶点标签的 list 删除多个顶点
: r7 A4 Q1 ` A% Aprint(G1.nodes()) # 查看顶点! S3 a2 O' b3 h6 i1 ^
# [2, 3, 0, 6, 10, 12] # 顶点列表
2 V) ~0 G7 A$ [" r+ n2.2.3 边的添加、删除和查看边是两个顶点之间的连接,在 NetworkX 中 边是由对应顶点的名字的元组组成 e=(node1,node2)。边可以设置权重、关系等属性。 边的常用操作:添加边,删除边,定义边的属性,查看边和边的属性。向图中添加边时,如果边的顶点是图中不存在的,则自动向图中添加该顶点。 Graph.add_edge(u_of_edge, v_of_edge, **attr)
" J! A: ~5 j. N3 s$ t* i( FGraph.add_edges_from(ebunch_to_add, **attr)3 Y" Z. M: T/ }4 E. l* t
Graph.add_weighted_edges_from(ebunch_to_add, weight=‘weight’, **attr)
6 R, E6 B5 y8 t
7 x! x6 N) I6 L3 Y# 边(edge)的操作
5 A, H+ n- C" t5 Q, A# 向图中添加边( a9 N1 j- m% \# Z, H
G1.add_edge(1,5) # 向 G1 添加边,并自动添加图中没有的顶点
9 C# T) p" f% y' c% s# h. T# NG1.add_edge(0,10, weight=2.7) # 向 G1 添加边,并设置边的属性0 ?8 y+ c$ w, c' e# b
G1.add_edges_from([(1,2,{'weight':0}), (2,3,{'color':'blue'})]) # 向图中添加边,并设置属性) W3 U( E3 K4 `5 S# c' F6 F
G1.add_edges_from([(3,6),(1,2),(6,7),(5,10),(0,1)]) # 向图中添加多条边
0 J8 U, u9 `5 A$ n& q+ O+ wG1.add_weighted_edges_from([(1,2,3.6),[6,12,0.5]]) # 向图中添加多条赋权边: (node1,node2,weight)4 \& p0 N& d R' j6 e
print(G1.nodes()) # 查看顶点
1 v! U2 ~. ~0 A$ N5 V& ?# [2, 3, 0, 6, 10, 12, 1, 5, 7] # 自动添加了图中没有的顶点
. d: N5 H4 A4 G$ V7 ?
& r) l2 E# Y) l0 x# 从图中删除边
& B: Q7 e' x& SG1.remove_edge(0,1) # 从图中删除边 0-1' ?0 n4 R1 g! \
G1.remove_edges_from([(2,3),(1,5),(6,7)]) # 从图中删除多条边
* G9 X- k! l2 I6 V% P4 D4 `$ X/ s& C. l1 t. m- \+ _7 r+ t+ l
# 查看 边和边的属性
' d5 |: x9 D, `2 n+ X5 eprint(G1.edges) # 查看所有的边
* V0 n; F1 M! u# {[(2, 1), (3, 6), (0, 10), (6, 12), (10, 5)]- o+ P9 R' [4 x: ~9 q
print(G1.get_edge_data(1,2)) # 查看指定边的属性
" i2 A6 D) s# O# {'weight': 3.6}
6 K3 I* N* u$ @: r' sprint(G1[1][2]) # 查看指定边的属性
( X0 q0 |2 V, d2 W: [( z0 h# {'weight': 3.6}4 b% v: i0 ~7 m$ k
print(G1.edges(data=True)) # 查看所有边的属性+ Z1 Z0 T" a+ M& @' k/ K5 Y* h
# [(2, 1, {'weight': 3.6}), (3, 6, {}), (0, 10, {'weight': 2.7}), (6, 12, {'weight': 0.5}), (10, 5, {})]
7 Y; l' P/ O: L
) ^! _' c! `8 y+ N7 f7 m' m4 [2.2.4 查看图、顶点和边的信息/ M; b7 ~0 G1 t) y4 n( G# a: v8 ]
: U2 X R- ]3 P- Y& D# 查看图、顶点和边的信息
$ _- [$ k' V( h# zprint(G1.nodes) # 返回所有的顶点 [node1,...]8 p9 d" D% {0 T) o' ^1 A7 H
# [2, 3, 0, 6, 10, 12, 1, 5, 7]; ~; v. l z- G2 g
print(G1.edges) # 返回所有的边 [(node1,node2),...]
3 f! J, D0 l) d. t- G# [(2, 1), (3, 6), (0, 10), (6, 12), (10, 5)]: R+ d0 c+ T- z; w y3 n. K/ a
print(G1.degree) # 返回各顶点的度 [(node1,degree1),...]
9 |1 Z% B; E" \8 S# [(2, 1), (3, 1), (0, 1), (6, 2), (10, 2), (12, 1), (1, 1), (5, 1), (7, 0)]
6 p5 [- L8 u' B5 ?3 E5 r: R- L v" Y) @print(G1.number_of_nodes()) # 返回顶点的数量# B' w/ F7 B9 G, m/ {
# 9
& C: s: O8 f: G8 T. `print(G1.number_of_edges()) # 返回边的数量* k7 n2 Y7 k" N0 g
# 5' W+ r) b$ }2 G
print(G1[10]) # 返回与指定顶点相邻的所有顶点的属性) @: ]0 o: }9 I: A! v) _7 o
# {0: {'weight': 2.7}, 5: {}}
6 L" v) j7 Y N3 vprint(G1.adj[10]) # 返回与指定顶点相邻的所有顶点的属性- a- p* O9 K/ b* } x( e' ]
# {0: {'weight': 2.7}, 5: {}}
6 l! k- z8 K9 ?: M* v; ?, r" [+ Y( \print(G1[1][2]) # 返回指定边的属性
! Z X6 q! y4 F8 R" q7 |6 n9 B% A" Y# {'weight': 3.6}
1 U3 e9 v0 q! c0 R. sprint(G1.adj[1][2]) # 返回指定边的属性, A7 ]' n6 x% R, \
# {'weight': 3.6}
# v- S6 f7 j3 N+ }- Gprint(G1.degree(10)) # 返回指定顶点的度9 b/ x5 z* R5 L' ` S1 m
# 2% K1 s. R) J( l' ^( D2 j2 l" I
7 g6 ?& y% x5 y) T, [
print('nx.info:',nx.info(G1)) # 返回图的基本信息1 G! F5 J; d0 a
print('nx.degree:',nx.degree(G1)) # 返回图中各顶点的度' _$ @( r% a9 P; k4 w( w
print('nx.density:',nx.degree_histogram(G1)) # 返回图中度的分布
* q) T$ u" R: Q* tprint('nx.pagerank:',nx.pagerank(G1)) # 返回图中各顶点的频率分布
; N y2 Z- w( w' F, n9 D2 T
' A* G- I# Q+ s0 ?. w# c7 ]' d* f% _) M9 `7 p% `
- j0 m i7 a; a
; l2 z& {! J8 B* F$ T( }' E' |' \# ^0 D" V( L. v. w; Q
2.3 图的属性和方法图的方法
+ a6 d+ s$ Q+ Y2 {" u0 }0 C
9 |, X; @" ^& @/ B' N方法 说明
" r, r- r3 G8 K3 v4 x. d, T5 N! Q8 nG.has_node(n) 当图 G 中包括顶点 n 时返回 True
" z! }- |/ l9 a$ |0 f AG.has_edge(u, v) 当图 G 中包括边 (u,v) 时返回 True
. T9 [; t6 D W& B! a9 u8 _7 K3 B! ~G.number_of_nodes() 返回 图 G 中的顶点的数量9 b; V4 w. |4 w) e: `
G.number_of_edges() 返回 图 G 中的边的数量
3 W. ~+ I Y) Q% o/ \G.number_of_selfloops() 返回 图 G 中的自循环边的数量
3 N' P9 O$ l, C# q3 l& _; ZG.degree([nbunch, weight]) 返回 图 G 中的全部顶点或指定顶点的度
# O3 S9 n# O. A2 B+ n: x# EG.selfloop_edges([data, default]) 返回 图 G 中的全部的自循环边
l) ]8 _2 z Z, d* XG.subgraph([nodes]) 从图 G1中抽取顶点[nodes]及对应边构成的子图
2 t4 j/ ~' q& T( Z% u* i- yunion(G1,G2) 合并图 G1、G2
! z. Z9 l7 @/ F3 cnx.info(G) 返回图的基本信息
3 ?5 T7 L; z. ~) ^nx.degree(G) 返回图中各顶点的度7 N! f s1 _' Z) G6 A
nx.degree_histogram(G) 返回图中度的分布! s) b% r' K% Y" b
nx.pagerank(G) 返回图中各顶点的频率分布3 u& i# l7 f8 K5 k. ]
nx.add_star(G,[nodes],**attr) 向图 G 添加星形网络
$ L) `# B2 r3 Y( p" b, d( X, x( L* Ynx.add_path(G,[nodes],**attr) 向图 G 添加一条路径' S6 [8 S8 `4 t9 T# B
nx.add_cycle(G,[nodes],**attr) 向图 G 添加闭合路径9 o9 p! z7 `# g9 D) ?
9 l5 }* }' W. N3 T- [- I" I; } v; j. a" q6 [6 M0 P U
例程:
, z) o) o4 A* {6 }3 y' O9 ]" jG1.clear() # 清空图G1
1 d) \5 ~+ U6 @) _1 a8 _nx.add_star(G1, [1, 2, 3, 4, 5], weight=1) # 添加星形网络:以第一个顶点为中心, o8 s6 p8 H3 [" Y0 E" @6 R
# [(1, 2), (1, 3), (1, 4), (1, 5)] j/ W" @4 t2 r8 A8 S3 j, c
nx.add_path(G1, [5, 6, 8, 9, 10], weight=2) # 添加路径:顺序连接 n个节点的 n-1条边
1 Z# e& Q1 m' V3 F0 _# [(5, 6), (6, 8), (8, 9), (9, 10)]
7 S+ V" c2 n4 B5 ~4 a2 v2 Gnx.add_cycle(G1, [7, 8, 9, 10, 12], weight=3) # 添加闭合回路:循环连接 n个节点的 n 条边- H$ t) T5 N0 w. }; ?
# [(7, 8), (7, 12), (8, 9), (9, 10), (10, 12)]
$ Z" O- G/ h2 p! ~8 k' J/ kprint(G1.nodes) # 返回所有的顶点 [node1,...]
2 V9 G2 g* v$ @1 e3 u' ynx.draw_networkx(G1): n1 [9 U. B" _+ e. ~
plt.show()1 E$ J; G6 W# @& y+ s( C
, Y- |" j# e5 [8 J# ^! P
G2 = G1.subgraph([1, 2, 3, 8, 9, 10])+ c: K3 J7 V# l3 S: z- q- C
G3 = G1.subgraph([4, 5, 6, 7])
: `6 {! ^5 d9 t1 TG = nx.union(G2, G3)2 q$ F1 ?$ o. H4 D2 q% |
print(G.nodes) # 返回所有的顶点 [node1,...]/ K9 n% B/ m) ] j
# [1, 2, 3, 8, 9, 10, 4, 5, 6, 7]) g( Y. D* w- r
2 |3 f6 K. p. n! E: K
* ^ j0 j- b6 w8 n4 \4 V
3、图的绘制与分析3.1 图的绘制
* r/ w: t$ ]1 H& a# {6 \; P3 x4 L+ ]2 x可视化是图论和网络问题中很重要的内容。NetworkX 在 Matplotlib、Graphviz 等图形工具包的基础上,提供了丰富的绘图功能。0 m9 o2 R6 D7 }6 V J( ?! G- R0 ]
6 _& C, t. w7 r* E本系列拟对图和网络的可视化作一个专题,在此只简单介绍基于 Matplotlib 的基本绘图函数。基本绘图函数使用字典提供的位置将节点放置在散点图上,或者使用布局函数计算位置。0 q+ w' O* z B8 W5 g s* a8 ]
) o# R' O( X) X4 b1 T8 N
方法 说明
f% @& w6 ?7 S% b2 }3 n5 F- mdraw(G[,pos,ax]) 基于 Matplotlib 绘制 图 G
* D8 Q9 e3 C8 T' Qdraw_networkx(G[, pos, arrows, with_labels]) 基于 Matplotlib 绘制 图 G
0 K$ V8 a: d4 E+ G: Sdraw_networkx_nodes(G, pos[, nodelist, . . . ]) 绘制图 G 的顶点
. V: }) V) j5 Q$ A1 [' \7 i+ P: D% edraw_networkx_edges(G, pos[, edgelist, . . . ]) 绘制图 G 的边# Z3 j4 h- ]7 K+ `: @5 z- v
draw_networkx_labels(G, pos[, labels, . . . ]) 绘制顶点的标签; m* q4 y7 B) [
draw_networkx_edge_labels(G, pos[, . . . ]) 绘制边的标签" J& J; \. ] f2 L' h% H2 P
' i7 `) t% E5 X( C- `- S" x) r- a7 v
( B7 D" Z W, D. U f/ z; \% y l其中,nx.draw() 和 nx.draw_networkx() 是最基本的绘图函数,并可以通过自定义函数属性或其它绘图函数设置不同的绘图要求。
+ x& D! z+ P7 r% L# g$ i( Ydraw(G, pos=None, ax=None, **kwds) draw_networkx(G, pos=None, arrows=True, with_labels=True, **kwds)
" u" S4 w' r6 |% T7 k' w0 { s常用的属性定义如下:! @$ p8 M' ]5 m
: a0 ^: w; ~! T3 O. c/ i# L‘node_size’:指定节点的尺寸大小,默认300
7 A B( X: ?1 @6 e8 p2 |! q‘node_color’:指定节点的颜色,默认红色2 o" D/ y9 @# r4 e" t
‘node_shape’:节点的形状,默认圆形( S2 X3 @$ g$ u
'‘alpha’:透明度,默认1.0,不透明; _5 _% R& A6 Z% U O
‘width’:边的宽度,默认1.0
& Z% W" I& e0 {' ?7 [‘edge_color’:边的颜色,默认黑色
7 G( n M, q/ v5 ^# J‘style’:边的样式,可选 ‘solid’、‘dashed’、‘dotted’、‘dashdot’; o) X) X6 r$ [ ]/ @8 b' y
‘with_labels’:节点是否带标签,默认True
# y7 L2 q+ T) z. z, ^; `4 M. `‘font_size’:节点标签字体大小,默认127 D3 _; d c$ u5 ?/ K6 M
‘font_color’:节点标签字体颜色,默认黑色
- H( l; n* R& v; F1 g+ x6 S- |& ^2 J
9 ?( Q; E$ U; |' s4 W
3.2 图的分析NetwotkX 提供了图论函数对图的结构进行分析& |+ i- X* V+ C4 F/ m0 b
子图
6 h8 `/ q2 I9 B4 S) G3 k- 子图是指顶点和边都分别是图 G 的顶点的子集和边的子集的图。
- subgraph()方法,按顶点从图 G 中抽出子图。例程如前。8 D5 m: D) X, t |# |! R" M; y
连通子图
7 X8 H0 a) t+ Z3 k. `8 }) ^8 U7 n2 [9 r. N- [
- 如果图 G 中的任意两点间相互连通,则 G 是连通图。
- [color=rgba(0, 0, 0, 0.749019607843137)]connected_components()方法,返回连通子图的集合。3 H1 J8 E7 n# k
[color=rgba(0, 0, 0, 0.749019607843137)]G = nx.path_graph(4)[color=rgba(0, 0, 0, 0.749019607843137)]nx.add_path(G, [7, 8, 9])[color=rgba(0, 0, 0, 0.749019607843137)]# 连通子图[color=rgba(0, 0, 0, 0.749019607843137)]listCC = [len(c) for c in sorted(nx.connected_components(G), key=len, reverse=True)][color=rgba(0, 0, 0, 0.749019607843137)]maxCC = max(nx.connected_components(G), key=len)[color=rgba(0, 0, 0, 0.749019607843137)]print('Connected components:{}'.format(listCC)) # 所有连通子图[color=rgba(0, 0, 0, 0.749019607843137)]# Connected components:[4, 3][color=rgba(0, 0, 0, 0.749019607843137)]print('Largest connected components:{}'.format(maxCC)) # 最大连通子图[color=rgba(0, 0, 0, 0.749019607843137)]# Largest connected components:{0, 1, 2, 3}[color=rgba(0, 0, 0, 0.749019607843137)]强连通如果有向图 G 中的任意两点间相互连通,则称 G 是强连通图。strongly_connected_components()方法,返回所有强连通子图的列表。# 强连通G = nx.path_graph(4, create_using=nx.DiGraph())nx.add_path(G, [3, 8, 1])# 找出所有的强连通子图con = nx.strongly_connected_components(G)print(type(con),list(con))# <class 'generator'> [{8, 1, 2, 3}, {0}]弱连通如果一个有向图 G 的基图是连通图,则有向图 G 是弱连通图。weakly_connected_components()方法,返回所有弱连通子图的列表。# 弱连通G = nx.path_graph(4, create_using=nx.DiGraph()) #默认生成节点 0,1,2,3 和有向边 0->1,1->2,2->3nx.add_path(G, [7, 8, 3]) #生成有向边:7->8->3con = nx.weakly_connected_components(G)print(type(con),list(con))# <class 'generator'> [{0, 1, 2, 3, 7, 8}]6 h: z0 ^' H7 s$ Q' K2 ?7 ^: i
4 o0 y9 S: M+ `$ g4 P4 K; o& y. F8 }
5 o: i7 e" w9 v1 p& f* [( f/ T5 \6 a" G" }
|