四. 数据结构之图形结构

内容整理于鱼c工作室教程

1. 图的基本概念

1.1 图的概念

图(Graph)是由顶点的有穷非空集合和顶点之间边的集合组成,通常表示为:G(V,E),其中,G表示一个图,V是图G中顶点的集合,E是图G中边的集合。

1.2 图的基本概念

顶点: 线性表中我们把数据元素叫元素,树中叫结点,在图中数据元素我们则称之为顶点(Vertex)。线性表可以没有数据元素,称为空表,树中可以没有结点,叫做空树,而图结构在咱国内大部分的教材中强调顶点集合V要有穷非空。

线性表中,相邻的数据元素之间具有线性关系,树结构中,相邻两层的结点具有层次关系,而图结构中,任意两个顶点之间都可能有关系,顶点之间的逻辑关系来表示,边集可以是空的。

无向边:若顶点Vi到Vj之间的边没有方向,则称这条边为无向边(Edge),用无序偶(Vi,Vj)来表示。

有向边:若从顶点Vi到Vj的边有方向,则称这条边为有向边,也成为弧(Arc),用有序偶来表示,Vi称为弧尾,Vj称为弧头。

上图G2是一个有向图,G2={V2,E2},其中V2={A,B,C,D},E2={<B,A>,<B,C>,<C,A>,<A,D>}

简单图:在图结构中,若不存在顶点到其自身的边,且同一条边不重复出现,则称这样的图为简单图。

无向完全图:在无向图中,如果任意两个顶点之间都存在边,则称该图为无向完全图。含有n个顶点的无向完全图有n*(n-1)/2条边。

有向完全图:在有向图中,如果任意两个顶点之间都存在方向互为相反的两条弧,则称该图为有向完全图。含有n个顶点的有向完全图有n*(n-1)条边。

稀疏图和稠密图:这里的稀疏和稠密是模糊的概念,都是相对而言的,通常认为边或弧数小于n*logn(n是顶点的个数)的图称为稀疏图,反之称为稠密图。

有些图的边或弧带有与它相关的数字,这种与图的边或弧相关的数叫做(Weight),带权的图通常称为(Network)。

假设有两个图G1=(V1,E1)和G2=(V2,E2),如果V2⊆V1,E2⊆E1,则称G2为G1的子图(Subgraph)。

图的顶点与边之间的关系:

(1) 无向图的顶点与边之间的关系:

对于无向图G=(V,E),如果边(V1,V2)∈E,则称顶点V1和V2互为邻接点(Adjacent),即V1和V2相邻接。

边(V1,V2)依附(incident)于顶点V1和V2,或者说边(V1,V2)与顶点V1和V2相关联。

顶点V的度(Degree)是和V相关联的边的数目,记为TD(V),如下图,顶点A与B互为邻接点,边(A,B)依附于顶点A与B上,顶点A的度为3。

(2) 有向图的顶点与边之间的关系:

对于有向图G=(V,E),如果有∈E,则称顶点V1邻接到顶点V2,顶点V2邻接自顶点V1。

以顶点V为头的弧的数目称为V的入度(InDegree),记为ID(V),以V为尾的弧的数目称为V的出度(OutDegree),记为OD(V),因此顶点V的度为TD(V)=ID(V)+OD(V)。

下图顶点A的入度是2,出度是1,所以顶点A的度是3。

简单路径:序列中顶点不重复出现的路径称为简单路径,除了第一个顶点和最后一个顶点之外,其余顶点不重复出现的回路,称为简单回路或简单环。

下图左侧是简单环,右侧不是简单环:

连通图:在无向图G中,如果从顶点V1到顶点V2有路径,则称V1和V2是连通的,如果对于图中任意两个顶点Vi和Vj都是连通的,则称G是连通图(ConnectedGraph)。

下图左侧不是连通图,右侧是连通图:

1.3 图的存储结构

