文档章节

数据结构-图之基本概念

如比如比
 如比如比
发布于 2015/06/13 19:29
字数 1417
阅读 205
收藏 3

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


© 著作权归作者所有

如比如比
粉丝 126
博文 178
码字总数 286951
作品 0
日本
程序员
私信 提问
加载中

评论(0)

2020考研 王道 408 书籍

转载以及下载pdf:http://t.cn/EonlGRW 第1章 绪论 1.1 数据结构的基本概念 1.1.1 基本概念和术语 1.1.2 数据结构的三要素 1.1.3 本节试题精选 1.1.4 答案与解析 1.2 算法和算法评...

Me极客
2019/07/14
0
0
数据结构的基本概念

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

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

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

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

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

sxhelijian
2017/08/30
0
0
数据结构系统学习(1)数据类型和数据结构的概念

目录 1.有关数据结构的基本概念和术语 2.数据结构   在现代计算机系统中,计算机更多地用于控制,管理及数据处理等非数值计算的处理工作,而不像之前只需要处理数值型数据。这个时候,数据...

一只帅气的IT小昂
03/17
0
0

没有更多内容

加载失败,请刷新页面

加载更多

为什么不能在网上做 mmpi明尼苏达多项人格测验

在网上看了很多文章,知乎上也看了不少大侠的文字,也就是说,网上做测试是不行的!所以,引出这个话题: 为什么不能在网上做 mmpi 明尼苏达多项人格测验? 1、mmpi是一个专业的测试量表 说不...

蛤蟆丸子
14分钟前
7
0
idea 子模块删除后 再创建同名的子模块时, 子模块目录右下角没有蓝色的maven的标识 解决方法

同名子模块创建后,如图所示操作 记得选择maven工程,将对应的子目录包添加进去

ATOZ_HJ
19分钟前
21
0
教你如何隐藏 Ubuntu 18.04 左上方的“活动”按钮

本快速教程介绍了如何删除Ubuntu Gnome桌面顶部栏左上角的“活动”按钮。 左上角的“活动”按钮显示所有打开的应用程序窗口,顶部带有搜索框,右侧是工作区。 一些用户发现它无用,并希望删除...

linuxprobe2020
25分钟前
19
0
SQL优化还凭经验?这个工具能帮你智能优化SQL

前言 SQL优化是程序开发中经常遇到的问题,尤其是在程序规模不断扩大的时候。SQL的好坏不仅制约着程序的规模,影响着用户的体验,甚至威胁着信息的安全。 我们经常听到说哪家平台挂了,哪家网...

吴伟祥
47分钟前
26
0
如何在一台服务器上添加和管理多个WEB站点?

网络上的每一个Web站点都有一个惟一的身份标识,从而使客户机能够准确地访问。这一标识由三部分组成,即TCP端口号、IP地址和主机头名,通常有三种不同的实现途径。 通常情况下我们只会想到利...

BirdCloud
51分钟前
20
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部