数据结构图（数据结构图的应用）

本篇文章给大家谈谈数据结构图，以及数据结构图的应用对应的知识点，希望对各位有所帮助，不要忘了收藏本站喔。

本文目录一览：

• 1、数据结构-图的简介
• 2、数据结构——图
• 3、数据结构 - 图（基础概念）
• 4、数据结构的图不能相交吗

数据结构-图的简介

举个例子，微信中许许多多的用户组成了一个多对多的朋友关系网，这个关系网就是数据结构中的图(Graph)。

图，是一种比树更为复杂的数据结构，树的节点之间是一对多的关系，并且存在父与子的层级划分，而图的顶点（注意在此不叫节点）之间是多对多的关系，并且所有顶点都是平等的，无所谓谁是父谁是子。

在图中，最基本的单元是 顶点 ，相当于树中的节点，顶点之间的关联关系，被称为 边 。

在一些图中，每一条边并不是完全等同的，使得边具有 权重 ，涉及到权重的图，称为 带权图 。

还有一些图中，顶点之间的关联并不是完全对称的，举个例子比如说微博，你的粉丝列表里有我，但我的粉丝列表里未必有你，类似于这种单方面关注的，顶点之间的边就有了方向的区分，这种带有方向的图称为 有向图 。

因此，综合有向无向、带权重不带权重，交叉来讲，图有带权重有向的、 带权重无向的 、不带权重的有向的、不带权重的无向的...

使用二维数组，表达各个顶点之间的关联关系

为了解决 邻接矩阵占用空间 的问题，人们想到了另一种图的表示方法：邻接表

在邻接表中，图的每一个顶点都兄派是一个链表的头节点，其晌枯后连接着该顶点能够直接达到的相邻顶点(在有向图中更能体现优势）

另外，其他表示方法：逆邻接表、十字链表...，在此不过多介绍了就。

即从图的某个顶点出发， 访问图中的所有顶点羡谨贺，且使每个顶点仅被访问一次 ，这个过程为图的遍历。

方法：BFS、DFS（具体介绍在之后章节，敬请期待。。。）

数据结构——图

转自：

阅读目录

一，图的定义

二，图相关的概念和术语

三，图的创建和遍历

四，最小生成树和最短路径

五，算法实现

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

1，图的定义？

2，图相关的概念和术语？

3，图的创建和遍历？

4，最小生成树和最短路径？

5，算法实现？

一，图的定义

什么是图呢？

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

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

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

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

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

二，图相关的概念和术语

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，若每条边都是有方向的，则称该图为有向图。图示如下。

因此，和是两条不同的有向边。注意，有向边又称为弧。

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

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

E(G)={，，，}

2，无向完全图和有向完全图

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

3，顶点的度

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

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

记住，不管是无向图还是有向图，顶点数n，边数e和顶点的度数有如下关系：

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

4，子图

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

5，路径，路径长度和回路

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

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

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

6，连通图(无向图)

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

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

7，强连通图(有向图)

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

8，网

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

三，图的创建和遍历

1，图的两种存储结构

1) 邻接矩阵，原理就是用两个数组，一个数组保存顶点集，一个数组保存边集。下面的算法实现里边我们也是采用这种存储结构。如下图所示：

2) 邻接表，邻接表是图的一种链式存储结构。这种存储结构类似于树的孩子链表。对于图G中每个顶点Vi，把所有邻接于Vi的顶点Vj链成一个单链表，这个单链表称为顶点Vi的邻接表。

2，图的两种遍历方法

1) 深度优先搜索遍历

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

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

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

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

图示如下：

注：红色数字代表遍历的先后顺序，所以图(e)无向图的深度优先遍历的顶点访问序列为：V0，V1，V2，V5，V4，V6，V3，V7，V8

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

2) 广度优先搜索遍历

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

a) 首先访问出发点Vi

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

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

图示如下：

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

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

四，最小生成树和最短路径

1，最小生成树

什么是最小生成树呢？在弄清什么是最小生成树之前，我们需要弄清什么是生成树？

用一句语简单概括生成树就是：生成树是将图中所有顶点以最少的边连通的子图。

比如图(g)可以同时得到两个生成树图(h)和图(i)

知道了什么是生成树之后，我们就很容易理解什么是最小生成树了。所谓最小生成树，用一句话总结就是：权值和最小的生成树就是最小生成树。

