数学建模社区-数学中国

标题: [数据结构与算法]16 什么,图这种数据结构把你难住了?! [打印本页]
作者: 杨利霞    时间: 2020-4-26 15:17
标题: [数据结构与算法]16 什么,图这种数据结构把你难住了?!
[数据结构与算法]16 什么,图这种数据结构把你难住了?!6 x9 p/ s8 D5 s1 M: q$ U% N
你是不是和我一样,在学习数据结构与算法时,了解了一下图这种数据结构之后,根本不知道它的用武之地在哪里?8 E* _! i! w, m9 r
在我查了资料之后,现在我可以跟你讲讲,图可以这么用!6 l( L" x. d8 x% C7 L9 c* C
6 z2 c; w$ o" ?8 J6 h# a
概念介绍- j: e  u8 b4 V* @9 G. r

0 k' a1 n3 }/ N7 t! Q2 p先来了解一下什么是图.0 @' q1 Y* H, ~5 M# f' o6 {
图,是一种非线性表数据结构.
7 }+ }' p8 x% A7 U那么你可能会问了,什么是线性表结构哇,我怎么区别一种数据结构是线性的,还是非线性的呢.
! }, k  j: [1 ^" i. x7 A  q/ U! B: O哈哈,还好我机智,在这篇文章之前就写了一篇文章来介绍,如果还有疑问,楼上雅座请: [数据结构与算法]14 搞不懂线性结构,非线性结构?
" y- E5 \6 x* B# N$ D0 S/ w9 m( \% g9 K# _+ L; F& Z/ c
在图中元素叫做顶点( vertex ),图中的一个顶点可以和其他任意顶点建立连接关系,这种建立的关系叫做边( edge )! c: r* K8 E; V) j

