Python小白的数学建模课-图论的基本概念, Y) \( F* U! ^
+ W' K+ \. }% o1 Z
- 图论中所说的图,不是图形图像或地图,而是指由顶点和边所构成的图形结构。
- 图论不仅与拓扑学、计算机数据结构和算法密切相关,而且正在成为机器学习的关键技术。
- 本系列结合数学建模的应用需求,来介绍 NetworkX 图论与复杂网络工具包的基本功能和典型算法。
5 R: w$ W, Z) u* d9 h
+ X1 b* X/ k3 L( a2 u1. 图论1.1 图论是什么
' ~2 L* k5 }9 z Q/ O: M% [图论〔Graph Theory〕以图为研究对象,是离散数学的重要内容。图论不仅与拓扑学、计算机数据结构和算法密切相关,而且正在成为机器学习的关键技术。
( z% O3 ?, u( z
" k" s7 _% y$ h- v3 `+ H4 H图论中所说的图,不是指图形图像(image)或地图(map),而是指由顶点(vertex)和连接顶点的边(edge)所构成的关系结构。0 b9 I5 L# |2 v1 ^( T: D3 o
. L, {" \' p( `( L2 @) m+ _图提供了一种处理关系和交互等抽象概念的更好的方法,它还提供了直观的视觉方式来思考这些概念。
$ `6 D! L% [: g9 Q. g+ A, v
4 t' S* r9 W$ b5 w1.2 NetworkX 工具包5 K6 Q+ |0 m# j; M
NetworkX 是基于 Python 语言的图论与复杂网络工具包,用于创建、操作和研究复杂网络的结构、动力学和功能。
; o4 k4 m* L) c1 P; P
& x' h7 f: ` C3 m* g4 [- {NetworkX 可以以标准和非标准的数据格式描述图与网络,生成图与网络,分析网络结构,构建网络模型,设计网络算法,绘制网络图形。; L3 x5 d& j, N. M* ]! R- P
3 N$ T U6 D6 s3 s
NetworkX 提供了图形的类、对象、图形生成器、网络生成器、绘图工具,内置了常用的图论和网络分析算法,可以进行图和网络的建模、分析和仿真。
9 h' R/ c) \6 ^
: u1 `# @, p. f6 t8 ]) GNetworkX 的功能非常强大和庞杂,所涉及内容远远、远远地超出了数学建模的范围,甚至于很难进行系统的概括。本系列结合数学建模的应用需求,来介绍 NetworkX 图论与复杂网络工具包的基本功能和典型算法。: G) N M. [# B6 y% h
% `% w! J+ R$ j7 q0 s2 U' X
![]()
: }9 U9 f2 S1 v- }( ~2、图、顶点和边的创建与基本操作; `/ r! ~# C" ]8 ^, ^+ c
图由顶点和连接顶点的边构成,但与顶点的位置、边的曲直长短无关。 Networkx 支持创建简单无向图、有向图和多重图;内置许多标准的图论算法,节点可为任意数据;支持任意的边值维度,功能丰富,简单易用。 2.1 图的基本概念6 j* v9 D3 V3 U1 ]
图(Graph):图是由若干顶点和连接顶点的边所构成关系结构。
( }" h/ M. r5 N* X. s顶点(Node):图中的点称为顶点,也称节点。; N6 |: W# q' c$ b
边(Edge):顶点之间的连线,称为边。4 |/ [) d/ k/ g) n8 c" Z' o
平行边(Parallel edge):起点相同、终点也相同的两条边称为平行边。: \- y, L3 j/ L1 K7 H
循环(Cycle):起点和终点重合的边称为循环。+ Y' |) q! |% b; H; K9 ^5 A
有向图(Digraph):图中的每条边都带有方向,称为有向图。" X7 R1 O' b% L5 H
无向图(Undirected graph):图中的每条边都没有方向,称为无向图。
" z5 c" v' V/ s3 a赋权图(Weighted graph):图中的每条边都有一个或多个对应的参数,称为赋权图。该参数称为这条边的权,权可以用来表示两点间的距离、时间、费用。
, X7 Z6 @* s: t" d5 \) v度(Degree):与顶点相连的边的数量,称为该顶点的度。
/ f6 e* V. j* L- Z/ l
- u* ?) V/ c" [: U2.2 图、顶点和边的操作* K2 R& C a$ |% u* X
Networkx很容易创建图、向图中添加顶点和边、从图中删除顶点和边,也可以查看、删除顶点和边的属性。* y% u5 Y# C& r5 N
# ?4 N- y5 P2 x* |9 K2.2.1 图的创建Graph() 类、DiGraph() 类、MultiGraph() 类和 MultiDiGraph() 类分别用来创建:无向图、有向图、多图和有向多图。定义和例程如下:, J+ w1 \& J2 d/ X9 _
- J4 ^: Z. {( x5 Q# u% e8 sclass Graph(incoming_graph_data=None, **attr)
$ }; U& Y1 T2 `& J ] I6 Fimport networkx as nx # 导入 NetworkX 工具包* _! K5 J6 B0 D8 a) Q
( f5 d5 b& y+ u; ] q% n
# 创建 图/ ?1 y; l0 h4 g+ m9 ?
G1 = nx.Graph() # 创建:空的 无向图
# n( ~3 y* j6 M* J$ pG2 = nx.DiGraph() #创建:空的 有向图) I/ H' m$ b6 ?$ {9 @) s4 M
G3 = nx.MultiGraph() #创建:空的 多图
; N3 p: C: G: M6 }/ i) \$ WG4 = nx.MultiDiGraph() #创建:空的 有向多图" |- [& v3 m, b- j: h. `
/ R# ^+ {0 f# f0 n, o. v3 E( V1 m% B4 q
' n6 N8 Y, ~( L2.2.2 顶点的添加、删除和查看
9 a, K% Z8 ?# G) f图的每个顶点都有唯一的标签属性(label),可以用整数或字符类型表示,顶点还可以自定义任意属性。 顶点的常用操作:添加顶点,删除顶点,定义顶点属性,查看顶点和顶点属性。定义和例程如下: + C3 N; ?( h% B* o' ~- r; Y; X) ]
Graph.add_node(node_for_adding, **attr)
/ \+ I& t# b9 _0 Z" _ yGraph.add_nodes_from(nodes_for_adding, **attr)3 g( ~, j. M* \# g3 F" \: S
Graph.remove_node(n)
$ ]. P ]' i9 K2 g! iGraph.remove_nodes_from(nodes)
7 r- J8 r6 m/ ~/ @
0 J, G" T' L5 U$ ?, r! _# 顶点(node)的操作9 D4 f b' r5 B. @; N
# 向图中添加顶点, ?6 D7 w7 i( |6 {/ ]
G1.add_node(1) # 向 G1 添加顶点 14 G" F1 ~5 |6 x7 {. B. t+ D
G1.add_node(1, name='n1', weight=1.0) # 添加顶点 1,定义 name, weight 属性. Q6 ^# E' ~7 g! L2 m. ]; ?
G1.add_node(2, date='May-16') # 添加顶点 2,定义 time 属性
5 o7 N {7 z2 H+ J0 H5 xG1.add_nodes_from([3, 0, 6], dist=1) # 添加多个顶点,并定义属性9 Q/ ?8 G# l% o( z% N
G1.add_nodes_from(range(10, 15)) # 向图 G1 添加顶点 10~149 ?" X7 g& P# r
4 @3 Z7 C ^# j7 V8 \$ {) E; G
# 查看顶点和顶点属性
1 ^" l* F) A: l) c" Z) g+ bprint(G1.nodes()) # 查看顶点列表
@% v& p5 o* R4 h2 d# [1, 2, 3, 0, 6, 10, 11, 12, 13, 14]
8 L9 A, {( Q5 N5 W5 E. K& Hprint(G1._node) # 查看顶点属性
2 `! B- ^8 F" f' \8 C* X8 Q# {1: {'name': 'n1', 'weight': 1.0}, 2: {'date': 'May-16'}, 3: {'dist': 1}, 0: {'dist': 1}, 6: {'dist': 1}, 10: {}, 11: {}, 12: {}, 13: {}, 14: {}}! @) I! V6 `$ i! g
9 }. r" z5 f: d' U2 V, ^# 从图中删除顶点
8 _: Y' B" ]# w# ^9 uG1.remove_node(1) # 删除顶点" c q7 F2 f" l1 T: M: U
G1.remove_nodes_from([1, 11, 13, 14]) # 通过顶点标签的 list 删除多个顶点
% A4 f$ d/ J7 x" |4 rprint(G1.nodes()) # 查看顶点% z I R \# Y6 N# W4 W/ C9 Y" G
# [2, 3, 0, 6, 10, 12] # 顶点列表! h* m8 F. Z/ R2 M0 T* z, C
2.2.3 边的添加、删除和查看边是两个顶点之间的连接,在 NetworkX 中 边是由对应顶点的名字的元组组成 e=(node1,node2)。边可以设置权重、关系等属性。 边的常用操作:添加边,删除边,定义边的属性,查看边和边的属性。向图中添加边时,如果边的顶点是图中不存在的,则自动向图中添加该顶点。 Graph.add_edge(u_of_edge, v_of_edge, **attr)4 e. g. V$ Q9 X- b) L
Graph.add_edges_from(ebunch_to_add, **attr)
8 c+ F4 M9 A. o* F uGraph.add_weighted_edges_from(ebunch_to_add, weight=‘weight’, **attr)) y( v" I2 \! y1 u9 ^( [
( _& m8 O5 p! O% r2 I; G) s# 边(edge)的操作
]+ G" @+ x% m1 }3 D# 向图中添加边
! x% X; H5 s4 o4 u; HG1.add_edge(1,5) # 向 G1 添加边,并自动添加图中没有的顶点
, g6 H) m H( d' @% TG1.add_edge(0,10, weight=2.7) # 向 G1 添加边,并设置边的属性7 ~' h/ o: m2 W" D; {
G1.add_edges_from([(1,2,{'weight':0}), (2,3,{'color':'blue'})]) # 向图中添加边,并设置属性( m, T' U6 j$ h, F7 P
G1.add_edges_from([(3,6),(1,2),(6,7),(5,10),(0,1)]) # 向图中添加多条边0 [) [' T9 u) ]5 R
G1.add_weighted_edges_from([(1,2,3.6),[6,12,0.5]]) # 向图中添加多条赋权边: (node1,node2,weight)
4 i% ^/ }; p( w1 @( d# T1 h$ _print(G1.nodes()) # 查看顶点
' F' I% V! N# _6 [# e: G$ Y+ P1 L+ T3 T# [2, 3, 0, 6, 10, 12, 1, 5, 7] # 自动添加了图中没有的顶点
4 p" ~# I( {6 x+ c9 n( d3 U4 S
+ |2 I$ G3 r N+ \. J* j$ I t, V! G+ Z# 从图中删除边
- v! @) D% T; n% }4 AG1.remove_edge(0,1) # 从图中删除边 0-1
% r- m9 G: V+ _G1.remove_edges_from([(2,3),(1,5),(6,7)]) # 从图中删除多条边
( E4 j) j# U( x0 t3 b* S6 |3 ~6 X- K( u5 h6 Q
# 查看 边和边的属性
. c9 W; L/ R7 t; G, D+ j# d" S1 jprint(G1.edges) # 查看所有的边
/ I+ Z$ x8 C1 y+ @+ V[(2, 1), (3, 6), (0, 10), (6, 12), (10, 5)]
: F) M2 q6 J0 f/ tprint(G1.get_edge_data(1,2)) # 查看指定边的属性
/ f( m. n7 e- {# {'weight': 3.6}1 ]; n* b3 y$ z1 m$ C6 B3 D
print(G1[1][2]) # 查看指定边的属性
' M' |7 C; Z$ T0 k9 e# {'weight': 3.6}$ w7 S! k# r0 S6 ?! a* j8 S5 j
print(G1.edges(data=True)) # 查看所有边的属性
2 o% w% e$ v- d% r! z: P# [(2, 1, {'weight': 3.6}), (3, 6, {}), (0, 10, {'weight': 2.7}), (6, 12, {'weight': 0.5}), (10, 5, {})]
! k8 a- _- m/ K; o# e! |( m7 `1 ?7 x
2.2.4 查看图、顶点和边的信息
8 q# ]# \# v" b8 Q& o2 d7 S2 o
# 查看图、顶点和边的信息$ H1 _( I2 _9 I0 r) V X4 C: N
print(G1.nodes) # 返回所有的顶点 [node1,...]
8 {: d/ S- e) V1 e) c# [2, 3, 0, 6, 10, 12, 1, 5, 7]
* Y! l" n' A, vprint(G1.edges) # 返回所有的边 [(node1,node2),...]: w( I& x. d8 t' q: K1 S. E
# [(2, 1), (3, 6), (0, 10), (6, 12), (10, 5)]
3 m+ L% I' o+ I' J, k5 s. Eprint(G1.degree) # 返回各顶点的度 [(node1,degree1),...]9 `0 x' |3 v% g7 I# p
# [(2, 1), (3, 1), (0, 1), (6, 2), (10, 2), (12, 1), (1, 1), (5, 1), (7, 0)]) W. e. M) u, M8 I1 k# ?
print(G1.number_of_nodes()) # 返回顶点的数量0 U! f7 ]5 p7 F: H: _
# 9
f" [- a7 P* L5 C7 y$ P" \3 Kprint(G1.number_of_edges()) # 返回边的数量: K+ g9 @) i3 _% g$ p+ i+ z
# 56 ]* P: P8 x& f% }" b! q7 r3 ^1 H
print(G1[10]) # 返回与指定顶点相邻的所有顶点的属性0 Q* q3 N8 b6 u- t
# {0: {'weight': 2.7}, 5: {}}
* n- W4 J( @3 b$ p' [4 y4 |5 g4 n' f# Mprint(G1.adj[10]) # 返回与指定顶点相邻的所有顶点的属性$ T2 p9 O/ v$ u* Q, m
# {0: {'weight': 2.7}, 5: {}}# L8 ]3 B& |" S# L8 K5 z
print(G1[1][2]) # 返回指定边的属性' E% Q" y7 D0 h# ]! S' g4 D2 F& j
# {'weight': 3.6}2 q" b3 X! y+ J4 a# T2 W+ `
print(G1.adj[1][2]) # 返回指定边的属性+ E4 ^- N8 X+ S/ C
# {'weight': 3.6}( c. n3 W: `; m# k+ f
print(G1.degree(10)) # 返回指定顶点的度
+ o: y- [" r9 P) M# 22 m) [4 P: F5 M, D
4 T: r/ \) z# V' L* Z# h7 E5 w
print('nx.info:',nx.info(G1)) # 返回图的基本信息
+ K+ a _' s* _2 k* I0 J; M s* T1 _* bprint('nx.degree:',nx.degree(G1)) # 返回图中各顶点的度9 }' ~. g& c/ D; i# m
print('nx.density:',nx.degree_histogram(G1)) # 返回图中度的分布
$ X" I& M) c4 _( \print('nx.pagerank:',nx.pagerank(G1)) # 返回图中各顶点的频率分布
t* w8 b+ C6 ?% ]" @/ [3 @: W3 i8 P& l) e
+ X# ]8 R8 k' v o- u# G
% r; S6 @6 U0 K9 X$ j* a
4 t7 M2 A, l0 Q; J% ~
2 l2 x( T7 z9 R' D* `8 _" ?5 u2.3 图的属性和方法图的方法7 H, V3 y) S, o$ q8 w; A% a% z
0 A; _; a1 g9 m# k. @# x( t' Z方法 说明* g; f* F7 `+ D' O/ B
G.has_node(n) 当图 G 中包括顶点 n 时返回 True6 O8 d& ^: a, Z1 @5 W
G.has_edge(u, v) 当图 G 中包括边 (u,v) 时返回 True: [' {* U. f# D A: i3 A1 Z
G.number_of_nodes() 返回 图 G 中的顶点的数量
5 v9 g5 \0 n3 A5 |& X0 a: K. vG.number_of_edges() 返回 图 G 中的边的数量! x7 z% c. [; i$ ~- y- P
G.number_of_selfloops() 返回 图 G 中的自循环边的数量
. J, E5 f1 [9 P) _G.degree([nbunch, weight]) 返回 图 G 中的全部顶点或指定顶点的度6 L- j7 k" E5 I0 l! H
G.selfloop_edges([data, default]) 返回 图 G 中的全部的自循环边: F5 ~ r1 w' E: C
G.subgraph([nodes]) 从图 G1中抽取顶点[nodes]及对应边构成的子图4 T1 g# A+ \+ `3 Y$ o, }* x
union(G1,G2) 合并图 G1、G2
* C/ a& d: z9 e3 a! V+ Onx.info(G) 返回图的基本信息 d( Q: M$ N' ]% w
nx.degree(G) 返回图中各顶点的度
" N/ B* y$ t0 C, q% u- a& znx.degree_histogram(G) 返回图中度的分布
" w8 Y9 V1 y. N( u+ \- b3 k/ c4 Onx.pagerank(G) 返回图中各顶点的频率分布
% X5 i( ^* Y [' _+ p! L( snx.add_star(G,[nodes],**attr) 向图 G 添加星形网络
3 D$ ?' ` K+ w. p1 P: C9 b! u* m# R! qnx.add_path(G,[nodes],**attr) 向图 G 添加一条路径
3 {; o# q' t# I" G, znx.add_cycle(G,[nodes],**attr) 向图 G 添加闭合路径( H9 N; K7 J5 u6 g& Z( E7 z
8 \9 s) `- l5 u" i2 n4 Y% o
. _: }* l3 [& a( k4 ?) ^5 `: W s例程:% p/ {8 [, R. v. W# E" y
G1.clear() # 清空图G14 P( t) G- y) W2 o% ?( q" j1 I
nx.add_star(G1, [1, 2, 3, 4, 5], weight=1) # 添加星形网络:以第一个顶点为中心
: X3 W5 L: \9 {1 B9 F# [(1, 2), (1, 3), (1, 4), (1, 5)]' D1 Z2 G0 u c# N
nx.add_path(G1, [5, 6, 8, 9, 10], weight=2) # 添加路径:顺序连接 n个节点的 n-1条边
( Y0 e2 F7 Q8 I( f- S1 j+ g1 t# [(5, 6), (6, 8), (8, 9), (9, 10)]
: w: s; I; n! D4 p( o4 M, h/ F. K5 anx.add_cycle(G1, [7, 8, 9, 10, 12], weight=3) # 添加闭合回路:循环连接 n个节点的 n 条边
R- w) [( J/ \$ I" c3 ?: Y# u# [(7, 8), (7, 12), (8, 9), (9, 10), (10, 12)]3 ?8 }/ m- w3 A! X' i6 m, f _8 p
print(G1.nodes) # 返回所有的顶点 [node1,...]
' w$ H* b' H6 @1 L, ~& dnx.draw_networkx(G1), U* M3 `# c/ {
plt.show()
5 F0 V2 g6 @# ~& G( Q: l
9 `; |1 @+ n# iG2 = G1.subgraph([1, 2, 3, 8, 9, 10])2 M6 A7 v8 U- N) Q f3 B+ U: S: {
G3 = G1.subgraph([4, 5, 6, 7])+ X4 w* M9 f. R1 q3 n; h
G = nx.union(G2, G3)* o' o% i/ n0 i4 y
print(G.nodes) # 返回所有的顶点 [node1,...]' x; m3 t0 A) F( E9 n# w
# [1, 2, 3, 8, 9, 10, 4, 5, 6, 7]
: Y9 d2 ^; a2 l/ ~0 } ]/ `1 k2 n0 v6 g2 z. z0 l
* G: @( C; l6 l3 t$ J5 T3、图的绘制与分析3.1 图的绘制$ N S5 }9 e! y. Z& o. E: X0 @
可视化是图论和网络问题中很重要的内容。NetworkX 在 Matplotlib、Graphviz 等图形工具包的基础上,提供了丰富的绘图功能。
' w- s1 G2 l" J/ E2 @
0 \, y$ T0 W; s/ u& K* _- }本系列拟对图和网络的可视化作一个专题,在此只简单介绍基于 Matplotlib 的基本绘图函数。基本绘图函数使用字典提供的位置将节点放置在散点图上,或者使用布局函数计算位置。! ?, m6 _0 m1 `! h
9 V: i" \2 [# P+ F' k% _
方法 说明
+ m8 I: l7 G# n5 |draw(G[,pos,ax]) 基于 Matplotlib 绘制 图 G
+ E: t8 m9 _ _2 ^2 Pdraw_networkx(G[, pos, arrows, with_labels]) 基于 Matplotlib 绘制 图 G( W# ?7 I, J4 }# C8 m
draw_networkx_nodes(G, pos[, nodelist, . . . ]) 绘制图 G 的顶点- p: U8 [2 Q7 d
draw_networkx_edges(G, pos[, edgelist, . . . ]) 绘制图 G 的边* R. \9 Y3 v* f+ X8 c
draw_networkx_labels(G, pos[, labels, . . . ]) 绘制顶点的标签8 \" P g% w8 n, G, r
draw_networkx_edge_labels(G, pos[, . . . ]) 绘制边的标签
- |. ], ~+ b. P7 ^% f1 w) B
; v( E1 ]3 \2 c: Q2 w. A
9 c4 U$ `- B, g( h$ u) m) ~其中,nx.draw() 和 nx.draw_networkx() 是最基本的绘图函数,并可以通过自定义函数属性或其它绘图函数设置不同的绘图要求。7 c, W0 b" q! q( K+ ]5 @& @# E
draw(G, pos=None, ax=None, **kwds) draw_networkx(G, pos=None, arrows=True, with_labels=True, **kwds)
/ V- L3 }8 V9 `( _) J+ j( s常用的属性定义如下:8 y. M" Q, k% G$ B
$ T5 \* ]0 k0 v* B1 `
‘node_size’:指定节点的尺寸大小,默认300
& \6 m* T) {; i‘node_color’:指定节点的颜色,默认红色+ y @& }) c/ n' N
‘node_shape’:节点的形状,默认圆形
! p5 S! |: j, p, h7 E'‘alpha’:透明度,默认1.0,不透明
8 }2 {! l" {/ i. \+ Z+ b' B6 ?% f‘width’:边的宽度,默认1.0, |8 b, ^! O* L& q. t: o
‘edge_color’:边的颜色,默认黑色& A0 d) U0 ~4 R! M* Z
‘style’:边的样式,可选 ‘solid’、‘dashed’、‘dotted’、‘dashdot’3 H9 V' b, _, A9 [7 |, d
‘with_labels’:节点是否带标签,默认True: c" Y( l' c# G7 H/ E
‘font_size’:节点标签字体大小,默认12
, ?/ Z, Z$ t$ D; H" Q1 l6 }( `‘font_color’:节点标签字体颜色,默认黑色 L* u+ S* k& L5 B3 [
* w0 I8 R7 J; Y/ \
$ }5 c2 v$ \( S/ `/ |
3.2 图的分析NetwotkX 提供了图论函数对图的结构进行分析
. g- W7 Z3 B% V* ]4 k8 T子图
% {" R+ E1 R8 j* C( u- 子图是指顶点和边都分别是图 G 的顶点的子集和边的子集的图。
- subgraph()方法,按顶点从图 G 中抽出子图。例程如前。
8 B1 e. l8 N Y& s% ?; O3 e5 j 连通子图
, z3 f, ?% _+ ]: d! k% w/ e5 I& T8 E3 B' s
- 如果图 G 中的任意两点间相互连通,则 G 是连通图。
- [color=rgba(0, 0, 0, 0.749019607843137)]connected_components()方法,返回连通子图的集合。7 f: I4 e! M7 v2 ^7 g$ ]/ \
[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}]
$ y& M6 C. h/ G- j ' X0 s" s7 p" w5 Q4 d- v1 X9 {- \
. {/ d0 M1 ], }4 U8 L) m. y0 p$ t5 [2 A7 v. o$ X4 N- j
8 m1 {% \) x a5 w+ o
|