图的存储结构相比较线性表与树来说就复杂很多。我们回顾下,对于线性表来说,是一对一的关系,所以用数组或者链表均可简单存放。树结构是一对多的关系,所以我们要将数组和链表的特性结合在一起才能更好的存放。那么我们的图,是多对多的情况,另外图上的任何一个顶点都可以被看作是第一个顶点,任一顶点的邻接点之间也不存在次序关系。

因为任意两个顶点之间都可能存在联系,因此无法以数据元素在内存中的物理位置来表示元素之间的关系(内存物理位置是线性的,图的元素关系是平面的)。如果用多重链表来描述倒是可以做到,但在几节课前的树章节我们已经讨论过,纯粹用多重链表导致的浪费是无法想像的(如果各个顶点的度数相差太大,就会造成巨大的浪费)。

1.3.1 邻接矩阵

(无向图)

考虑到图是由顶点和边或弧两部分组成,合在一起比较困难,那就很自然地考虑到分为两个结构来分别存储。顶点因为不区分大小、主次,所以用一个一维数组来存储是狠不错的选择。而边或弧由于是顶点与顶点之间的关系,一维数组肯定就搞不定了,那我们不妨考虑用一个二维数组来存储。

图的邻接矩阵(Adjacency Matrix)存储方式是用两个数组来表示图。一个一维数组存储图中顶点信息,一个二维数组(称为邻接矩阵)存储图中的边或弧的信息。

我们可以设置两个数组,顶点数组为vertex[4]={V0,V1,V2,V3},边数组arc[4][4]为对称矩阵(0表示不存在顶点间的边,1表示顶点间存在边)。

对称矩阵:所谓对称矩阵就是n阶矩阵的元满足a[i][j]=a[j][i](0<=i,j<=n)。即从矩阵的左上角到右下角的主对角线为轴,右上角的元与左下角相对应的元全都是相等的。

有了这个二维数组组成的对称矩阵,我们就可以很容易地知道图中的信息:

要判定任意两顶点是否有边无边就非常容易了;

要知道某个顶点的度,其实就是这个顶点Vi在邻接矩阵中第i行(或第i列)的元素之和;

求顶点Vi的所有邻接点就是将矩阵中第i行元素扫描一遍,arc[i][j]为1就是邻接点咯。

(有向图)

无向图的边构成了一个对称矩阵,貌似浪费了一半的空间,那如果是有向图来存放,会不会把资源都利用得很好呢?

可见顶点数组vertex[4]={V0,V1,V2,V3},弧数组arc[4][4]也是一个矩阵,但因为是有向图,所以这个矩阵并不对称,例如由V1到V0有弧,得到arc[1][0]=1,而V0到V1没有弧,因此arc[0][1]=0。

另外有向图是有讲究的,要考虑入度和出度,顶点V1的入度为1,正好是第V1列的各数之和,顶点V1的出度为2,正好是第V1行的各数之和。

(网)

在图的术语中,我们提到了网这个概念,事实上也就是每条边上带有权的图就叫网。

1.3.2 邻接表

(无向图)

邻接矩阵看上去是个不错的选择,首先是容易理解,第二是索引和编排都很舒服~

但是我们也发现,对于边数相对顶点较少的图,这种结构无疑是存在对存储空间的极大浪费。

因此我们可以考虑另外一种存储结构方式,例如把数组与链表结合一起来存储,这种方式在图结构也适用,我们称为邻接表(AdjacencyList)。

邻接表的处理方法是这样:

图中顶点用一个一维数组存储,当然,顶点也可以用单链表来存储,不过数组可以较容易地读取顶点信息,更加方便。图中每个顶点Vi的所有邻接点构成一个线性表,由于邻接点的个数不确定,所以我们选择用单链表来存储。

(有向图)

若是有向图,邻接表结构也是类似的,我们先来看下把顶点当弧尾建立的邻接表,这样很容易就可以得到每个顶点的出度:

(网)

对于带权值的网图,可以在边表结点定义中再增加一个数据域来存储权值即可:

1.3.3 十字链表

邻接表固然优秀,但也有不足,例如对有向图的处理上,有时候需要再建立一个逆邻接表~那我们思考了:有没有可能把邻接表和逆邻接表结合起来呢?答案是肯定的,这就是我们现在要谈的十字链表(Orthogonal List)。为此我们重新定义顶点表结点结构:

