文档章节

数据结构-图之基本概念

放个屁
 放个屁
发布于 2015/06/13 19:29
字数 1417
阅读 146
收藏 3

在图中的数据元素称为顶点(Vertex)。顶点之间的关系称为边(Edge)。图G是由顶点的有穷集合V,以及边的集合E组成。

 

由有序对构成的图为有向图(Digraph)。在有向图中,两个顶点之间的由弧(Arc)连接,起始点(Initial node)为弧尾(Tail),终止点(terminal node)为弧首(Head)

 

由无序对构成的图是无向图(Undigraph)。无向的一条相当于有向的中两条,即如果无向v1v2有一条,那么既有从v1接到v2,也有从v2接到v1<v1,v2>E 并且<v2,v1>E,而有向格区分方向的。

 

如果n为顶点的数目,e为弧或边的数目时,有0.5*n*(n-1)条边的无向图称为完全图(Completed graph)。对于有向图,e的取值范围是0nn-1)。具有nn-1)条弧的有向图称为有向完全图。与图的边或弧相关的数叫做权(Weight),带权的图称为网。

 

如果一个图中的顶点和弧与另一个图的顶点和弧(或者部分顶点和弧)完全相同的话,这个图是另一个图的子图。

 

在无向图中,在同一条边上的顶点称作邻接点。也就是说这连个顶点相邻接。这条边依附于这连个顶点,或者说这条边和这连个顶点相关联。和顶点相关联的边的数目称为这个顶点的度。对于有向图,自始至终的相关联,以这个顶点为起始点的弧的数目称为这个顶点的入度。为终点的弧的数目称为出度。入度与出度的和是这个顶点的度。

度(Degree)是一个顶点的度是指与该顶点相关联的总边数,顶点v的度记作d(v)

阶(Order):图G中顶集V的大小称作图G的阶。

自环(Loop):若一条边的两个顶点相同,则此边称作自环。

路径(Path):从顶点u到顶点v的一条路径是指一个序列v_0,e_1,v_1,e_2,v_2,...e_k,v_ke_i的起点终点为v_{i-1}v_ik称作路径的长度;v_0=u,称为路径的起点;v_k=v,称为路径的终点。如果u=v,称该路径是闭的,反之则称为开的;如果v_1,...,v_k两两不等,则称之为简单路径(Simple path,注意,u=v是允许的)。轨道(Track):即简单路径。

行迹(Trace):如果路径P(u,v)中边各不相同,则该路径称为uv的一条行迹。

距离(Distance): 从顶点u出发到顶点v的最短路径若存在,则此路径的长度称作从uv的距离。若从uv根本不存在路径,则记该距离为无穷(∞)。

桥(Bridge):若去掉一条边,便会使得整个图不连通,该边称为桥。

 

图存储表示

邻接矩阵(数组)存储表示,用一个矩阵来保持边的情况,<v1,v2>EMatrix[v1][v2]=Weight

邻接表存储表示,需要保存一个顺序存储的顶点表和每个顶点上的边的链接表。

前向星存储表示

有向图的十字链表存储表示

无向图的邻接多重表存储表示

 

图的遍历方法有深度优先搜索法和广度(宽度)优先搜索法。

深度优先搜索

深度优先搜索法是树的先根遍历的推广,它的基本思想是:从图G的某个顶点v0出发,访问v0,然后选择一个与v0相邻且没被访问过的顶点vi访问,再从vi出发选择一个与vi相邻且未被访问的顶点vj进行访问,依次继续。如果当前被访问过的顶点的所有邻接顶点都已被访问,则退回到已被访问的顶点序列中最后一个拥有未被访问的相邻顶点的顶点w,从w出发按同样的方法向前遍历,直到图中所有顶点都被访问。

 

广度优先搜索

