Python小白的数学建模课-图论的基本概念
5 A _5 H+ ?, Y1 L$ q- `- p. Q: q+ W5 Q: x- Y. M0 M
- 图论中所说的图,不是图形图像或地图,而是指由顶点和边所构成的图形结构。
- 图论不仅与拓扑学、计算机数据结构和算法密切相关,而且正在成为机器学习的关键技术。
- 本系列结合数学建模的应用需求,来介绍 NetworkX 图论与复杂网络工具包的基本功能和典型算法。9 T8 J8 q K% @3 I
) N) T3 \" H2 N& q* j3 \1. 图论1.1 图论是什么) `5 F: c% g9 C# M
图论〔Graph Theory〕以图为研究对象,是离散数学的重要内容。图论不仅与拓扑学、计算机数据结构和算法密切相关,而且正在成为机器学习的关键技术。
' P% b7 L9 x! S- r% a' s; D' ~" l2 E ?5 e
图论中所说的图,不是指图形图像(image)或地图(map),而是指由顶点(vertex)和连接顶点的边(edge)所构成的关系结构。
& J. v" B% [3 h& Q+ T
+ L+ V) i2 d5 p: l9 b* Q图提供了一种处理关系和交互等抽象概念的更好的方法,它还提供了直观的视觉方式来思考这些概念。
+ U; s! \& [1 e3 k0 ^4 h! |( Z; h; e% T* z ]8 z
1.2 NetworkX 工具包
: H% }1 Z+ P+ n. p$ L4 m2 gNetworkX 是基于 Python 语言的图论与复杂网络工具包,用于创建、操作和研究复杂网络的结构、动力学和功能。! f( O$ ?" |. M& q
+ D4 ^; F, W. z3 ^7 ~NetworkX 可以以标准和非标准的数据格式描述图与网络,生成图与网络,分析网络结构,构建网络模型,设计网络算法,绘制网络图形。8 G. k& H# w2 ^! U* l2 R
$ T% _0 R( H9 I- j5 eNetworkX 提供了图形的类、对象、图形生成器、网络生成器、绘图工具,内置了常用的图论和网络分析算法,可以进行图和网络的建模、分析和仿真。3 y# L, v5 O3 q) [' ?; K
$ i" N. s6 _5 ~9 k" ^% a$ ?NetworkX 的功能非常强大和庞杂,所涉及内容远远、远远地超出了数学建模的范围,甚至于很难进行系统的概括。本系列结合数学建模的应用需求,来介绍 NetworkX 图论与复杂网络工具包的基本功能和典型算法。' A, u( u5 C& X( S0 Y' G) w
, @) K( Y- f, ~, Z0 d1 ^ T3 E- W![]()
8 Q$ i) l: E# M0 c4 |2、图、顶点和边的创建与基本操作
+ ]2 _; D2 ?* ~, O$ b图由顶点和连接顶点的边构成,但与顶点的位置、边的曲直长短无关。 Networkx 支持创建简单无向图、有向图和多重图;内置许多标准的图论算法,节点可为任意数据;支持任意的边值维度,功能丰富,简单易用。 2.1 图的基本概念0 h+ n' I& }( M
图(Graph):图是由若干顶点和连接顶点的边所构成关系结构。
5 j X! g R2 Q( Z# Y. k# G3 L2 B顶点(Node):图中的点称为顶点,也称节点。
, J" H6 t0 |. ~+ v, a边(Edge):顶点之间的连线,称为边。* y+ n+ R$ m! ]- |$ B4 J
平行边(Parallel edge):起点相同、终点也相同的两条边称为平行边。7 a; B& t8 g2 O( r
循环(Cycle):起点和终点重合的边称为循环。1 u2 i' p) K6 \8 w, }7 U
有向图(Digraph):图中的每条边都带有方向,称为有向图。
2 `" p; ` ^9 ~( L/ M无向图(Undirected graph):图中的每条边都没有方向,称为无向图。: q8 M1 p" V; F
赋权图(Weighted graph):图中的每条边都有一个或多个对应的参数,称为赋权图。该参数称为这条边的权,权可以用来表示两点间的距离、时间、费用。
/ `2 E- `3 k9 d/ {% J2 V度(Degree):与顶点相连的边的数量,称为该顶点的度。% `- s0 u- Z/ ?
$ V. f6 D" M6 L" z2.2 图、顶点和边的操作3 R$ o x/ b H; G1 u0 a! I& e1 L$ h
Networkx很容易创建图、向图中添加顶点和边、从图中删除顶点和边,也可以查看、删除顶点和边的属性。
! V3 o$ A: D9 c. R- a0 d: \1 d( h4 N, J- N# z# M
2.2.1 图的创建Graph() 类、DiGraph() 类、MultiGraph() 类和 MultiDiGraph() 类分别用来创建:无向图、有向图、多图和有向多图。定义和例程如下:
4 W) b3 r/ Q' S! o4 d+ i) @9 U% E5 f/ g3 l I$ @$ d H& w5 |
class Graph(incoming_graph_data=None, **attr)6 D- b j# u* |3 D2 V$ a& J0 e; s
import networkx as nx # 导入 NetworkX 工具包
5 `- V4 I! @! _! {2 {. o" ^
# U4 D# I& N# e( s& e. x$ Y) E# 创建 图7 A- ?/ I' I5 ^$ d6 V8 ?
G1 = nx.Graph() # 创建:空的 无向图" k) F7 ?0 e h% ~4 f6 A
G2 = nx.DiGraph() #创建:空的 有向图
1 v% {! u8 d: p, G7 T- O$ hG3 = nx.MultiGraph() #创建:空的 多图5 q# j7 k0 F! }6 ^# E
G4 = nx.MultiDiGraph() #创建:空的 有向多图
9 | P! @" J4 E
~, U3 s8 x1 K% G- O8 F3 {) V( k8 W, O
2.2.2 顶点的添加、删除和查看
( D6 d- C/ W J图的每个顶点都有唯一的标签属性(label),可以用整数或字符类型表示,顶点还可以自定义任意属性。 顶点的常用操作:添加顶点,删除顶点,定义顶点属性,查看顶点和顶点属性。定义和例程如下: 3 A( m- ^7 D5 k9 ? k3 r3 N
Graph.add_node(node_for_adding, **attr)
" |5 e6 @; v/ |0 `0 c0 oGraph.add_nodes_from(nodes_for_adding, **attr)+ z0 d3 Z6 T+ f- {
Graph.remove_node(n)4 V# h% ^7 K+ y) c0 }7 m: c! n
Graph.remove_nodes_from(nodes)
8 i" Y# Q( `6 j
1 I( t: {0 n; X1 S! l# 顶点(node)的操作 ?% B- @1 \' P: g% ~0 J
# 向图中添加顶点% v3 {, ^( j' q, ^# F- f
G1.add_node(1) # 向 G1 添加顶点 1
0 W% {0 K0 l' W' u6 ~( U9 [: oG1.add_node(1, name='n1', weight=1.0) # 添加顶点 1,定义 name, weight 属性
. I m& ~8 Q- a' x4 lG1.add_node(2, date='May-16') # 添加顶点 2,定义 time 属性$ F: o/ \; {& O1 }/ D/ h' I8 s. R# ~
G1.add_nodes_from([3, 0, 6], dist=1) # 添加多个顶点,并定义属性- c8 `. E, N- Q+ O1 `9 @; _
G1.add_nodes_from(range(10, 15)) # 向图 G1 添加顶点 10~14+ [: m5 Q- w; }, a/ R
9 { i( v c! l3 Y. h5 R! L8 D! Y# 查看顶点和顶点属性5 n. o# m0 I6 f8 n9 [
print(G1.nodes()) # 查看顶点列表0 ~; t4 ]7 Y1 G4 D8 J5 T
# [1, 2, 3, 0, 6, 10, 11, 12, 13, 14]
; i" C" T- m3 W8 }print(G1._node) # 查看顶点属性4 Q- {4 L' m/ R1 l4 x
# {1: {'name': 'n1', 'weight': 1.0}, 2: {'date': 'May-16'}, 3: {'dist': 1}, 0: {'dist': 1}, 6: {'dist': 1}, 10: {}, 11: {}, 12: {}, 13: {}, 14: {}}
" A: l" a! K! h- y5 y$ A* Q7 p5 p: }
# 从图中删除顶点' h# |9 C8 s# ] A0 ~
G1.remove_node(1) # 删除顶点* { T9 |: H, i/ s% H' o8 v
G1.remove_nodes_from([1, 11, 13, 14]) # 通过顶点标签的 list 删除多个顶点9 L/ Y- N, g6 M
print(G1.nodes()) # 查看顶点
8 o$ f( y( w# r$ N2 }9 w Z& @# [2, 3, 0, 6, 10, 12] # 顶点列表
) |9 G" u0 r; y. o2.2.3 边的添加、删除和查看边是两个顶点之间的连接,在 NetworkX 中 边是由对应顶点的名字的元组组成 e=(node1,node2)。边可以设置权重、关系等属性。 边的常用操作:添加边,删除边,定义边的属性,查看边和边的属性。向图中添加边时,如果边的顶点是图中不存在的,则自动向图中添加该顶点。 Graph.add_edge(u_of_edge, v_of_edge, **attr)
' S& w% ~: {) V# _Graph.add_edges_from(ebunch_to_add, **attr)
6 d# [+ J/ y2 y9 N+ VGraph.add_weighted_edges_from(ebunch_to_add, weight=‘weight’, **attr)
& k8 z `, _' j% ?7 f
2 l, Y! c1 Q5 N# 边(edge)的操作# \2 c* P/ e8 T6 ]1 R+ i
# 向图中添加边* r z1 n, i1 K, I" p; H; D# t% B
G1.add_edge(1,5) # 向 G1 添加边,并自动添加图中没有的顶点
: u! k5 w: N3 I: R+ ]' F8 pG1.add_edge(0,10, weight=2.7) # 向 G1 添加边,并设置边的属性 L5 J5 I; P4 I; w- w9 F. G& j. j
G1.add_edges_from([(1,2,{'weight':0}), (2,3,{'color':'blue'})]) # 向图中添加边,并设置属性2 J2 t0 o8 A( ]) T$ u* e8 p* r
G1.add_edges_from([(3,6),(1,2),(6,7),(5,10),(0,1)]) # 向图中添加多条边
' J( E5 n( Y1 \ G5 p- }G1.add_weighted_edges_from([(1,2,3.6),[6,12,0.5]]) # 向图中添加多条赋权边: (node1,node2,weight)! D; N$ b* a2 ^
print(G1.nodes()) # 查看顶点2 F. E8 g, s8 @6 A- ?
# [2, 3, 0, 6, 10, 12, 1, 5, 7] # 自动添加了图中没有的顶点
) @7 o7 N4 A6 d
8 g4 h- v" a0 `& ]( }2 S: U# 从图中删除边. q6 r: Y: I" q* U l' V
G1.remove_edge(0,1) # 从图中删除边 0-1
" \6 E1 b8 h PG1.remove_edges_from([(2,3),(1,5),(6,7)]) # 从图中删除多条边+ u/ c( Z+ F5 Q
2 o2 R' z2 j; u, ^/ X. t
# 查看 边和边的属性
9 _( D; I0 M0 X s5 [* A4 mprint(G1.edges) # 查看所有的边
9 L F H0 c- Z$ N# s, B; D3 ~[(2, 1), (3, 6), (0, 10), (6, 12), (10, 5)]
( \, ?* m |5 A0 K/ Kprint(G1.get_edge_data(1,2)) # 查看指定边的属性
7 \, K% a$ y: ^) V# {'weight': 3.6}1 M# e& R! s, v. c
print(G1[1][2]) # 查看指定边的属性1 O& u9 u5 @, | R& u6 z+ v
# {'weight': 3.6}. Z/ V$ H' S. }9 W ~; N& k- s5 h0 w
print(G1.edges(data=True)) # 查看所有边的属性
, H! X. j6 B5 w- i7 M% ?8 \# [(2, 1, {'weight': 3.6}), (3, 6, {}), (0, 10, {'weight': 2.7}), (6, 12, {'weight': 0.5}), (10, 5, {})]
w" K: v3 D7 }
4 k2 |. K. A4 j+ I7 \( v. x# b' R3 a, U2.2.4 查看图、顶点和边的信息
: y) x) M4 l n* K# o* F6 ?2 W3 C' l* G- i8 C R" H a
# 查看图、顶点和边的信息/ M' [# D: B9 d- ~
print(G1.nodes) # 返回所有的顶点 [node1,...]
! m. o8 b9 K9 [% i3 g# Y# [2, 3, 0, 6, 10, 12, 1, 5, 7]! V, p+ K9 H. s" P' _4 y. c
print(G1.edges) # 返回所有的边 [(node1,node2),...]
& C* T2 z4 {; \: z! m. c# [(2, 1), (3, 6), (0, 10), (6, 12), (10, 5)]
$ C, C$ h9 f' C; @. v# } {4 x3 Jprint(G1.degree) # 返回各顶点的度 [(node1,degree1),...]
* v7 z5 N: M) q( W# [(2, 1), (3, 1), (0, 1), (6, 2), (10, 2), (12, 1), (1, 1), (5, 1), (7, 0)]( A4 N+ t _3 _& ]9 Z8 r( s: c# Y! M
print(G1.number_of_nodes()) # 返回顶点的数量# J% l3 u/ ~ _: I. S, \
# 9
/ B* G' t0 R2 B! z$ Hprint(G1.number_of_edges()) # 返回边的数量
3 \$ O' }8 e. u# k# 50 K# x# H: d' b9 m/ W/ i
print(G1[10]) # 返回与指定顶点相邻的所有顶点的属性 \1 Y( K9 P, P$ c5 {
# {0: {'weight': 2.7}, 5: {}}
2 h9 m" f/ {6 ^: _% y% _. P0 v6 uprint(G1.adj[10]) # 返回与指定顶点相邻的所有顶点的属性
! c5 T8 x4 w" C% H# {0: {'weight': 2.7}, 5: {}}6 Y! ^8 X6 ]+ D, h3 w; }: y3 Q) g
print(G1[1][2]) # 返回指定边的属性
7 o, S% _2 W+ F3 L, c# {'weight': 3.6}
" |; f" ]( a+ ~$ n/ r+ ], uprint(G1.adj[1][2]) # 返回指定边的属性; M* G( @* N i! `+ b# N
# {'weight': 3.6}
* `: x7 t- h) P, Sprint(G1.degree(10)) # 返回指定顶点的度
# K9 L& Y" e5 T$ ^: |# 2
0 `8 |3 D1 l3 d5 M: O! h4 v
' U; z! ~9 A- L- uprint('nx.info:',nx.info(G1)) # 返回图的基本信息" k/ z7 f8 {* |# n6 d9 s2 n
print('nx.degree:',nx.degree(G1)) # 返回图中各顶点的度( \, c6 z3 i5 p6 p; m1 `
print('nx.density:',nx.degree_histogram(G1)) # 返回图中度的分布8 `# _ j% ~3 B: e. ]1 }
print('nx.pagerank:',nx.pagerank(G1)) # 返回图中各顶点的频率分布
6 F. I6 m! {) }, W# I w3 U4 W% A* j) K8 v
2 G6 r- _4 ?7 ]
) N: V/ z0 d1 ]1 K6 @- z* ?2 O
+ F6 `; C9 ?' L8 z2.3 图的属性和方法图的方法+ A1 C" n0 v; d* K
: z3 M8 {9 W: G! r% W. s9 j7 ?方法 说明
4 L: R. w/ P. ?% ?+ u7 a8 O6 c: AG.has_node(n) 当图 G 中包括顶点 n 时返回 True6 v, Z) ?; b5 J
G.has_edge(u, v) 当图 G 中包括边 (u,v) 时返回 True
+ n2 B8 n2 m' C2 V0 sG.number_of_nodes() 返回 图 G 中的顶点的数量
. W% Z T8 `! ^# _; W1 ]G.number_of_edges() 返回 图 G 中的边的数量
4 m4 R0 R* O& {! Y- Z+ ^- E6 Q2 o% S/ QG.number_of_selfloops() 返回 图 G 中的自循环边的数量
( r, E2 x4 x3 zG.degree([nbunch, weight]) 返回 图 G 中的全部顶点或指定顶点的度) t3 ?0 X, [% ^5 i# ]
G.selfloop_edges([data, default]) 返回 图 G 中的全部的自循环边
1 @& x) |4 \% w" O' CG.subgraph([nodes]) 从图 G1中抽取顶点[nodes]及对应边构成的子图% w1 l, x5 M. D+ ], H- c
union(G1,G2) 合并图 G1、G2
3 ?9 h' w( l( P+ q7 i7 S" _nx.info(G) 返回图的基本信息
* A0 x) `/ h7 b, Unx.degree(G) 返回图中各顶点的度
. v2 X2 H3 ~! b% qnx.degree_histogram(G) 返回图中度的分布2 m$ p" J; F) D4 b/ h- y
nx.pagerank(G) 返回图中各顶点的频率分布
3 U, Z% a) f8 Snx.add_star(G,[nodes],**attr) 向图 G 添加星形网络$ L% s/ \& A& S1 R" e) A1 l
nx.add_path(G,[nodes],**attr) 向图 G 添加一条路径# q7 X6 _ @% p! A
nx.add_cycle(G,[nodes],**attr) 向图 G 添加闭合路径# ]' p8 H" F5 h7 V. p) b
3 I% a# ^% O1 A J! T6 y
. Y6 `( o3 M. C8 e" \2 u
例程:
3 q3 J2 U5 N7 v4 i" h9 ^- SG1.clear() # 清空图G1
- h0 }+ O0 I( q, v! U5 _nx.add_star(G1, [1, 2, 3, 4, 5], weight=1) # 添加星形网络:以第一个顶点为中心
1 T" V7 \. |5 X# [(1, 2), (1, 3), (1, 4), (1, 5)]
- O6 y# J3 _, P7 j2 y' b* Fnx.add_path(G1, [5, 6, 8, 9, 10], weight=2) # 添加路径:顺序连接 n个节点的 n-1条边3 K: Q/ u9 m# L- L2 S7 L
# [(5, 6), (6, 8), (8, 9), (9, 10)]
8 i. o6 j& p: Z% v& Anx.add_cycle(G1, [7, 8, 9, 10, 12], weight=3) # 添加闭合回路:循环连接 n个节点的 n 条边
7 b+ `. s; ^& Z7 |5 ` e8 z! o" R# [(7, 8), (7, 12), (8, 9), (9, 10), (10, 12)] ?; i: L$ l$ {
print(G1.nodes) # 返回所有的顶点 [node1,...]6 T- J& W4 ~$ } |1 ^
nx.draw_networkx(G1)
: L2 Z% ?* ]! @. splt.show(), J2 z: H C, S: R: b
- l! ^# z' Q, q4 n- k3 T1 s; K( UG2 = G1.subgraph([1, 2, 3, 8, 9, 10])+ V% T8 C# a7 l* z( H
G3 = G1.subgraph([4, 5, 6, 7])$ U6 y3 L5 f! s. @! f) n$ m- z
G = nx.union(G2, G3)
) }- _) }, Y0 ^- _8 A1 C$ P7 }print(G.nodes) # 返回所有的顶点 [node1,...]
. }' r8 L2 G' e* j$ G9 S+ t. i# [1, 2, 3, 8, 9, 10, 4, 5, 6, 7]+ ?' x1 W2 ]+ z, Y r! D9 z
9 G; h! {' K2 A+ R: g
, P4 A# D4 [6 A# t, a$ k
3、图的绘制与分析3.1 图的绘制
. ^( q. a& b7 L0 S: i( h( Y, p* R可视化是图论和网络问题中很重要的内容。NetworkX 在 Matplotlib、Graphviz 等图形工具包的基础上,提供了丰富的绘图功能。
. O( h3 E* K3 X. |3 o5 J, ^ g
7 X: c5 @' q( [1 S) Z本系列拟对图和网络的可视化作一个专题,在此只简单介绍基于 Matplotlib 的基本绘图函数。基本绘图函数使用字典提供的位置将节点放置在散点图上,或者使用布局函数计算位置。% ?3 J# l ]. H- P
! o% R! Z$ w- q3 w' M# |# C! [1 T1 H方法 说明' P# W0 a, o1 d. J+ ~& h+ I
draw(G[,pos,ax]) 基于 Matplotlib 绘制 图 G
0 z6 Z. u; C* Sdraw_networkx(G[, pos, arrows, with_labels]) 基于 Matplotlib 绘制 图 G
6 u% {5 I4 V0 kdraw_networkx_nodes(G, pos[, nodelist, . . . ]) 绘制图 G 的顶点4 x* e$ s# c" E. C% J* _2 b
draw_networkx_edges(G, pos[, edgelist, . . . ]) 绘制图 G 的边( R7 V7 b2 E1 ^& R6 m
draw_networkx_labels(G, pos[, labels, . . . ]) 绘制顶点的标签
/ ]/ h; L0 k$ z. @5 ~' }draw_networkx_edge_labels(G, pos[, . . . ]) 绘制边的标签
/ p$ \. ?+ a, d" r' H1 }$ k# l
[" A9 w% O+ ?, q( x' f
O" S- _4 C# l1 Q, R; |其中,nx.draw() 和 nx.draw_networkx() 是最基本的绘图函数,并可以通过自定义函数属性或其它绘图函数设置不同的绘图要求。
8 Z% T/ R9 u% \) i2 |4 ]8 Kdraw(G, pos=None, ax=None, **kwds) draw_networkx(G, pos=None, arrows=True, with_labels=True, **kwds)
j! i) d. O$ y( y常用的属性定义如下:, V7 k, p) Q1 l. ~: Z0 t
1 b' f3 c7 {9 {; c& _0 E
‘node_size’:指定节点的尺寸大小,默认300% j6 @: l4 ?# f r! K
‘node_color’:指定节点的颜色,默认红色
8 I$ `) M. F0 j6 h# \; Y9 G‘node_shape’:节点的形状,默认圆形
( Q, o* ?+ [# q+ }'‘alpha’:透明度,默认1.0,不透明
# F9 r: s- ?: n- l, |4 U‘width’:边的宽度,默认1.0
3 n/ \7 C$ `# K" n‘edge_color’:边的颜色,默认黑色: G6 p6 _% e7 z; o2 Y" P7 R
‘style’:边的样式,可选 ‘solid’、‘dashed’、‘dotted’、‘dashdot’* U0 O& ^7 j# p/ A+ ]
‘with_labels’:节点是否带标签,默认True" w |7 ~' \) G5 a
‘font_size’:节点标签字体大小,默认12* ?% s# m) M d; v
‘font_color’:节点标签字体颜色,默认黑色
4 W8 ~6 Y! _6 y: S. I
) f* O# _% l3 z' q, \1 z![]()
/ m7 W1 P/ g3 t/ i2 |* o3.2 图的分析NetwotkX 提供了图论函数对图的结构进行分析- O9 X: | ^! v [$ r& N
子图' r# a R% x4 W; D
- 子图是指顶点和边都分别是图 G 的顶点的子集和边的子集的图。
- subgraph()方法,按顶点从图 G 中抽出子图。例程如前。. g( T6 ?( n5 Y
连通子图! ]* v% q$ J; D& x. L
/ g# f& h" T o. n9 v
- 如果图 G 中的任意两点间相互连通,则 G 是连通图。
- [color=rgba(0, 0, 0, 0.749019607843137)]connected_components()方法,返回连通子图的集合。( E% F3 t' b% U4 N/ Y# G/ D9 v
[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}]
( w9 M: ?0 u% i2 @. D
/ U) c" a6 C) r' t& b" a' c$ E8 B* `) Q. e
) Z/ n2 e$ o) Y0 q. y( L
1 W. I; \) e' C
|