数学建模社区-数学中国
标题:
[数据结构与算法]16 什么,图这种数据结构把你难住了?!
[打印本页]
作者:
杨利霞
时间:
2020-4-26 15:17
标题:
[数据结构与算法]16 什么,图这种数据结构把你难住了?!
[数据结构与算法]16 什么,图这种数据结构把你难住了?!
" L6 }8 L: p5 t/ M4 X, N9 G
你是不是和我一样,在学习数据结构与算法时,了解了一下图这种数据结构之后,根本不知道它的用武之地在哪里?
% Y' k& J0 |1 R/ h" B, m
在我查了资料之后,现在我可以跟你讲讲,图可以这么用!
' j0 Y# N i" g+ {: g6 Z
e3 _- c; K3 I0 F0 O3 _$ O
概念介绍
5 s0 e6 p3 P' h/ m. q
6 r. T: c$ D& L$ h1 a T
先来了解一下什么是图.
: | U; E5 t1 ?, L4 h3 r; ?
图,是一种非线性表数据结构.
) P* l: D; l3 B4 M
那么你可能会问了,什么是线性表结构哇,我怎么区别一种数据结构是线性的,还是非线性的呢.
% u+ g, l$ d5 J- Q
哈哈,还好我机智,在这篇文章之前就写了一篇文章来介绍,如果还有疑问,楼上雅座请: [数据结构与算法]14 搞不懂线性结构,非线性结构?
* f: x+ v: H) | O
3 V2 n; Q/ ^5 X" `' T
在图中元素叫做顶点( vertex ),图中的一个顶点可以和其他任意顶点建立连接关系,这种建立的关系叫做边( edge )
' @+ ]" i8 h* j) T, Z$ w$ q; a
# g3 P# h) ]1 @- V; t
无向图
& Y1 m( S! p. M5 z# [" D% d1 h
2020-4-26 15:15 上传
下载附件
(44.34 KB)
$ q( H! N$ ~( n+ G" K
5 `" K* U/ t( r0 g
上面给出的是无向图.看到这里你可能就觉得比较疑惑,这个无向图看起来没啥呀,怎么会有这种数据结构呢?
5 x, `: k2 Y' m
不知道你是怎么想的,我刚开始学的时候就有这种疑问,这是什么神仙数据结构哇,还会有应用场景?
6 r' J& x2 l/ O. r
3 z F& _8 d3 e0 x" Z1 `( m: N
既然有疑惑,那就给个应用场景:
4 p/ D+ s) l; ]
假设,现在你和我是微信好友,那是不是应该你的好友列表里面有我,我的好友里面有你,这样咱们才是好友对不对~
+ [2 ?9 O: ]9 @4 D' l
那在数据库中如何表示呢?吼~这个时候无向图就登场了
5 @, D( x3 b9 s7 M$ H" {. r6 V) s
你和我是微信好友,那就在咱俩之间来条线,表示咱俩之间有关系,一条线就解决了问题,真是完美至极啊
, g8 @& h6 x7 ^3 r# E
假设,(怎么又是假设,哈哈哈)上图中表示的就是 A,B,C,D,E,F 之间的关系,那你可能就发现问题了,有的顶点线比较多,比如 D 有四条线,有的就相对少一些,比如 B 有两条线.这些线就表示顶点的度( degree ).这个概念有啥用?
# w0 j$ S' |7 t) s& G7 S9 V* ^6 t
能一眼看出来谁的好友多!那这个功能有啥用?(好吧,这个功能好像是有点儿鸡肋,不过也算是一个应用场景
" }2 @, z# j2 W; M( t/ B0 C8 N
7 n) W f( b& N6 Z# ~% ]
有向图
: x& r- d/ B" M+ F- o
2020-4-26 15:15 上传
下载附件
(40.76 KB)
8 ~- |/ {* l7 ~6 T: }$ F
看到上面的无向图,基础不错的小伙伴肯定会说了,我还知道有向图呢!
$ d9 {# v6 F$ l5 {. U& l* e0 e
呦呵,不错,有向图就是下面这个样子:
1 [2 u0 }7 p- t( I2 B* W
( t8 `. z* C" g% [
在无向图中,咱们知道一个顶点有多少条边,就说它的度为多少.
% ^1 M% I d0 R. N' i4 Z9 R$ p
在有向图中呢,有指向顶点的,也有从顶点指出去的,基于无向图的概念,咱们把从这个顶点指出去的边称为出度,指向该顶点的边称为入度.
- ~4 x7 D1 G9 F! X2 \# W+ j
那么有向图会应用在哪些场景呢?微信好友这个场景是不太可以了
) S$ u0 g( X1 N- Z& q
那么微博呢?
: ^, Z" ?5 F( Y @
微博和微信有什么不一样呢?微信是你和我是好友,那么咱们的好友列表里一定是要有彼此的,拉黑或者删除彼此了,那就不能互相发送消息了.
3 j9 j. }& Z h8 k2 H; L6 {& d
但是微博呢?你关注了我,并不代表我就要关注你对吧?看到这里有没有一种豁然开朗的感觉~
2 ^( b" x5 X7 ]; J
那么我关注了多少人就是出度,多少人关注了我就是入度.
% A7 j( Q* H" j# X4 ?! F
这样带入理解是不是会比较好一点儿?(我可真是个天才,哈哈哈
" s* Y* g. h% s7 F6 r7 f5 }3 s
4 c- A3 {. O' b# _7 l3 e7 Q4 G
带权图
( G. h& R! ^: d) G3 z. u
2020-4-26 15:16 上传
下载附件
(37.68 KB)
5 F, Z5 w( e2 W) W
看完了无向图,有向图,相信就有人说,我还见过带权图!(陈独秀给我坐下!
9 N3 s4 q U) u: v. J
带权图长啥样呢?就下面这个样子:
% H" m3 i2 R& ^' H% h5 q5 I
$ p' L2 P( g6 t0 `5 H5 [
懵逼了,这每条边上的数字是个什么鬼呦
) X, T7 V' `, w P( ]+ R% c
别急,咱们来个场景:大家都玩 QQ 嘛?(别跟我说不玩,配合一下嘛…
7 W5 P6 t. _/ G0 H; h# f" m7 \
玩 QQ 的话,一定知道有 QQ 空间,然后空间里面有个「谁在意我」「我在意谁」的功能,就是下图:
) \; N; u4 _* u* H+ H
& S* s6 J( d5 R$ F# h
那么有没有好奇过呢? QQ 怎么知道我在意谁,谁在意我呢?
9 [% i* |0 F9 W+ L- N% ?
就是通过带权图哇
3 K0 q7 G! G$ S) \; d$ O' b
你访问了一个人的空间,这条边的权重就增加一点儿;别人访问了你的空间,那这条边的权重就增加一点儿;这段时间你们两个人聊天聊得比较频繁,来个小火花,顺便在你们两者之间的边权重增加一点儿.然后根据这些边的权重从大到小排序就得出了「谁在意我」「我在意谁」
( ~: r$ |% s+ d: e" i$ Y1 o' B3 k3 D
6 P: s n# E) v
到这里,上面的一切理解都还 OK ?
+ _5 |) I: N2 o8 T- v6 r, e
那咱们继续.图是怎么表示的呢?
& e0 j* C, w, L# d$ M% ?
图这种数据结构,再怎么画顶点,画边,到最后在物理结构上是怎么存储的呢?
3 j7 K2 D. @2 z
别急,你所疑惑的,我都帮你想到了
8 B6 @/ ~5 ?( p+ n
% \. s5 s4 R' {
图的存储方法
- |; W# q0 | @+ N5 S9 f
4 T* e* Q0 @3 j* L$ A, g& C" ~. S( w9 Z+ Z
图的存储方法主要有以下两种:
0 q) o; h& p9 q( _9 p
# h. F+ H" g7 U
邻接矩阵
/ E; D, o6 v( |5 Q, ?
2 q) O' m# k, J! J
邻接矩阵的底层依赖一个二维数组.对于无向图来说,如果 i 与 j 之间有边,那就将 A
[j] 和 A[j]
标记为 1 ;对于无向图来说,如果 i 指向 j ,那么 A
[j] 值为 1 ,如果 j 指向 i ,那么 A[j]
值为 1 ;对于带权图来说, A
[j] 存储的值就不是 1 了,而是对应的权重值.所以这是图最直观的一种存储方法.
; `# ~8 E2 E3 J' s z
啥,你跟我说这还不直观?该不会是没有看下图吧:
* \' X7 |) A1 q. h# m5 n
2020-4-26 15:16 上传
下载附件
(150.27 KB)
' J6 t4 T' w" O$ Q' A2 ?6 A0 t
但是你发现问题了嘛,这样看起来确实是直观了很多,但是很浪费空间有没有!比如无向图,如果 A
[j] 为 1 ,那么 A[j]
肯定也是 1 ,多存储 A[j]
根本没啥必要.就像买东西,明明一块钱能买到的东西,为啥非要花两块钱?
/ J c: {( r3 @+ M. V) _
所以如果使用邻接矩阵来表示的话,一定要清楚它的缺点.
3 ^/ J5 J* k0 [" o2 }
" \, x3 X$ ?7 M& i% Z2 B5 l
但这并不是说,使用邻接矩阵来存储就没啥优点.这天底下哪儿有那么绝对的事情呢.
: N: |8 A- @2 [8 m c
首先,邻接矩阵的存储方式简单,直接,所以当我们需要获取两个顶点之间的关系时,相信我没有比这种存储结构更高效的了.
# N3 k' b4 r' @ |9 O' \1 ^
还有就是使用邻接矩阵存储图的另外一个优点就是方便计算,因为可以将很多图的运算转换成矩阵之间的运算.
% r" o2 s8 Y1 ?0 K+ J- k
2 |+ U- j2 n+ N7 Q
邻接表
9 p2 j! e0 _3 t
; \! I- J2 `# K/ r% Z4 v' v
先来看图:
( i d5 \8 I9 x! i, w0 V
2020-4-26 15:17 上传
下载附件
(102.16 KB)
0 W6 b3 B9 e# z* O P5 S9 M
& \* K3 _8 F# V. l
乍一看,这不是散列表嘛!每个顶点对应一条链表,链表中存储的是与这个顶点相连接的其他顶点.
# p2 x8 X+ a& j. d: `8 z! R8 O
嘿嘿,直觉超棒!
, ^# a6 H U5 E$ p8 j& |' W8 v
9 K D" o) K$ n: ~" o o
如果你对散列表熟悉的话,应该知道,在散列表中,如果链太长了,会导致冲突概率增大,复杂度也蹭的一下升高.而且吧,链表的存储方式你也知道,不是连续的,所以相对于数组来说, CPU 读取就会慢一些,相对于邻接矩阵的存储方式,在邻接表中查询两个顶点之间的关系就没那么高效了.
( G- L+ H w' Z9 x8 M1 [
所以在实际开发中要注意遇到这种情况该如何处理,或者在刚开始的时候就直接设计好实现方式.比如可以将邻接表中的链表改为平衡二叉树,或者红黑树.
Q+ X# a, X$ g1 m. i3 I4 v
5 ]' h% S2 W. L1 T* Z4 i; a
我觉得对于数据结构来说,没有最好的,只有最合适的~
+ G7 j- B/ K) i9 W
: ^, C# a7 v) Q V- }; f: r. B+ S4 Y4 p
参考
3 M2 X, }/ Z( o8 O9 f! `5 _
' S0 h) ?8 [' l2 p: m$ W
极客时间—<数据结构与算法之美>
2 _1 c: q9 x2 A- y) J6 }
————————————————
3 ~/ @! i! ^2 L& n$ p
版权声明：本文为CSDN博主「郑璐璐」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
7 A) r; a* M M5 s
原文链接：https://blog.csdn.net/zll_0405/article/details/105209800
9 N L) z) u9 N
- P5 T' ~0 m& ]( y
2 _) F' q& D; U4 Z/ T) }9 Q
欢迎光临 数学建模社区-数学中国 (http://www.madio.net/)
Powered by Discuz! X2.5
