Chinaunix首页 | 论坛 | 博客
  • 博客访问: 2270416
  • 博文数量: 102
  • 博客积分: 1444
  • 博客等级: 中尉
  • 技术积分: 13853
  • 用 户 组: 普通用户
  • 注册时间: 2012-03-29 10:58
文章分类

全部博文(102)

文章存档

2014年(29)

2013年(14)

2012年(59)

分类: C/C++

2012-04-09 22:28:45

转载请注明来源chengyaogen.blog.chinaunix.net
 
一、图是一种比线性表和树更为复杂的数据结构

 
线性表:元素之间是线性关系,即表中元素最多一个直接前驱和一个直接后继

树:元素之间是层次关系。除根外,元素只有唯一直接前驱,但可以有若干个直接后继

图 :任意的两个元素都可能相关,即图中任一元素可以有若干个直接前驱和直接后继,属于网状结构类型   

注意:实际上,树是图的特列---有向无环图 

图的定义:

图(Graph)是一种非线性数据结构,形式 化描述为:Graph=(V,R)
其中,V={Vi | Vi ∈datatype, i=0,1,……,n-1} 是图中元素Vi(称为顶点Vertex )的集合,n=0时,V为空集,记为φ。
R是顶点之间的关系集,P(Vi,Vj)为顶点Vi与Vj之间是否存在路径的判定条件,即若Vi与Vj之间的路径存在,则关系< Vi,Vj >∈R。
 
二、图的基本术语
 
1)有向图(Digraph)
 
设Vi、Vj为图中的两个顶点,若关系存在方向性,即: ≠ ,则称相应的图为有向图。< Vi,Vj >∈R,表示从顶点 Vi到Vj的一条弧(Arc):
 
Vi为弧尾,Vj为弧头
 
2)无向图(Undigraph)

设Vi、Vj为图中的两个顶点,若关系无方向性,即:当∈R时,必有∈R,则称此时的图为无向图。关系用(Vi,Vj)或(Vj,Vi)表示,称为图中的一条边(Edge):(Vi,Vj)
eg:
设有向图G1 = (V,R)

V={V0,V1,V2,V3,V4,V5} (n = 6)
R = {         }

则G1的表示如下图所示:
 
 
值的注意的是,按照图的定义,图中的顶点V0经过V2到达V5,存在一条路径(V0,V2,V5),但G1的R中并未出现这样的关系,这是因为在关系R的等价闭包R'中,应包括关系传递性,即若: ∈R,则有∈R'。

故图的关系集一般是取最小关系集,即只写出图中弧的条数即可。

9)生成树(Spanning Tree)

无向连通图的生成树是图中的一个极小连通子图,它包含有图中全部顶点(设顶点数为n),但只有足以构成一棵树的n-1条边。如图的G2中,以V0为起点(根)的一棵生成树如图所示。若在生成树上增加一条边,必定形成回路,因为它使得两顶点间有了第二条通路。若图中有n个顶点,而小于n-1条边,则图是 非连通的,但有n-1条边的图不一定是树。

10)生成森林

若有向图中恰有一个顶点入度为0,其余顶点入度全为1,则此图可视为一棵有向树。有向图的生成森林F由图中若干棵有向树 组成。F是有向图的一个子图,包含有图中全部顶点,但只有足以构成若干棵不相交的有向树的弧。

如图G4,其生成森林如下:

几个问题

1.什么是子图?

答:假设G=(V,E)和G'=(V',E')是两个图(同为无向图或同为有向图),若V'∈V,并且E'∈E,则称G'是G的子图。

2.什么是路径长度?

答:无向图G=(V,E)中,若存在顶点序列Vi0,Vi1,...,Vin,使得(Vi0,Vi1),(Vi1,Vi2),...,(Vin-1,Vin)都在E中(若是有向图,则使得,,...,都在E中),则称从顶点Vi0到Vin存在一条路径,路径长度为路径上的边数。

3.什么是连通图?

答:无向图G=(V,E)中,若从Vi到Vj有一条路径(从Vj到Vi也一定有一条路径),则称Vi和Vj是连通的。若V(G)中任意两个不同的顶点Vi和Vj都是连通的(即有路径),则称G为连通图。

3.什么是强连通图?

答:有向图G=中,若V(G)中任意两个不同的顶点Vi和Vj都存在从Vi到Vj以及从Vj到Vi的路径,则称图G是强连通图。
 
 
阅读(4366) | 评论(3) | 转发(12) |
0

上一篇:u-boot启动完全分析

下一篇:图的存储

给主人留下些什么吧!~~

草根老师2012-04-11 22:23:40

呵呵,已经更新上了。

重返人生2012-04-11 16:30:49

可以说一说基于图的一些应用,各种算法,深度优先遍历、广度优先遍历等等,应该会有人看哈~

十七岁的回忆2012-04-10 22:45:01

节点多一些关系复杂一些嘛就是!