Python小白的数学建模课-图论的基本概念5 e' i; z6 y* Z. Y+ X6 y$ ^" F* Z
0 M4 m+ R. a! x" a- 图论中所说的图,不是图形图像或地图,而是指由顶点和边所构成的图形结构。
- 图论不仅与拓扑学、计算机数据结构和算法密切相关,而且正在成为机器学习的关键技术。
- 本系列结合数学建模的应用需求,来介绍 NetworkX 图论与复杂网络工具包的基本功能和典型算法。
+ x$ d" ~: c2 G( e/ X& D9 D" T
+ j9 Z r1 w7 @4 v \) ]0 m* }1. 图论1.1 图论是什么* V* ]9 _: Y4 A& W8 F; r
图论〔Graph Theory〕以图为研究对象,是离散数学的重要内容。图论不仅与拓扑学、计算机数据结构和算法密切相关,而且正在成为机器学习的关键技术。1 R+ m! u( J4 S: n! w9 ~1 H
- N9 Q" D0 h. n
图论中所说的图,不是指图形图像(image)或地图(map),而是指由顶点(vertex)和连接顶点的边(edge)所构成的关系结构。
# H$ `$ _5 ?3 i7 l' H& n" E) o3 q* S0 b5 c; t* e a
图提供了一种处理关系和交互等抽象概念的更好的方法,它还提供了直观的视觉方式来思考这些概念。
7 y& x4 O/ i& s; h7 Y. K" ~1 z9 ?; ?( r- V3 p! _
1.2 NetworkX 工具包$ Z& \) z- I8 h( o
NetworkX 是基于 Python 语言的图论与复杂网络工具包,用于创建、操作和研究复杂网络的结构、动力学和功能。
: Z- R$ U; _" b
3 _6 \3 G& n- U1 M, r6 ^7 ~NetworkX 可以以标准和非标准的数据格式描述图与网络,生成图与网络,分析网络结构,构建网络模型,设计网络算法,绘制网络图形。 Y1 p \ c$ p* v7 }
2 V% H& |4 g# M# ?, x [8 U) Y. y( v
NetworkX 提供了图形的类、对象、图形生成器、网络生成器、绘图工具,内置了常用的图论和网络分析算法,可以进行图和网络的建模、分析和仿真。
/ t2 H9 N/ x2 t) D0 P, G7 p* x. \, L. t6 ?$ ?. r
NetworkX 的功能非常强大和庞杂,所涉及内容远远、远远地超出了数学建模的范围,甚至于很难进行系统的概括。本系列结合数学建模的应用需求,来介绍 NetworkX 图论与复杂网络工具包的基本功能和典型算法。
p* Y f% g3 {: a
! T" O$ y) b9 `: z2 z/ E6 \$ y X3 g$ o) y
2、图、顶点和边的创建与基本操作 n4 C8 w9 `% o. p5 n
图由顶点和连接顶点的边构成,但与顶点的位置、边的曲直长短无关。 Networkx 支持创建简单无向图、有向图和多重图;内置许多标准的图论算法,节点可为任意数据;支持任意的边值维度,功能丰富,简单易用。 2.1 图的基本概念
4 b! J! }) `! d0 [/ W# a% I图(Graph):图是由若干顶点和连接顶点的边所构成关系结构。
$ ~2 j6 `* s2 Z2 K, w顶点(Node):图中的点称为顶点,也称节点。0 u. u- i* @8 _. D5 p9 t+ K
边(Edge):顶点之间的连线,称为边。1 I- v) V, b: W0 r# [1 X9 y
平行边(Parallel edge):起点相同、终点也相同的两条边称为平行边。* D [5 e! {0 x8 h; W8 c- P3 L8 Y
循环(Cycle):起点和终点重合的边称为循环。8 s2 M& x& W1 S; k# n- l
有向图(Digraph):图中的每条边都带有方向,称为有向图。
$ K# Y9 z; ~# ]: o: ]无向图(Undirected graph):图中的每条边都没有方向,称为无向图。
$ Q: ?9 X- R' z5 f赋权图(Weighted graph):图中的每条边都有一个或多个对应的参数,称为赋权图。该参数称为这条边的权,权可以用来表示两点间的距离、时间、费用。
& O7 n) H8 p$ t$ H+ M" O度(Degree):与顶点相连的边的数量,称为该顶点的度。. ]7 `! L3 T% n [ \& d
1 T0 A" w' Q3 E2.2 图、顶点和边的操作+ e$ m& A# g2 e1 H9 U( X+ c: c. e# Y
Networkx很容易创建图、向图中添加顶点和边、从图中删除顶点和边,也可以查看、删除顶点和边的属性。
; E+ G- u* I0 k& z& C' g! ^! l4 c, J# p
2.2.1 图的创建Graph() 类、DiGraph() 类、MultiGraph() 类和 MultiDiGraph() 类分别用来创建:无向图、有向图、多图和有向多图。定义和例程如下:8 ^& J& B8 R4 O
' P; U! ^: D& P2 P" a2 H& N; N
class Graph(incoming_graph_data=None, **attr)8 Q5 y* z+ x ~0 X' _2 F5 s
import networkx as nx # 导入 NetworkX 工具包
% F8 @: V n( C% G/ g5 a
0 ~' d* H' Q% k" M# 创建 图; P$ O8 c0 y1 Q. b; T
G1 = nx.Graph() # 创建:空的 无向图
" A2 w5 N5 Z. w8 i8 g- ~G2 = nx.DiGraph() #创建:空的 有向图/ i/ F b7 u9 T% X" g) n; n+ |
G3 = nx.MultiGraph() #创建:空的 多图
2 n1 I$ B9 f" V- w1 oG4 = nx.MultiDiGraph() #创建:空的 有向多图8 j0 [) b1 y0 k6 a
; ~! E# \3 A, ~3 B+ e% q* y0 T$ f
7 G4 N# X; Z# P5 c, Z# D2 D2.2.2 顶点的添加、删除和查看/ O" C" k) C3 {$ r
图的每个顶点都有唯一的标签属性(label),可以用整数或字符类型表示,顶点还可以自定义任意属性。 顶点的常用操作:添加顶点,删除顶点,定义顶点属性,查看顶点和顶点属性。定义和例程如下:
7 }( J5 \! x* l; J% ?Graph.add_node(node_for_adding, **attr)) f0 e' f* _5 f/ N8 v3 h
Graph.add_nodes_from(nodes_for_adding, **attr)5 z M, ?& |9 \& Q6 V# j n: K
Graph.remove_node(n)" M0 }/ s. ~; v/ `
Graph.remove_nodes_from(nodes), G5 ~& T: k+ g$ C3 h2 Q: Z! \! s
) ^4 O) N7 G( D5 k N. Y
# 顶点(node)的操作/ [& P, U/ ^. }1 T
# 向图中添加顶点
0 u+ M) P1 {$ t+ {8 |2 l& C! f' BG1.add_node(1) # 向 G1 添加顶点 10 F1 C6 V! N% h' j/ I7 L- U4 o
G1.add_node(1, name='n1', weight=1.0) # 添加顶点 1,定义 name, weight 属性
2 L: W- |& b2 QG1.add_node(2, date='May-16') # 添加顶点 2,定义 time 属性5 `8 W) w% k( s
G1.add_nodes_from([3, 0, 6], dist=1) # 添加多个顶点,并定义属性: l2 H, K7 p5 s" {5 C9 X
G1.add_nodes_from(range(10, 15)) # 向图 G1 添加顶点 10~14
( p5 v- E' z* J+ E' N
h* E, K" g; w3 z. l9 r4 Y# 查看顶点和顶点属性
# z% H/ E3 q% H( n* }print(G1.nodes()) # 查看顶点列表
5 J8 W& z6 z/ K$ A2 A. ?4 o# [1, 2, 3, 0, 6, 10, 11, 12, 13, 14]
- A9 d% J* H) j2 b6 @, dprint(G1._node) # 查看顶点属性
- Q1 o6 |0 m4 s) Q6 N+ b# {1: {'name': 'n1', 'weight': 1.0}, 2: {'date': 'May-16'}, 3: {'dist': 1}, 0: {'dist': 1}, 6: {'dist': 1}, 10: {}, 11: {}, 12: {}, 13: {}, 14: {}}1 f& C7 ?' p V) q( K
4 u7 X0 v/ C2 L: {1 ^# 从图中删除顶点7 F, N* H0 e9 V5 W* F6 @( V
G1.remove_node(1) # 删除顶点
% W/ m4 b2 X0 w/ W) ]' ?+ v7 y& fG1.remove_nodes_from([1, 11, 13, 14]) # 通过顶点标签的 list 删除多个顶点3 ~5 H8 k/ |" ~7 r# I" M
print(G1.nodes()) # 查看顶点0 Z( _+ B2 T! W4 V" v
# [2, 3, 0, 6, 10, 12] # 顶点列表
' S7 A& |7 V& H3 Y3 y/ F6 N7 x0 O2.2.3 边的添加、删除和查看边是两个顶点之间的连接,在 NetworkX 中 边是由对应顶点的名字的元组组成 e=(node1,node2)。边可以设置权重、关系等属性。 边的常用操作:添加边,删除边,定义边的属性,查看边和边的属性。向图中添加边时,如果边的顶点是图中不存在的,则自动向图中添加该顶点。 Graph.add_edge(u_of_edge, v_of_edge, **attr)
, B) u# K. l X2 \) `% ~! L! AGraph.add_edges_from(ebunch_to_add, **attr)' [* \' s" g7 m
Graph.add_weighted_edges_from(ebunch_to_add, weight=‘weight’, **attr)' o( S. Y- U2 }5 V$ d
1 S c3 k/ ?: j7 t( s9 ~# 边(edge)的操作
: k6 I) ]; U3 @' \$ B, k# 向图中添加边
4 b; T9 \5 C( A3 h/ W( ~+ cG1.add_edge(1,5) # 向 G1 添加边,并自动添加图中没有的顶点
/ M, Q: `5 X' g) W7 p2 i' c( t! l! _! y& JG1.add_edge(0,10, weight=2.7) # 向 G1 添加边,并设置边的属性
: H" r0 ^ F9 ]3 F2 q# P. Z" JG1.add_edges_from([(1,2,{'weight':0}), (2,3,{'color':'blue'})]) # 向图中添加边,并设置属性& b4 F0 I; U3 y4 _
G1.add_edges_from([(3,6),(1,2),(6,7),(5,10),(0,1)]) # 向图中添加多条边
% |: o5 ^3 ~3 pG1.add_weighted_edges_from([(1,2,3.6),[6,12,0.5]]) # 向图中添加多条赋权边: (node1,node2,weight)
2 y- U4 S* `: V: F) J8 g0 }print(G1.nodes()) # 查看顶点: p; g+ A4 q7 g0 p! X6 U' l
# [2, 3, 0, 6, 10, 12, 1, 5, 7] # 自动添加了图中没有的顶点
; t* R- s' [+ b/ j. F: {5 N$ w
- H4 C# x5 |6 B4 X* @# 从图中删除边
' o( H% H# E7 ~3 q% c: [; {7 cG1.remove_edge(0,1) # 从图中删除边 0-1
' e5 K0 W) I# e" P1 z+ |2 x7 aG1.remove_edges_from([(2,3),(1,5),(6,7)]) # 从图中删除多条边
0 {; o$ ]% q$ @5 S; J
: N" b- D& u0 s9 S$ e, D# 查看 边和边的属性2 r8 q7 y8 O; b9 ^
print(G1.edges) # 查看所有的边
% ?1 Z. U0 E! l: I* N# b[(2, 1), (3, 6), (0, 10), (6, 12), (10, 5)]
* F W, {; R/ V4 [! }print(G1.get_edge_data(1,2)) # 查看指定边的属性6 Z0 o L( `1 Q" d
# {'weight': 3.6}9 O0 s6 f" D+ Q' J1 G4 f
print(G1[1][2]) # 查看指定边的属性, X: W3 r) X" F* ]
# {'weight': 3.6}6 D' B; A1 R% G6 L" a
print(G1.edges(data=True)) # 查看所有边的属性- J5 {, W) T( O6 F! g8 b1 m7 I* c
# [(2, 1, {'weight': 3.6}), (3, 6, {}), (0, 10, {'weight': 2.7}), (6, 12, {'weight': 0.5}), (10, 5, {})]0 w; c Z" i( G1 S
/ c& w$ {( Q. I2 w4 [& ^
2.2.4 查看图、顶点和边的信息9 f O+ D3 [* p; T, ^# v
" y* g2 M& q0 w' N
# 查看图、顶点和边的信息
. U! R$ ~# r7 g) I: a6 yprint(G1.nodes) # 返回所有的顶点 [node1,...]2 t) Q9 L- ?" @, l: N1 o- _
# [2, 3, 0, 6, 10, 12, 1, 5, 7]- r8 F2 N( ^& w! x: P: }# `
print(G1.edges) # 返回所有的边 [(node1,node2),...]0 Y' H8 ]* t- p9 ?, J
# [(2, 1), (3, 6), (0, 10), (6, 12), (10, 5)]
1 Z" O+ Q* |7 Q/ W% Z4 Bprint(G1.degree) # 返回各顶点的度 [(node1,degree1),...]
7 Q7 u2 v3 m4 t9 Q# [(2, 1), (3, 1), (0, 1), (6, 2), (10, 2), (12, 1), (1, 1), (5, 1), (7, 0)]
* n9 N( [! w5 jprint(G1.number_of_nodes()) # 返回顶点的数量
6 X _: g. a3 V1 ?# 9; |8 H: M7 k0 J' P4 d
print(G1.number_of_edges()) # 返回边的数量
- B5 O: d. ^7 |# 5" Q+ d9 M$ U: r8 }' L
print(G1[10]) # 返回与指定顶点相邻的所有顶点的属性
}' ~+ Z: G0 H, C( x. c# {0: {'weight': 2.7}, 5: {}}# G+ ~, d% b- j. `0 E1 d* H4 q* N& u
print(G1.adj[10]) # 返回与指定顶点相邻的所有顶点的属性
: @) Y% H4 |4 P1 V# {0: {'weight': 2.7}, 5: {}}6 S8 |2 v2 z T" M- b
print(G1[1][2]) # 返回指定边的属性
+ k$ u) S8 [/ z; g% ]# {'weight': 3.6}
% c4 y( ~0 V% h/ V+ d1 l0 xprint(G1.adj[1][2]) # 返回指定边的属性5 t9 T# L2 ~$ N1 c
# {'weight': 3.6}& o$ Z8 t6 [ I
print(G1.degree(10)) # 返回指定顶点的度$ o' H1 x5 X. w+ U" e/ l
# 2& [! @4 r7 V% a2 H9 X2 F( Z
" D) u4 u, [5 e4 T) bprint('nx.info:',nx.info(G1)) # 返回图的基本信息
: O- n7 d* o' u3 ]% Tprint('nx.degree:',nx.degree(G1)) # 返回图中各顶点的度9 j% z" R; }1 X% A# Z0 f
print('nx.density:',nx.degree_histogram(G1)) # 返回图中度的分布4 ~+ q2 a$ S% n% s; y% ?
print('nx.pagerank:',nx.pagerank(G1)) # 返回图中各顶点的频率分布
- a+ U+ t9 q7 q7 Q" D: o" m0 N- a& q4 o p% s, p" n$ S4 N
* V2 B& n8 g9 t! m0 _# }) c/ |+ J/ O2 H9 }8 z
3 Z7 R W d( u
?+ n6 u4 q) Z! d" k2 g0 k
2.3 图的属性和方法图的方法
+ M& C! Y2 [, j$ D- k& ]. `" ^
. x0 h0 ^3 s6 K1 l7 d7 j& J方法 说明3 [1 {2 D$ q" m
G.has_node(n) 当图 G 中包括顶点 n 时返回 True# B! }4 h; P: \. v& T# T
G.has_edge(u, v) 当图 G 中包括边 (u,v) 时返回 True+ ~5 ]% T5 X5 c5 j8 ?1 x1 h0 c) h
G.number_of_nodes() 返回 图 G 中的顶点的数量) j4 h6 K3 ^ F4 U- f- z2 r) ]
G.number_of_edges() 返回 图 G 中的边的数量
" |+ u; r6 Q; x; l" R3 eG.number_of_selfloops() 返回 图 G 中的自循环边的数量. X2 R8 E! N; F2 u
G.degree([nbunch, weight]) 返回 图 G 中的全部顶点或指定顶点的度7 z& O/ ]1 K5 N- ?3 U7 f
G.selfloop_edges([data, default]) 返回 图 G 中的全部的自循环边
+ ~* y; X) C0 W2 U3 k; AG.subgraph([nodes]) 从图 G1中抽取顶点[nodes]及对应边构成的子图
* L9 ]" v! D6 u" \ W% Yunion(G1,G2) 合并图 G1、G2
( f0 p& i& a- ~) [1 t8 n4 n% |nx.info(G) 返回图的基本信息, n( {3 x1 G0 a5 I0 ]) ]8 H) X
nx.degree(G) 返回图中各顶点的度
6 _- S C9 k. ~/ H6 snx.degree_histogram(G) 返回图中度的分布
' |; G& \( D* w8 f0 `nx.pagerank(G) 返回图中各顶点的频率分布
# \% G- h) K$ Q$ x9 {* d2 Znx.add_star(G,[nodes],**attr) 向图 G 添加星形网络
- H3 I+ e2 r( Y: E+ Vnx.add_path(G,[nodes],**attr) 向图 G 添加一条路径7 B+ a4 J* ~; g2 K- Q" s
nx.add_cycle(G,[nodes],**attr) 向图 G 添加闭合路径
5 X' r- } n( k2 G# n4 p% _/ i0 q; I
" n$ R- I' t/ j例程:
' y5 O2 m C+ jG1.clear() # 清空图G1# }- b' y u, j' p9 o" v2 o
nx.add_star(G1, [1, 2, 3, 4, 5], weight=1) # 添加星形网络:以第一个顶点为中心 [& F# ?) k4 U+ X: S9 O$ d
# [(1, 2), (1, 3), (1, 4), (1, 5)]' V6 W) F4 K7 y' i) p) M
nx.add_path(G1, [5, 6, 8, 9, 10], weight=2) # 添加路径:顺序连接 n个节点的 n-1条边
/ r( l$ i4 G. l( N# [(5, 6), (6, 8), (8, 9), (9, 10)]
N- n8 ]1 e/ d. fnx.add_cycle(G1, [7, 8, 9, 10, 12], weight=3) # 添加闭合回路:循环连接 n个节点的 n 条边( u! K$ z @$ ]0 @+ ^
# [(7, 8), (7, 12), (8, 9), (9, 10), (10, 12)]
2 \7 V4 b3 t0 R* F h0 T2 aprint(G1.nodes) # 返回所有的顶点 [node1,...]0 J& S5 L& b( v& o1 p6 w
nx.draw_networkx(G1)
) y6 E9 i! N t( _8 M1 L3 splt.show()
+ k5 {0 v: Y. I9 i, y) n$ t
9 y9 p: g) I3 w0 O p! O6 w0 gG2 = G1.subgraph([1, 2, 3, 8, 9, 10])
' a$ ]6 v/ M2 k9 z tG3 = G1.subgraph([4, 5, 6, 7])
; K: S. [3 `8 \' w0 d1 n* LG = nx.union(G2, G3)
, i9 o o& O. C) iprint(G.nodes) # 返回所有的顶点 [node1,...]
% [! g+ l6 U8 s' r3 a" R# [1, 2, 3, 8, 9, 10, 4, 5, 6, 7]
# L& O2 K5 F9 O }% J6 A
_) o; o7 c& d6 a/ \0 N+ h* O) s! ]( T' q# [5 T+ K
3、图的绘制与分析3.1 图的绘制
$ [9 F" u' }4 Z/ G1 j6 F2 B1 k. a! }可视化是图论和网络问题中很重要的内容。NetworkX 在 Matplotlib、Graphviz 等图形工具包的基础上,提供了丰富的绘图功能。
$ h F) i! z0 e4 U- ?% U
; @# _; [9 W$ r @本系列拟对图和网络的可视化作一个专题,在此只简单介绍基于 Matplotlib 的基本绘图函数。基本绘图函数使用字典提供的位置将节点放置在散点图上,或者使用布局函数计算位置。
7 s) i% q9 A: Q! P% Z( }( k0 n) K p4 B3 T' g
方法 说明: K/ P1 T% W. V" E9 D# E
draw(G[,pos,ax]) 基于 Matplotlib 绘制 图 G
& v" w: x g# F# z: ?$ }! h& ddraw_networkx(G[, pos, arrows, with_labels]) 基于 Matplotlib 绘制 图 G6 c2 r; |& K* y' {8 ^4 ^
draw_networkx_nodes(G, pos[, nodelist, . . . ]) 绘制图 G 的顶点
0 N" k+ r, w( a3 }; Idraw_networkx_edges(G, pos[, edgelist, . . . ]) 绘制图 G 的边# {; S2 D [- C7 d# I
draw_networkx_labels(G, pos[, labels, . . . ]) 绘制顶点的标签
# J4 s' m, ?5 h7 B' F( Ydraw_networkx_edge_labels(G, pos[, . . . ]) 绘制边的标签
2 F2 m; e" U+ v1 T W' a8 V/ `& X* }( \. }8 [
. w9 V( ~4 z* q9 \/ ?- {9 S! `
其中,nx.draw() 和 nx.draw_networkx() 是最基本的绘图函数,并可以通过自定义函数属性或其它绘图函数设置不同的绘图要求。
. L7 a6 Z* H6 e" d4 G5 Qdraw(G, pos=None, ax=None, **kwds) draw_networkx(G, pos=None, arrows=True, with_labels=True, **kwds)
/ O/ I4 s% V! ~) ~9 |常用的属性定义如下:) c2 l4 V2 j# w. Y4 x2 \
2 \( i# W! v; O5 U {% V \8 N! j‘node_size’:指定节点的尺寸大小,默认300
6 |( X5 ~, I5 ?& Z U4 H; r G‘node_color’:指定节点的颜色,默认红色
9 ~3 g+ s# V0 @3 Z‘node_shape’:节点的形状,默认圆形. s( R g! C" a
'‘alpha’:透明度,默认1.0,不透明
) p- L( s+ j+ c‘width’:边的宽度,默认1.00 S. ]+ R2 n: i+ W
‘edge_color’:边的颜色,默认黑色
6 C- x3 N1 @4 M5 M‘style’:边的样式,可选 ‘solid’、‘dashed’、‘dotted’、‘dashdot’+ C4 X. S4 g5 I- \& k0 t
‘with_labels’:节点是否带标签,默认True
8 q e' k5 H' Z5 L* \; k7 J" B‘font_size’:节点标签字体大小,默认12 B* \- k" z- ^. |
‘font_color’:节点标签字体颜色,默认黑色
9 }) ]3 {( w7 r
; [; A; R4 ^* t& X& L* `! s% b# z# d
3.2 图的分析NetwotkX 提供了图论函数对图的结构进行分析
/ \4 m+ u! y; s子图
) X, x1 y" I& j& J- 子图是指顶点和边都分别是图 G 的顶点的子集和边的子集的图。
- subgraph()方法,按顶点从图 G 中抽出子图。例程如前。
# }9 d; M& g# ^. n 连通子图
) k! ^' I6 h5 f, e2 p
K: ]8 I8 l! `$ K5 \1 V/ G( K0 r- 如果图 G 中的任意两点间相互连通,则 G 是连通图。
- [color=rgba(0, 0, 0, 0.749019607843137)]connected_components()方法,返回连通子图的集合。
- c7 z' x# J/ S+ o9 s[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}]
! e( Z# F% z3 h( ?( H5 P* v" S$ ^ ; a+ Y( y5 \; o* N: f) ~# ]' _
" r, @3 v0 W( g9 x, ~. x
7 P& X2 V; U% k: ?* Q. e; s# e+ \6 g2 S8 @7 i8 T& Q7 D9 J8 M) g
|