图的广度优先搜索是树的按层次遍历的推广,它的基本思想是:首先访问初始点vi,并将其标记为已访问过,接着访问vi的所有未被访问过的邻接点vi1,vi2,…, vi t,并均标记已访问过,然后再按照vi1,vi2,…, vi t的次序,访问每一个顶点的所有未被访问过的邻接点,并均标记为已访问过,依次类推,直到图中所有和初始点vi有路径相通的顶点都被访问过为止。

 

最小生成树 (带权图的最小树生成)

有向图的拓扑排序

环和树

连通性表

Warshall算法

最短路径问题

Dijkstra算法

 

Kruskal算法:

不停地循环,每一次都寻找两个顶点,这两个顶点不在同一个真子集里,且边上的权值最小。

把找到的这两个顶点联合起来。

初始时,每个顶点各自属于自己的子集合,共n个子集合。

每一步操作,都会将两个子集合融合成一个,进而减少一个子集合。

结束时,所有的顶点都在同一个子集合里,这个子集合就是最小生成树。

 http://cs.anu.edu.au/people/Warren.Armstrong/apac/trunk/module4/basic_graph_algorithms.xhtml


© 著作权归作者所有

共有 人打赏支持
放个屁
粉丝 124
博文 177
码字总数 285078
作品 0
日本
程序员
数据结构的基本概念

(一)什么是数据结构 数据结构是计算机存储、组织数据的方式。数据结构是指相互之间存在一种或多种特定关系的数据元素的集合。通常情况下,精心选择的数据结构可以带来更高的运行或者存储效...

九劫散仙
02/01
0
0
数据库基本概念

一、 数据库相关的概念:数据、数据库、数据库管理系统、数据库系统 二、 三、 数据库三个阶段:人工管理阶段,文件系统阶段,数据库系统阶段。 四、 数据库系统特点:1.数据结构化;2.数据共...

mehome
2017/04/11
0
0
数据结构课程主页-2016级

  新学期,再度起程!   翻转的数据结构课程再度迎来新的一批同学。   前两年,资源建设基本完备,课堂方案逐渐完善,同学们对新型的学习方式设计给予了肯定(参见2014级问卷调查和201...

sxhelijian
2017/08/30
0
0
Hibernate 基本概念

这一段正在学Hibernate,首先要了解下Hibernate大概的意思,究竟什么是Hibernate,到底它是个什么东西,必须从整体上把握下Hibernate在整个开发过程中所起到的作用,这样对更深入的理解很有帮...

ke_ry
2016/11/15
0
0
[深度学习]tensorflow基本概念01

前言 用tensorflow这样工具的原因是:它允许我们用计算图(Computational Graphs)的方式建立网络. 下面就是对计算图的直观讲解。 例如: 结构 计算图所建立的只是一个网络框架。在编程时,并...

baihuaxiu123
2017/09/01
0
0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

qduoj~前端~二次开发~打包docker镜像并上传到阿里云容器镜像仓库

上一篇文章https://my.oschina.net/finchxu/blog/1930017记录了怎么在本地修改前端,现在我要把我的修改添加到部署到本地的前端的docker容器中,然后打包这个容器成为一个本地镜像,然后把这...

虚拟世界的懒猫
今天
1
0
UML中 的各种符号含义

Class Notation A class notation consists of three parts: Class Name The name of the class appears in the first partition. Class Attributes Attributes are shown in the second par......

hutaishi
今天
1
0
20180818 上课截图

小丑鱼00
今天
1
0
Springsecurity之SecurityContextHolderStrategy

注:下面分析的版本是spring-security-4.2.x,源码的github地址是: https://github.com/spring-projects/spring-security/tree/4.2.x 先上一张图: 图1 SecurityContextHolderStrategy的三个......

汉斯-冯-拉特
今天
1
0
LNMP架构(Nginx负载均衡、ssl原理、生成ssl密钥对、Nginx配置ssl)

Nginx负载均衡 网站的访问量越来越大,服务器的服务模式也得进行相应的升级,比如分离出数据库服务器、分离出图片作为单独服务,这些是简单的数据的负载均衡,将压力分散到不同的机器上。有时...

蛋黄_Yolks
今天
1
0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

返回顶部
顶部