比如上图中的两个生成树，生成树1和生成树2，生成树1的权值和为：12，生成树2的权值为：14，我们可以证明图(h)生成树1就是图(g)的最小生成树。

那么如何构造最小生成树呢？可以使用普里姆算法。

2，最短路径

求最短路径也就是求最短路径长度。下面是一个带权值的有向图，表格中分别列出了顶点V1其它各顶点的最短路径长度。

表：顶点V1到其它各顶点的最短路径表

从图中可以看出，顶点V1到V4的路径有3条(V1，V2，V4)，(V1，V4)，(V1，V3，V2，V4)，其路径长度分别为15，20和10，因此，V1到V4的最短路径为(V1，V3，V2，V4)。

那么如何求带权有向图的最短路径长度呢？可以使用迪杰斯特拉(Dijkstra)算法。

[img]

数据结构 - 图（基础概念）

[TOC]

我们知道， 数据结构 是存储相互之间存在的一种或多种特定关系的数据元素的集合。也即，数据结构是对数据的存储与数据关系的描述。

实际上，数据结构强调的是对数据关系的描述，存储只是为了持有数据，同时在底层以一个合适的存储结构对数据进行组织，以便更好地满足对数据关系的描述。

对于数据的存储结构，有按前驱后继的线性组织形式排列的，比如线性表。也有数据按层的方式进行组织的，比如说树（结点与结点之间是一种层次关系）。

但是，无论是哪种数据存储组织方式，其基本底层存储结构主要就是数组和链表。因此，很多其他的数据结构底层真正用于存储数据就是数组和链表，然后在这之上构建出线性或层次组织。

对于数据关系的描述，我们知道，数据之间存在四种关系：

简而言之， 图 是一种较线性表和树等数据结构更加复杂的结构，在图中，元素之间的关系可以是任意的，图中任意两个数据元素之间都可能存在关系。

因此，对于图的元素之间的关系描述就显得比较复杂。

简单来说， 图 是由顶点和边组合而成，其结构示意图如下所示：

对于图的定义，有以下几个地方需丛谈要明确注意：

图是一个相对复杂的数据结构，为了更好地对图进行描述，让我们先来了解下与图相关的一些基础概念，主要包含如下：

注 ：实际上，如果一个图有 个顶点和小于 条边，则它是非连通图。

由前面的内容可以知道，图中的元素主要由顶点和边（或弧）组成，任意两个顶点之间都可禅郑培能存在联系，而顶点和边本身也存在联系，因此图的结构比较复杂，很难以数据元素在内存中的物理位置来表示图中元素之间的关系，也就是说， 图不可能仅用简单的顺序存储结构（即数组）来表示 。而多重链表尽管可以实现图结构（即以一个数据域和多个指针域组成的结点表示图中的一个顶点），但是却存在内存浪费或操作不便的问题。因此，图存储结构最终还是得通过结合顺序存储和链式存储才能做到比较好地实现。

当前用于图的存储主要有以下 5 种结构贺唯：

数据结构的图不能相交吗

数据结构图是一种：数据元素间存简缓在多对多关系的数据结构加上一组基本操作构成的抽象数据类型

不相交集数据结构是一种数据结构，它跟踪划分为多个不相交（非拦宴模重叠）子集的一组元素。联合查找算法是对此类数据结构执行两个有用操作的算法：

查找：确定特定元素所在的子集。这可用于确定两个元素是否在同一子集中。

并集：将两个子集合并为一个子集。这里我们首先祥悉要检查这两个子集是否属于同一个集合。如果没有，那么我们就不能执行联合。

我们将讨论不相交集数据结构的应用。应用程序用于检查给定的图形是否包含循环。

联合查找算法可用于检查无向图是否包含圈。注意，我们已经讨论了一种检测循环的算法。这是另一种基于联合查找的方法。此方法假定图形不包含任何自循环。

我们可以跟踪一维数组中的子集，我们称之为父数组。

图表中的循环

对于每条边，使用边的两个顶点创建子集。如果两个顶点位于同一子集中，则会找到一个循环。

以上说明数据结构图不能相交。

关于数据结构图和数据结构图的应用的介绍到此就结束了，不知道你从中找到你需要的信息了吗 ？如果你还想了解更多这方面的信息，记得收藏关注本站。