QQ登录

只需要一步,快速开始

 注册地址  找回密码
查看: 1593|回复: 0
打印 上一主题 下一主题

[数据结构与算法]16 什么,图这种数据结构把你难住了?!

[复制链接]
字体大小: 正常 放大
杨利霞        

5273

主题

82

听众

17万

积分

  • TA的每日心情
    开心
    2021-8-11 17:59
  • 签到天数: 17 天

    [LV.4]偶尔看看III

    网络挑战赛参赛者

    网络挑战赛参赛者

    自我介绍
    本人女,毕业于内蒙古科技大学,担任文职专业,毕业专业英语。

    群组2018美赛大象算法课程

    群组2018美赛护航培训课程

    群组2019年 数学中国站长建

    群组2019年数据分析师课程

    群组2018年大象老师国赛优

    跳转到指定楼层
    1#
    发表于 2020-4-26 15:17 |只看该作者 |倒序浏览
    |招呼Ta 关注Ta
    [数据结构与算法]16 什么,图这种数据结构把你难住了?!- [- X7 }/ C4 \9 J! K2 v, L5 D' v
    你是不是和我一样,在学习数据结构与算法时,了解了一下图这种数据结构之后,根本不知道它的用武之地在哪里?/ _) s! B1 Q! X, z8 N& \; ~
    在我查了资料之后,现在我可以跟你讲讲,图可以这么用!
    , O5 G0 S) A7 I* W- l/ E  N' Q+ D( X# X# X# V! z- g) k$ g
    概念介绍9 t4 C$ O* H% p0 _/ i: L# |
    % m8 g+ _# X  A' O5 N1 B3 W2 D
    先来了解一下什么是图.! j5 d( n+ b- i1 L
    图,是一种非线性表数据结构.% |) c, X, h8 Q/ D! b
    那么你可能会问了,什么是线性表结构哇,我怎么区别一种数据结构是线性的,还是非线性的呢.
    ; H7 C. }. x: g哈哈,还好我机智,在这篇文章之前就写了一篇文章来介绍,如果还有疑问,楼上雅座请: [数据结构与算法]14 搞不懂线性结构,非线性结构?5 [6 |: S7 I6 \1 P# j

    ' t5 [5 b; R' R$ ]在图中元素叫做顶点( vertex ),图中的一个顶点可以和其他任意顶点建立连接关系,这种建立的关系叫做边( edge )
    % N8 Z) _8 X* N  D8 Q
    ' a: {0 \: F0 h; {4 r- {! g无向图
    ) W  z  [6 q& U$ F 1.jpg
    / F% b1 J& r' K6 Z; z
    " o, @* Q) j5 d- Y" _上面给出的是无向图.看到这里你可能就觉得比较疑惑,这个无向图看起来没啥呀,怎么会有这种数据结构呢?  H  F( I* ^& L' d( T
    不知道你是怎么想的,我刚开始学的时候就有这种疑问,这是什么神仙数据结构哇,还会有应用场景?
    + }6 b! x/ L7 f2 C, U+ Y' s- m  v2 \7 s% E0 [& y+ ~
    既然有疑惑,那就给个应用场景:& U7 h: j3 A' y( f# S; v
    假设,现在你和我是微信好友,那是不是应该你的好友列表里面有我,我的好友里面有你,这样咱们才是好友对不对~! a  D: c2 G0 x5 _
    那在数据库中如何表示呢?吼~这个时候无向图就登场了9 d. E2 [0 i2 r
    你和我是微信好友,那就在咱俩之间来条线,表示咱俩之间有关系,一条线就解决了问题,真是完美至极啊5 F  Q, p: X3 M  {' c' @" v  H
    假设,(怎么又是假设,哈哈哈)上图中表示的就是 A,B,C,D,E,F 之间的关系,那你可能就发现问题了,有的顶点线比较多,比如 D 有四条线,有的就相对少一些,比如 B 有两条线.这些线就表示顶点的度( degree ).这个概念有啥用?
    3 b* g  u2 z" e5 o: J) i6 E能一眼看出来谁的好友多!那这个功能有啥用?(好吧,这个功能好像是有点儿鸡肋,不过也算是一个应用场景1 }: q# }1 D) K) B9 X$ V
    + r7 r& n+ m* k( V  ?. g
    有向图% c4 d- y- l3 }6 I' }1 C" w- C& B
    2.jpg ! f3 P% }2 S6 ^. k9 ~! s/ [
    看到上面的无向图,基础不错的小伙伴肯定会说了,我还知道有向图呢!
    ! D/ ^# X5 t* I呦呵,不错,有向图就是下面这个样子:
    9 v1 Z; H6 }! }" ?( \8 z' P: A$ P7 b8 b
    在无向图中,咱们知道一个顶点有多少条边,就说它的度为多少.
    & M: O  H+ ~- I5 ^0 Q在有向图中呢,有指向顶点的,也有从顶点指出去的,基于无向图的概念,咱们把从这个顶点指出去的边称为出度,指向该顶点的边称为入度.
    0 w2 b3 w/ y! Q/ q) @" c/ O那么有向图会应用在哪些场景呢?微信好友这个场景是不太可以了0 n- v3 h( Q7 g: o( _  z! k
    那么微博呢?; ^9 t0 H, j4 ]) V! q1 d
    微博和微信有什么不一样呢?微信是你和我是好友,那么咱们的好友列表里一定是要有彼此的,拉黑或者删除彼此了,那就不能互相发送消息了.
    & j5 ?: d+ b, s$ G/ F( h( G8 t& `但是微博呢?你关注了我,并不代表我就要关注你对吧?看到这里有没有一种豁然开朗的感觉~9 A* Q2 @" m- k. R5 S
    那么我关注了多少人就是出度,多少人关注了我就是入度.. M$ B  s+ U& W4 ~
    这样带入理解是不是会比较好一点儿?(我可真是个天才,哈哈哈
    5 Q+ r/ b- a5 \5 G, V! B
    ' n' b* {2 J  M( X% M6 j带权图, B( a" ^; j7 s2 X! B! m2 H9 t$ J
    3.jpg
    7 c- ]; j& }: y看完了无向图,有向图,相信就有人说,我还见过带权图!(陈独秀给我坐下!
    ( K$ L$ F9 [- d% g2 [8 s带权图长啥样呢?就下面这个样子:8 o$ D' [6 v& J0 X0 L
    ; Y: j/ C1 `( X9 R8 b5 E- q" p
    懵逼了,这每条边上的数字是个什么鬼呦
    , O& z/ `( _2 V: Y) z. v% ^7 u别急,咱们来个场景:大家都玩 QQ 嘛?(别跟我说不玩,配合一下嘛…
    . [3 W5 l/ V/ l7 O玩 QQ 的话,一定知道有 QQ 空间,然后空间里面有个「谁在意我」「我在意谁」的功能,就是下图:
    ; E3 n- U4 y1 ?' K: N: k8 s- o( ~+ [. m$ U
    那么有没有好奇过呢? QQ 怎么知道我在意谁,谁在意我呢?
    5 k  `9 [' c0 g' H" W就是通过带权图哇
    ( ?3 {; }( Q; g4 P你访问了一个人的空间,这条边的权重就增加一点儿;别人访问了你的空间,那这条边的权重就增加一点儿;这段时间你们两个人聊天聊得比较频繁,来个小火花,顺便在你们两者之间的边权重增加一点儿.然后根据这些边的权重从大到小排序就得出了「谁在意我」「我在意谁」! R; w) Q# b! w

    5 d3 ]7 N1 u( L# R  ]; k到这里,上面的一切理解都还 OK ?! O" l4 i( O( t5 ~+ w1 W
    那咱们继续.图是怎么表示的呢?, m3 q* r" ~! G
    图这种数据结构,再怎么画顶点,画边,到最后在物理结构上是怎么存储的呢?
    . }8 e( d( n! e: ]* n; q2 n别急,你所疑惑的,我都帮你想到了
    / d3 {7 |3 |, H, y0 F: r( M
    " e* S" v* `0 b# l6 C9 d% [6 ^图的存储方法2 @5 u& \" Z% H1 F1 Q9 T

    . B1 e+ L4 O+ }7 u! e$ O图的存储方法主要有以下两种:
    2 W/ P" |5 y, W- d9 q1 k4 N0 r/ B
    邻接矩阵$ j2 U6 h% I8 U4 v% c: A0 H
    6 z; e( f( q8 V( A) a5 F
    邻接矩阵的底层依赖一个二维数组.对于无向图来说,如果 i 与 j 之间有边,那就将 A[j] 和 A[j] 标记为 1 ;对于无向图来说,如果 i 指向 j ,那么 A[j] 值为 1 ,如果 j 指向 i ,那么 A[j] 值为 1 ;对于带权图来说, A[j] 存储的值就不是 1 了,而是对应的权重值.所以这是图最直观的一种存储方法.
    1 J' H5 k8 {- M3 `/ ?: a6 l啥,你跟我说这还不直观?该不会是没有看下图吧:
    % B  i4 D' b9 q# V 4.jpg
    8 `8 [/ g: _/ u; O但是你发现问题了嘛,这样看起来确实是直观了很多,但是很浪费空间有没有!比如无向图,如果 A[j] 为 1 ,那么 A[j] 肯定也是 1 ,多存储 A[j] 根本没啥必要.就像买东西,明明一块钱能买到的东西,为啥非要花两块钱?
    ! V! v! D0 n5 l# n- }; w& u7 ^' y所以如果使用邻接矩阵来表示的话,一定要清楚它的缺点.
    , R- `; ^0 n' n9 @1 T6 ^/ O7 D) A" b4 J$ f4 q9 T- W' b
    但这并不是说,使用邻接矩阵来存储就没啥优点.这天底下哪儿有那么绝对的事情呢.
    ! X5 H# |+ p0 C) Y* W首先,邻接矩阵的存储方式简单,直接,所以当我们需要获取两个顶点之间的关系时,相信我没有比这种存储结构更高效的了.
    + X: W' j; ]1 a( h2 G+ l4 g" D还有就是使用邻接矩阵存储图的另外一个优点就是方便计算,因为可以将很多图的运算转换成矩阵之间的运算.
    7 a" g8 T8 n) J$ y# r3 U# Y) @4 x) m) v! I! Y* B& N
    邻接表) C  P- f$ E( ~8 W

    . }' L8 Z1 l; V! F( P" \2 z先来看图:4 X# T4 R0 T% T( i2 [
    5.jpg 4 O! W9 F7 u8 I! [  ?4 W
    + h. @* M! K' Y8 Y% A
    乍一看,这不是散列表嘛!每个顶点对应一条链表,链表中存储的是与这个顶点相连接的其他顶点.* G2 y* W% Y1 \1 z4 E
    嘿嘿,直觉超棒!2 K! `' ~: |, e+ y$ e

    8 W8 P4 _2 s. a! L如果你对散列表熟悉的话,应该知道,在散列表中,如果链太长了,会导致冲突概率增大,复杂度也蹭的一下升高.而且吧,链表的存储方式你也知道,不是连续的,所以相对于数组来说, CPU 读取就会慢一些,相对于邻接矩阵的存储方式,在邻接表中查询两个顶点之间的关系就没那么高效了.- q9 s) ^. c3 a( d" n# i' x/ j
    所以在实际开发中要注意遇到这种情况该如何处理,或者在刚开始的时候就直接设计好实现方式.比如可以将邻接表中的链表改为平衡二叉树,或者红黑树.
    % K4 K( i8 \3 r3 p. w5 _! r2 |. \7 {3 J7 `
    我觉得对于数据结构来说,没有最好的,只有最合适的~
    $ |. S/ V" O" [4 O3 X: N, W5 O; B' E0 ?- M
    参考. N" O* o1 _; p! Q

    + V  x4 y- A) U( l极客时间—<数据结构与算法之美>
    ' o/ l; \2 q' e: j( s————————————————" _/ l. T# j) l5 e6 d: H0 c" }
    版权声明:本文为CSDN博主「郑璐璐」的原创文章,遵循CC 4.0 BY-SA版权协议,转载请附上原文出处链接及本声明。) d9 k) R% c7 M# }
    原文链接:https://blog.csdn.net/zll_0405/article/details/105209800) d% l$ E$ w' G- z3 M3 ?/ Y  S

    / \0 g- |) j# U+ z; F% X1 N) G) v" c* ^- C& q
    zan
    转播转播0 分享淘帖0 分享分享0 收藏收藏0 支持支持0 反对反对0 微信微信
    您需要登录后才可以回帖 登录 | 注册地址

    qq
    收缩
    • 电话咨询

    • 04714969085
    fastpost

    关于我们| 联系我们| 诚征英才| 对外合作| 产品服务| QQ

    手机版|Archiver| |繁體中文 手机客户端  

    蒙公网安备 15010502000194号

    Powered by Discuz! X2.5   © 2001-2013 数学建模网-数学中国 ( 蒙ICP备14002410号-3 蒙BBS备-0002号 )     论坛法律顾问:王兆丰

    GMT+8, 2026-7-25 15:20 , Processed in 0.425597 second(s), 54 queries .

    回顶部