1.3.4 邻接多重表

讲了有向图的优化存储结构,对于无向图的邻接表,有没有问题呢?如果我们在无向图的应用中,关注的重点是顶点的话,那么邻接表是不错的选择,但如果我们更关注的是边的操作,比如对已经访问过的边做标记,或者删除某一条边等操作,邻接表就显得不那么方便了。

到底有多烦?小甲鱼用图片告诉你:

若要删除(V0,V2)这条边,就需要对邻接表结构中边表的两个结点进行删除操作。

1.3.5 边集数组

边集数组是由两个一维数组构成,一个是存储顶点的信息,另一个是存储边的信息,这个边数组每个数据元素由一条边的起点下标(begin)、终点下标(end)和权(weight)组成。

1.4 图的遍历

树的遍历我们谈了四种方式,大家回忆一下,树因为根结点只有一个,并且所有的结点都只有一个双亲,所以不是很难理解。但是谈到图的遍历,那就复杂多了,因为它的任一顶点都可以和其余的所有顶点相邻接,因此极有可能存在重复走过某个顶点或漏了某个顶点的遍历过程。对于图的遍历,如果要避免以上情况,那就需要科学地设计遍历方案,通常有两种遍历次序方案:它们是深度优先遍历和广度优先遍历。

1.4.1 深度优先遍历

深度优先遍历(DepthFirstSearch),也有称为深度优先搜索,简称为DFS。

它的具体思想类似于课程开头讲的找钥匙方案,无论从哪一间房间开始都可以,将房间内的墙角、床头柜、床上、床下、衣柜、电视柜等挨个寻找,做到不放过任何一个死角,当所有的抽屉、储藏柜中全部都找遍,接着再寻找下一个房间。现在请大家一起来想办法走以下这个迷宫:

我们可以约定右手原则:在没有碰到重复顶点的情况下,分叉路口始终是向右手边走,每路过一个顶点就做一个记号。迷宫走完了,所有的顶点也遍历过了,这就是深度优先遍历!反应快的童鞋一定会感觉深度优先遍历其实就是一个递归的过程嘛~如果再细心观察,你会发现整个遍历过程就像是一棵树的前序遍历!


1.4.2 广度优先遍历

广度优先遍历(BreadthFirstSearch),又称为广度优先搜索,简称BFS。

如果以之前我们找钥匙的例子来讲,运用深度优先遍历意味着要先彻底查找完一个房间再开始另一个房间的搜索。但我们知道,钥匙放在沙发地下等犄角旮旯的可能性极低,因此我们运用新的方案:先看看钥匙是否放在各个房间的显眼位置,如果没有,再看看各个房间的抽屉有没有。这样逐步扩大查找的范围的方式我们称为广度优先遍历。

广度优先遍历是连通图的一种遍历策略。其基本思想如下:

1、从图中某个顶点V0出发,并访问此顶点;

2、从V0出发,访问V0的各个未曾访问的邻接点W1,W2,…,Wk;然后,依次从W1,W2,…,Wk出发访问各自未被访问的邻接点;

3、重复步骤2,直到全部顶点都被访问为止。