; v! Z2 F2 t3 |无向图' p+ M; k8 J" _0 }5 X. E6 \
1.jpg
$ y& A0 s& f6 h1 B! \
/ [* b2 W9 D- x3 D上面给出的是无向图.看到这里你可能就觉得比较疑惑,这个无向图看起来没啥呀,怎么会有这种数据结构呢?  R  i2 ^7 g/ l! s
不知道你是怎么想的,我刚开始学的时候就有这种疑问,这是什么神仙数据结构哇,还会有应用场景?- a/ u7 D3 e+ U! a8 h
3 _9 j6 B8 ^$ T- [& K( `
既然有疑惑,那就给个应用场景:0 W) r* q0 N, s5 ?1 s4 G" o) _
假设,现在你和我是微信好友,那是不是应该你的好友列表里面有我,我的好友里面有你,这样咱们才是好友对不对~
& b7 ]6 V# |  b3 v' f- z" T那在数据库中如何表示呢?吼~这个时候无向图就登场了" v$ H- W1 O: z* n" x# E% [7 L4 Z
你和我是微信好友,那就在咱俩之间来条线,表示咱俩之间有关系,一条线就解决了问题,真是完美至极啊0 Y9 p1 Q- s2 u
假设,(怎么又是假设,哈哈哈)上图中表示的就是 A,B,C,D,E,F 之间的关系,那你可能就发现问题了,有的顶点线比较多,比如 D 有四条线,有的就相对少一些,比如 B 有两条线.这些线就表示顶点的度( degree ).这个概念有啥用?# R. a+ z+ |& g4 X7 v: y, e
能一眼看出来谁的好友多!那这个功能有啥用?(好吧,这个功能好像是有点儿鸡肋,不过也算是一个应用场景
( d6 d9 l" l' g) X$ d+ t# Y/ w1 E; U* h) r& m
有向图6 F3 l+ q% s+ |
2.jpg
  n+ ]/ U& C* `' g) g( Q4 P看到上面的无向图,基础不错的小伙伴肯定会说了,我还知道有向图呢!
; x( h+ d3 U5 h3 }; m' \呦呵,不错,有向图就是下面这个样子:; |" M1 h1 f7 x" `7 T

  M3 `# Z5 I7 L" r3 Q6 ]$ r* V在无向图中,咱们知道一个顶点有多少条边,就说它的度为多少.2 C) _9 T: W- X- o+ b, e4 E
在有向图中呢,有指向顶点的,也有从顶点指出去的,基于无向图的概念,咱们把从这个顶点指出去的边称为出度,指向该顶点的边称为入度.( l3 R" @* a! J' [
那么有向图会应用在哪些场景呢?微信好友这个场景是不太可以了
% z( K. O& y* U  Z$ u, {那么微博呢?3 S/ [) I" B4 Y  S" k0 _  ^
微博和微信有什么不一样呢?微信是你和我是好友,那么咱们的好友列表里一定是要有彼此的,拉黑或者删除彼此了,那就不能互相发送消息了.  d: Y' [6 ?+ ^4 A
但是微博呢?你关注了我,并不代表我就要关注你对吧?看到这里有没有一种豁然开朗的感觉~
; w0 j4 Z% `  L' M那么我关注了多少人就是出度,多少人关注了我就是入度.; p8 k6 x/ v2 c! m( \8 `' Q5 v
这样带入理解是不是会比较好一点儿?(我可真是个天才,哈哈哈
. Q* n- _9 ^6 i( m3 n$ a! V
1 D/ @- P: M2 \/ K; ~1 {" e) l9 n带权图8 `. n5 z- o0 n$ L, x6 K
3.jpg 4 Q! D, I2 i; S& N) l$ |
看完了无向图,有向图,相信就有人说,我还见过带权图!(陈独秀给我坐下!" _0 N7 a1 b0 m7 l' p9 z) q
带权图长啥样呢?就下面这个样子:
8 H, ]& R0 R3 H$ V9 c: A
* t; ?  E4 N1 f6 b( R懵逼了,这每条边上的数字是个什么鬼呦, t2 A3 {# M* o6 Z& t
别急,咱们来个场景:大家都玩 QQ 嘛?(别跟我说不玩,配合一下嘛…* ~: L* ^- o" K; `2 ]" |! h. _) [( d" q
玩 QQ 的话,一定知道有 QQ 空间,然后空间里面有个「谁在意我」「我在意谁」的功能,就是下图:, O- y2 W2 ^" m9 c( A
' g( A( @9 k; T( N0 p! B1 M, D6 s
那么有没有好奇过呢? QQ 怎么知道我在意谁,谁在意我呢?
" p& X5 O- G: |0 I+ `就是通过带权图哇( ^0 m; u! G/ N5 q
你访问了一个人的空间,这条边的权重就增加一点儿;别人访问了你的空间,那这条边的权重就增加一点儿;这段时间你们两个人聊天聊得比较频繁,来个小火花,顺便在你们两者之间的边权重增加一点儿.然后根据这些边的权重从大到小排序就得出了「谁在意我」「我在意谁」, z5 u; U  n( ?# N" Z
: p, ?+ x' K& w. [* w
到这里,上面的一切理解都还 OK ?% U7 _! L( s/ Z1 l  _
那咱们继续.图是怎么表示的呢?
' v5 k1 b5 H# ~8 a图这种数据结构,再怎么画顶点,画边,到最后在物理结构上是怎么存储的呢?
; F/ L; l. b) }# _2 O/ a8 T1 ?. y别急,你所疑惑的,我都帮你想到了
2 M3 t, h5 X( y8 w5 c+ x" b
# _$ G. d- B+ u6 D图的存储方法
) [" ?  @- {0 K' b4 L4 F
  a7 V9 n$ C* i" i9 A$ l5 ]! [图的存储方法主要有以下两种:  N4 P2 x+ a# V0 D

1 L9 }$ X0 ]2 U1 s% j+ t邻接矩阵
9 W' e( m1 h# c8 g4 v$ ]3 e$ D4 c9 U
邻接矩阵的底层依赖一个二维数组.对于无向图来说,如果 i 与 j 之间有边,那就将 A[j] 和 A[j] 标记为 1 ;对于无向图来说,如果 i 指向 j ,那么 A[j] 值为 1 ,如果 j 指向 i ,那么 A[j] 值为 1 ;对于带权图来说, A[j] 存储的值就不是 1 了,而是对应的权重值.所以这是图最直观的一种存储方法.
: u9 i1 g: K8 X' @% x5 N啥,你跟我说这还不直观?该不会是没有看下图吧:" S  j6 V( C% d+ \
4.jpg / b- `, x* l) z! Z5 K+ N! w0 c. o1 I
但是你发现问题了嘛,这样看起来确实是直观了很多,但是很浪费空间有没有!比如无向图,如果 A[j] 为 1 ,那么 A[j] 肯定也是 1 ,多存储 A[j] 根本没啥必要.就像买东西,明明一块钱能买到的东西,为啥非要花两块钱?. k0 V7 J' D8 `' \7 o/ k
所以如果使用邻接矩阵来表示的话,一定要清楚它的缺点.6 U/ L: U0 z) P9 X+ m

. E9 t4 ^& C! D" {8 ~5 H但这并不是说,使用邻接矩阵来存储就没啥优点.这天底下哪儿有那么绝对的事情呢.
7 r8 P; H& T1 [9 o& @* p首先,邻接矩阵的存储方式简单,直接,所以当我们需要获取两个顶点之间的关系时,相信我没有比这种存储结构更高效的了.; Y  M. I, ?4 C; k7 l
还有就是使用邻接矩阵存储图的另外一个优点就是方便计算,因为可以将很多图的运算转换成矩阵之间的运算.4 ~+ D  C9 N0 u# W. ?- e) V

) k' q! U5 \2 _) L2 z8 t7 A% Y邻接表. B7 f. E5 @4 @! {# S
3 r; ]# H# L& d4 F9 y/ G3 r8 r6 _
先来看图:
( [! _* L1 Z' y8 U3 T2 w 5.jpg 6 x  ~! ^2 h( ~. m
8 K8 m7 [$ Z6 J: D
乍一看,这不是散列表嘛!每个顶点对应一条链表,链表中存储的是与这个顶点相连接的其他顶点." I4 w5 H. x: A+ d
嘿嘿,直觉超棒!: Z5 r4 t  j3 E# }1 w; w. Z' g
# u; Z3 a' N# m' m: g/ z% O) C
如果你对散列表熟悉的话,应该知道,在散列表中,如果链太长了,会导致冲突概率增大,复杂度也蹭的一下升高.而且吧,链表的存储方式你也知道,不是连续的,所以相对于数组来说, CPU 读取就会慢一些,相对于邻接矩阵的存储方式,在邻接表中查询两个顶点之间的关系就没那么高效了.. L( u9 V1 F# F
所以在实际开发中要注意遇到这种情况该如何处理,或者在刚开始的时候就直接设计好实现方式.比如可以将邻接表中的链表改为平衡二叉树,或者红黑树.3 a# i+ U9 D1 l; t4 y' i# f

, v4 x/ B+ J  [# Y2 Y9 p我觉得对于数据结构来说,没有最好的,只有最合适的~
1 X$ B  j& j+ z# F
5 _0 D% P" I5 r. A; Y. G9 L: ]' C参考% z" s5 I' i1 d4 D, o) v

4 `% h* x- c/ Y/ ~; u极客时间—<数据结构与算法之美>; [0 p$ ?4 U$ P* s
————————————————
: ~# M3 i. M4 l  z版权声明：本文为CSDN博主「郑璐璐」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
9 e7 G+ x! m# w) c原文链接：https://blog.csdn.net/zll_0405/article/details/105209800
. L; f& {; [2 B+ ~+ r/ L% N
! g7 S! j: i. b8 q; y- k$ h: z  J$ b2 _- b4 }




欢迎光临 数学建模社区-数学中国 (http://www.madio.net/) Powered by Discuz! X2.5