文档章节

数据结构-图之基本概念

放个屁
 放个屁
发布于 2015/06/13 19:29
字数 1417
阅读 145
收藏 3
点赞 0
评论 0

在图中的数据元素称为顶点(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


© 著作权归作者所有

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

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

九劫散仙 ⋅ 02/01 ⋅ 0

数据库基本概念

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

mehome ⋅ 2017/04/11 ⋅ 0

数据结构课程主页-2016级

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

sxhelijian ⋅ 2017/08/30 ⋅ 0

Hibernate 基本概念

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

ke_ry ⋅ 2016/11/15 ⋅ 0

[深度学习]tensorflow基本概念01

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

baihuaxiu123 ⋅ 2017/09/01 ⋅ 0

tensorflow(一) 介绍及基本操作

一、tensorflow介绍 TensorFlow是谷歌基于DistBelief进行研发的第二代人工智能学习系统,其命名来源于本身的运行原理。Tensor(张量)意味着N维数组,Flow(流)意味着基于数据流图的计算,T...

missayaaa ⋅ 04/23 ⋅ 0

新栋BOOK教你学elasticsearch(一)-基本概念

一、首先必须要掌握以下4个数据结构的基本概念。 1、索引(index) 我们已经有了关系型数据库的基础,现在可以用类比理解。elasticsearch的索引,你就可以理解为是一张表。记住这里的‘索引’...

新栋BOOK ⋅ 2016/12/26 ⋅ 0

Trie 树实现与应用

Trie树 基本概念  Trie树又称字典树,它是用来查询字符串的一种数据结构。它每一个节点都有26个子节点,所以是26叉树。优点查询字符串的时候速度快,缺点浪费大量空间。  当一个字符串长为...

sdoyuxuan ⋅ 01/24 ⋅ 0

Delphi 面向对象编程 第一章

面向过程:程序和数据是分开的,即程序员所看到的就是过程或者函数的集合以及单独的一批数据。 面向对象:程序被看作是相互协作的对象的集合,每个对象都是类的实例,所有的类构成一个通过继...

CODER-SU ⋅ 2011/12/19 ⋅ 0

学习软件测试各阶段知识点汇总

第一阶段(软件测试理论及基础) Windows操作系统及网络基础:软件测试概念、计算机层次、软件分类、 互联网概述、 IP地址、虚拟机使用、操作系统安装 软件测试基础理论:软件开发阶段划分,软...

白一客 ⋅ 2017/06/01 ⋅ 0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

骰子游戏代码开源地址

因为阿里云现在服务器已经停用了,所以上面的配置已经失效。 服务端开源地址:https://gitee.com/goalya/chat4.git 客户端开源地址:https://gitee.com/goalya/client4.git 具体运行界面请参考...

算法之名 ⋅ 36分钟前 ⋅ 0

设计模式--装饰者模式

装饰者模式 定义 动态地给一个对象添加一些额外的职责。就增加功能来说,装饰模式相比生成子类更为灵活。 通用类图 意图 动态地给一个对象添加一些额外的职责。就增加功能来说,装饰模式相比...

gaob2001 ⋅ 今天 ⋅ 0

JavaScript零基础入门——(八)JavaScript的数组

JavaScript零基础入门——(八)JavaScript的数组 欢迎大家回到我们的JavaScript零基础入门,上一节课我们讲了有关JavaScript正则表达式的相关知识点,便于大家更好的对字符串进行处理。这一...

JandenMa ⋅ 今天 ⋅ 0

sbt网络问题解决方案

转自:http://dblab.xmu.edu.cn/blog/maven-network-problem/ cd ~/.sbt/launchers/0.13.9unzip -q ./sbt-launch.jar 修改 vi sbt/sbt.boot.properties 增加一个oschina库地址: [reposit......

狐狸老侠 ⋅ 今天 ⋅ 0

大数据,必须掌握的10项顶级安全技术

我们看到越来越多的数据泄漏事故、勒索软件和其他类型的网络攻击,这使得安全成为一个热门话题。 去年,企业IT面临的威胁仍然处于非常高的水平,每天都会看到媒体报道大量数据泄漏事故和攻击...

p柯西 ⋅ 今天 ⋅ 0

Linux下安装配置Hadoop2.7.6

前提 安装jdk 下载 wget http://mirrors.hust.edu.cn/apache/hadoop/common/hadoop-2.7.6/hadoop-2.7.6.tar.gz 解压 配置 vim /etc/profile # 配置java环境变量 export JAVA_HOME=/opt/jdk1......

晨猫 ⋅ 今天 ⋅ 0

crontab工具介绍

crontab crontab 是一个用于设置周期性被执行的任务工具。 周期性执行的任务列表称为Cron Table crontab(选项)(参数) -e:编辑该用户的计时器设置; -l:列出该用户的计时器设置; -r:删除该...

Linux学习笔记 ⋅ 今天 ⋅ 0

深入Java多线程——Java内存模型深入(2)

5. final域的内存语义 5.1 final域的重排序规则 1.对于final域,编译器和处理器要遵守两个重排序规则: (1)在构造函数内对一个final域的写入,与随后把这个被构造对象的引用赋值给一个引用...

江左煤郎 ⋅ 今天 ⋅ 0

面试-正向代理和反向代理

面试-正向代理和反向代理 Nginx 是一个高性能的反向代理服务器,但同时也支持正向代理方式的配置。

秋日芒草 ⋅ 今天 ⋅ 0

Spring 依赖注入(DI)

1、Setter方法注入: 通过设置方法注入依赖。这种方法既简单又常用。 类中定义set()方法: public class HelloWorldOutput{ HelloWorld helloWorld; public void setHelloWorld...

霍淇滨 ⋅ 昨天 ⋅ 0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

返回顶部
顶部