最后编辑于
©著作权归作者所有,转载或内容合作请联系作者
  • 序言:七十年代末,一起剥皮案震惊了整个滨河市,随后出现的几起案子,更是在滨河造成了极大的恐慌,老刑警刘岩,带你破解...
    沈念sama阅读 199,393评论 5 467
  • 序言:滨河连续发生了三起死亡事件,死亡现场离奇诡异,居然都是意外死亡,警方通过查阅死者的电脑和手机,发现死者居然都...
    沈念sama阅读 83,790评论 2 376
  • 文/潘晓璐 我一进店门,熙熙楼的掌柜王于贵愁眉苦脸地迎上来,“玉大人,你说我怎么就摊上这事。” “怎么了?”我有些...
    开封第一讲书人阅读 146,391评论 0 330
  • 文/不坏的土叔 我叫张陵,是天一观的道长。 经常有香客问我,道长,这世上最难降的妖魔是什么? 我笑而不...
    开封第一讲书人阅读 53,703评论 1 270
  • 正文 为了忘掉前任,我火速办了婚礼,结果婚礼上,老公的妹妹穿的比我还像新娘。我一直安慰自己,他们只是感情好,可当我...
    茶点故事阅读 62,613评论 5 359
  • 文/花漫 我一把揭开白布。 她就那样静静地躺着,像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上,一...
    开封第一讲书人阅读 48,003评论 1 275
  • 那天,我揣着相机与录音,去河边找鬼。 笑死,一个胖子当着我的面吹牛,可吹牛的内容都是我干的。 我是一名探鬼主播,决...
    沈念sama阅读 37,507评论 3 390
  • 文/苍兰香墨 我猛地睁开眼,长吁一口气:“原来是场噩梦啊……” “哼!你这毒妇竟也来了?” 一声冷哼从身侧响起,我...
    开封第一讲书人阅读 36,158评论 0 254
  • 序言:老挝万荣一对情侣失踪,失踪者是张志新(化名)和其女友刘颖,没想到半个月后,有当地人在树林里发现了一具尸体,经...
    沈念sama阅读 40,300评论 1 294
  • 正文 独居荒郊野岭守林人离奇死亡,尸身上长有42处带血的脓包…… 初始之章·张勋 以下内容为张勋视角 年9月15日...
    茶点故事阅读 35,256评论 2 317
  • 正文 我和宋清朗相恋三年,在试婚纱的时候发现自己被绿了。 大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
    茶点故事阅读 37,274评论 1 328
  • 序言:一个原本活蹦乱跳的男人离奇死亡,死状恐怖,灵堂内的尸体忽然破棺而出,到底是诈尸还是另有隐情,我是刑警宁泽,带...
    沈念sama阅读 32,984评论 3 316
  • 正文 年R本政府宣布,位于F岛的核电站,受9级特大地震影响,放射性物质发生泄漏。R本人自食恶果不足惜,却给世界环境...
    茶点故事阅读 38,569评论 3 303
  • 文/蒙蒙 一、第九天 我趴在偏房一处隐蔽的房顶上张望。 院中可真热闹,春花似锦、人声如沸。这庄子的主人今日做“春日...
    开封第一讲书人阅读 29,662评论 0 19
  • 文/苍兰香墨 我抬头看了看天上的太阳。三九已至,却和暖如春,着一层夹袄步出监牢的瞬间,已是汗流浃背。 一阵脚步声响...
    开封第一讲书人阅读 30,899评论 1 255
  • 我被黑心中介骗来泰国打工, 没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留,地道东北人。 一个月前我还...
    沈念sama阅读 42,268评论 2 345
  • 正文 我出身青楼,却偏偏与公主长得像,于是被迫代替她去往敌国和亲。 传闻我的和亲对象是个残疾皇子,可洞房花烛夜当晚...
    茶点故事阅读 41,840评论 2 339

推荐阅读更多精彩内容

  • 第一章 绪论 什么是数据结构? 数据结构的定义:数据结构是相互之间存在一种或多种特定关系的数据元素的集合。 第二章...
    SeanCheney阅读 5,720评论 0 19
  • 图是由顶点的有穷非空集合和顶点之间边的集合组成,通常表示为:G(V,E),其中,G表示一个图,V是图G中顶点的集合...
    开心糖果的夏天阅读 791评论 0 9
  • 图是一种比线性表和树更复杂的数据结构,在图中,结点之间的关系是任意的,任意两个数据元素之间都可能相关。图是一种多对...
    Alent阅读 2,271评论 1 22
  • 弗洛伊德算法适用于为图中每一个顶点求最短路径,思路如下 检查图中任何一个 到 任何另一个点能否通过第一个点降低最短...
    RichardW阅读 945评论 0 1
  • https://zh.visualgo.net/graphds 浅谈图形结构https://zh.visualgo...
    狼之独步阅读 4,097评论 0 0