文档介绍：数据结构(C语言版) 第7章图
第7章图
内容
图的概念
图的存贮结构
图的遍历
图的最小生成树
拓扑排序
关键路径
最短路径
图的概念
: 定义Graph=(v,E) v:表示元素集合 E:元素之间的关系 现举两个例子,如下图:[例一][例二] 无向图中(1,2)和(2,1)代表同一边 有向图中<1,2>和<2,1>表示两个不同的方向边 以<1,2>为例,在<1,2>中: 1称为此边的起点或尾(弧尾) 2称为此边的终点或头(弧头) 边的方向规定为弧尾——〉弧头
V(G1)={1,2,3,4}顶点集合; E(G1)={<1,2>,<1,3>,<3,4>,<4,1>}边的集合(顶点关系)
V(G2)={1,2,3,4,5}顶点集合; E(G2)={(1,2),(1,4),(2,3),(2,5),(3,4),(3,5)}边的集合
1、完全图:在一个有N个顶点的图中,若每个顶点到其它(N-1)顶点都有一条边,则图中有N个顶点且有(N*(N-1)/2)条边的图称为完全图。
2、邻接点:对无向图G=(V,E),若有(V1,V2)属于E则称V1和V2互为邻接点。
3、相关边:两个相邻接的点连成的边叫做这两个结点的相关边。
4、度:与每个顶点相连的边的数叫该点的度。
5、入度:对有向图中某结点的弧头数(边的终点)称为该结点的入度。
6、出度:对有向图中某结点的弧尾数(边的终点)称为该结点的出度。
7、路径:在一图中若从某个顶点VP出发,沿着一些边经过顶点V1,V2,…,VM到达VG则称路径 8、回路:从一顶点出发又回到该顶点,则所经过的路径称为回路。
9、子图若G和G'是两个图,且存在着V(G')≤V(G)和E(G’)≤E(G)的关系,则称G’是G的子图
10、有关连通的概念
连通:在无向图中,若从顶点VI到顶点VJ之间有路径则称此二顶点是连通的。
连通图:如果图中任意一对顶点之间都是连通的,则称此图为连通图。
强连通:对于有向图,若从顶点VI到顶点VJ到顶点VI之间都有路径,则称这两点是强连通的。强连通图:图中任何一对顶点都是强连通的,则此图叫强连通图。
连通分量:非连通图中的每一个连通部分叫连通分量。
强连通分量:有向图中极大强连通子图称为有向图的强连通分量。
11、生成树
一个连通的生成树,它含有图中全部顶点,但只有足以构成树的N-1条边(N顶点个数)
如图P159
12. 权、网
权: 有些图对应每条边有一相应的数值。这个数值叫该边的权。
网: 这种带权的图叫网。
注:不同网络的权有不同的意义:电网络权可以是阻抗,运输网络中的权可以是路程长度,运费等。
图的几种基本操作
(1) LOC_VERTEX(G,v)顶点定位函数
 顶点函数: ,则函数值为零.
(2) GET_VERTEX(G,i)取顶点函数
  取点函数:>图G中顶点数则函数值为零.
(3) FIRST_ADJ(G,v)求第一个邻接点函数
     求第一个邻接点函数:,则函数值为零.
……P156