数据结构10 图

这一篇我们要总结的是图(Graph),图可能比我们之前学习的线性结构和树形结构都要复杂,不过没关系,我们一点一点地来总结。那么关于图,我将从以下几点进行总结:

1、图的定义

2、图相关的概念和术语

3、图的创建和遍历

1、图的定义

什么是图呢?

图是一种复杂的非线性结构。

在线性结构中,数据元素之间满足唯一的线性关系,每个数据元素(除第一个和最后一个外)只有一个直接前驱和一个直接后继;

在树形结构中,数据元素之间有着明显的层次关系,并且每个数据元素只与上一层中的一个元素(父节点)及下一层的多个元素(孩子节点)相关;

而在图形结构中,节点之间的关系是任意的,图中任意两个数据元素之间都有可能相关。

图G由两个集合V(顶点Vertex)和E(边Edge)组成,定义为G=(V,E)

2、图相关的概念和术语

2-1、无向图和有向图

对于一个图,若每条边都是没有方向的,则称该图为无向图。图示如下:

因此,(Vi,Vj)和(Vj,Vi)表示的是同一条边。注意,无向图是用小括号,而下面介绍的有向图是用尖括号。

无向图的顶点集和边集分别表示为:

V(G)={V1,V2,V3,V4,V5}

E(G)={(V1,V2),(V1,V4),(V2,V3),(V2,V5),(V3,V4),(V3,V5),(V4,V5)}

对于一个图G,若每条边都是有方向的,则称该图为有向图。图示如下:

因此,(Vi,Vj)和(Vj,Vi)是两条不同的有向边。注意,有向边又称为弧。

有向图的顶点集和边集分别表示为:

V(G)={V1,V2,V3}

E(G)={1,V2>,2,V3>,3,V1>,1,V3>}

2-2、无向完全图和有向完全图

我们将具有n(n-1)/2条边的无向图称为无向完全图。同理,将具有n(n-1)条边的有向图称为有向完全图。

2-3、顶点的度

对于无向图,顶点的度表示以该顶点作为一个端点的边的数目。比如,图(a)无向图中顶点V3的度D(V3)=3

对于有向图,顶点的度分为入度和出度。入度表示以该顶点为终点的入边数目,出度是以该顶点为起点的出边数目,该顶点的度等于其入度和出度之和。比如,图(b)中顶点V1的入度ID(V1)=1,出度OD(V1)=2,所以D(V1)=ID(V1)+OD(V1)=1+2=3

不管是无向图还是有向图,边数e、顶点数n和顶点的度数有如下关系:

拿图(b)来举例,由公式可以得到图G的边数e=(D(V1)+D(V2)+D(V3))/2=(3+2+3)/2=4

2-4、子图

故名思义,这个就不解释了。

2-5、路径,路径长度和回路

路径,比如在无向图G中,存在一个顶点序列Vp,Vi1,Vi2,Vi3…,Vim,Vq,使得(Vp,Vi1),(Vi1,Vi2),…,(Vim,Vq)均属于边集E(G),则称顶点Vp到Vq存在一条路径。

路径长度,是指一条路径上经过的边的数量。

回路,指一条路径的起点和终点为同一个顶点。

2-6、连通图(无向图)

连通图是指图G中任意两个顶点Vi和Vj都连通,则称为连通图。比如图(b)就是连通图。下面是一个非连通图的例子:

上图中,因为V5和V6是单独的,所以是非连通图。

2-7、强连通图(有向图)

强连通图是对于有向图而言的,与无向图的连通图类似。

2-8、网

带”权值”的连通图称为网。如图所示:

3、图的创建和遍历

3-1、图的两种存储结构

  1. 邻接矩阵,原理就是用两个数组,一个数组保存顶点集,一个数组保存边集。
  2. 邻接表,邻接表是图的一种链式存储结构。这种存储结构类似于树的孩子链表。对于图G中每个顶点Vi,把所有邻接于Vi的顶点Vj链成一个单链表,这个单链表称为顶点Vi的邻接表。

3-2、图的两种遍历方法

1.深度优先搜索遍历

深度优先搜索(DFS)遍历类似于树的前序遍历。其基本思路是:

①假设初始状态是图中所有顶点都未曾访问过,则可从图G中任意一顶点V为初始出发点,首先访问出发点V,并将其标记为已访问过。

②然后依次从V出发搜索V的每个邻接点W,若W未曾访问过,则以W作为新的出发点出发,继续进行深度优先遍历,直到图中所有和V有路径相通的顶点都被访问到。

③若此时图中仍有顶点未被访问,则另选一个未曾访问的顶点作为起点,重复上述步骤,直到图中所有顶点都被访问到为止。

图示如下:

注:红色数字代表遍历的先后顺序

如果采用邻接矩阵存储,则时间复杂度为O(n2);如果采用邻接表存储,时间复杂度为O(n+e)

2.广度优先搜索遍历

广度优先搜索遍历(BFS)类似于树的按层次遍历。其基本思路是:

①首先访问出发点Vi

②接着依次访问Vi的所有未被访问过的邻接点Vi1,Vi2,Vi3,…,Vit并均标记为已访问过。

③然后再按照Vi1,Vi2,… ,Vit的次序,访问每一个顶点的所有未曾访问过的顶点并均标记为已访问过,依此类推,直到图中所有和初始出发点Vi有路径相通的顶点都被访问过为止。

图示如下:

因此,图(f)采用广度优先搜索遍历以V0为出发点的顶点序列为:V0,V1,V3,V4,V2,V6,V8,V5,V7

如果采用邻接矩阵存储,则时间复杂度为O(n2),如果采用邻接表存储,则时间复杂度为O(n+e)

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏从流域到海域

图(Graph)的常用代码集合

图的相关概念请查阅离散数学图这一章或者数据结构中对图的介绍。代码来自课本。 /*Graph存储结构*/ //邻接矩阵表示法 #define MAX_VERTEX...

38160
来自专栏mathor

搜索(1)

 在讨论图的遍历问题之前,我们先来讨论一下图的存储问题,也就是我们在写程序的时候如何保存、表示一个图。首先我们会用连续的整数编号来表示点集。比如1号顶点、2号顶...

13910
来自专栏向治洪

数据结构之图

基本概念 图(Graph):图(Graph)是一种比线性表和树更为复杂的数据结构。 图结构:是研究数据元素之间的多对多的关系。在这种结构中,任意两个元素之间...

22550
来自专栏数据结构与算法

BZOJ3143: [Hnoi2013]游走(期望DP 高斯消元)

Description 一个无向连通图,顶点从1编号到N,边从1编号到M。  小Z在该图上进行随机游走,初始时小Z在1号顶点,每一步小Z以相等的概率随机选 择当...

48960
来自专栏mathor

图的常见算法

 图是由一系列点和边的集合构成的,一般有邻接矩阵和邻接表两种表示方式,c/c++可以看我的这篇文章:搜索(1)  这篇文章主要讲java语言中图的相关算法。首...

22720
来自专栏zaking's

用js来实现那些数据结构15(图01)

20240
来自专栏Android机动车

数据结构——图相关概念

可是现实生活中,好多关系不再是一对一或一对多,比如人和人之间的关系,会互相认识,就要考虑多对多的情况。这就是今天要介绍的——图。

11220
来自专栏机器学习与自然语言处理

Lake Counting(POJ-2386)

题目链接: http://poj.org/problem?id=2386 题目大意: 计算出相连的'W'有多少块 所需算法: 深度优先搜索(DFS) 主要思路:...

25170
来自专栏尾尾部落

[剑指offer] 跳台阶

一只青蛙一次可以跳上1级台阶,也可以跳上2级。求该青蛙跳上一个n级的台阶总共有多少种跳法(先后次序不同算不同的结果)。

9820
来自专栏算法与数据结构

数据结构 图

1-1 无向连通图至少有一个顶点的度为1 错误: 无向连通图考点: 1. 每条边连接两个顶点,所有顶点的度之和等于边数的2倍 2.记住两个特殊的无相连通图模型:...

43870

扫码关注云+社区

领取腾讯云代金券