数据结构第七章图(2016)

n n ID ( v ) = OD ( v ) = e i i i =1 i =1
V3
V4
４）子图：
7.1 图的概念
设有两个图 G＝(V, E) 和 G’＝(V’, E’)。 若 V’ V 且 E’ E, 且E’ 中的边所关联的顶点均 在V’中，则称 图G’ 是 图G 的子图。
7.1 图的概念 ５）路径：在无向图G=(V, E)中，从顶点vp到顶点vq之 间的路径是一个顶点序列(vp=vi0,vi1,vi2, …, vim=vq)，其 中， (vij-1,vij)∈E（ 1≤j≤m）。若 G是有向图，则路径也 是有方向的，顶点序列满足<vij-1,vij>∈E。
vexs=
V1 V2 V3 V4
V1 V2 V3 V4
V3
V4
0 0 arcs= 0 1
1 0 0 0
1 0 0 0
0 0 1 0
V1
V2
V3
V4
如何求顶点 i 的出度？
邻接矩阵的第 i 行非零元素个数。
7.2.1 邻接矩阵表示法
有向图的邻接矩阵
V1 V2 vexs= V1 V2 V3 V4
V1 V2 V3 V4
有向图： 图G中的每条边(有向边)都是有方向的； 无向图： 图G中的每条边(无向边)都是无方向的； 完全图： 图G任意两个顶点都有一条边相连接；
若 n 个顶点的无向图有 n(n-1)/2 条边, 称为无向完全图 若 n 个顶点的有向图有n(n-1) 条边, 称为有向完全图
例：判断下列4种图形各属什么类型？ 7.1 图的概念
#define n 6 /*顶点数*/ #define e 8 /*边数*/ typedef char vextype; typedef float adjtype; typedef struct { vextype vexs[n]; adjtype arcs[n][n]; }graph;
1, 如果 < Vi , Vj > E 或者 (Vi , Vj ) E A[i ][ j ] = 否则 0,
7.2.1 邻接矩阵表示法
有向图的邻接矩阵
V1
V2
vexs=
V1 V2 V3 V4
V1 V2 V3 V4
V3
V4
0 0 arcs= 0 1
1 0 0 0
1 0 0 0
0 0 1 0
V1
V2
V3
V4
有向图的邻接矩阵一定不对称吗？
不一定，例如有向完全图。
7.2.1 邻接矩阵表示法
有向图的邻接矩阵
V1 V2
顶点的入度：在有向图中，顶点v的入度是指以该顶点为弧 头的弧的数目，记为ID (v)； 顶点的出度：在有向图中，顶点v的出度是指以该顶点为弧 尾的弧的数目，记为OD (v)。 顶点的度：有向图中，入度与出度之和。 如：v1的入度为1，出度为2，度为3。 在具有 n 个顶点、 e 条边的有向图 G 中，各顶点的入度之和与各顶点的 出度之和的关系？与边数之和的关 系？ V1 V2
无向图的邻接矩阵
vexs= V1 V4 V1 V2 V3 V4
V1 V2 V3 V4
V2
V3
0 1 arcs= 0 1
1 0 1 1
0 1 0 0
1 1 0 0
V1 V2 V3
V4
ቤተ መጻሕፍቲ ባይዱ
如何求顶点 i 的所有邻接点？
将数组中第 i 行元素扫描一遍，若arcs[i][j]为1，则 顶点 j 为顶点 i 的邻接点。
第七章 图
1
2 3 4 5
图的概念 图的存储
图的遍历 生成树和最小生成树
最短路径
7.1 图的概念
1、图的定义：记为 G＝( V, E ) 其中：V 是G的顶点集合，是有穷非空集； E 是G的边集合，是有穷集。
问：当E(G)为空时，图G存在否？ 答：存在！但此时图G只有顶点而没有边。
V为顶点(vertex) E为边(edge)
3、图的基本术语
7.1 图的概念
1）简单图：在图中，若不存在顶点到其自身的边， 且同一条边不重复出现。 V1 V3 V4 非简单图 V5 V4 非简单图 V2 V1 V3 V5 V2 V1 V2
V3 V4
简单图 V5
数据结构中讨论的都是简单图。
2）邻接、关联 无向图中，对于任意两个顶点 vi和顶点 vj，若存在边 (vi， vj)，则称顶点 vi和顶点 vj互为邻接点，同时称边 (vi，vj)关联于顶点vi和顶点vj。 V2 V1
7.2.1 邻接矩阵表示法
无向图的邻接矩阵
vexs=
V1 V2 V3 V4
V1 V2 V3 V4
V1
V4
V2
V3
0 1 arcs= 0 1
1 0 1 1
0 1 0 0
1 1 0 0
V1
V2
V3 V4
无向图的邻接矩阵特点？ 主对角线为 0 且一定是对称矩阵。
7.2.1 邻接矩阵表示法
无向图的邻接矩阵
0或 ∞
V1 5
2
7 8
V2
V3
V4
∞ 2 ∞ ∞ arcs= ∞ ∞ 7 ∞
5 ∞ ∞ ∞
∞ ∞ 8 ∞
建立无向网络邻接矩阵步骤： 建立无向网络的邻接矩阵算法： （1）读入n个顶点信息，建 Void CREATGRAPH(graph *ga) { int i,j,k; float w; 立顶点表； （2）邻接矩阵初始化，即 for (i=0;i<n;i++) arcs[i][j]=0; ga->vexs[i]=getchar(); （3）读入e条边，修改相应 for(i=0;i<n;i++) 的arcs[i][j]的值。 for(j=0;j<n;j++) ga->arcs[i][j]=0; 注意：
3 4 1 2 ^ 0 ^
v3 v4
v4
4
4 3
3
2 2
1
0 1
^
^ ^
思考:如何求结点的度? 例2：有向图的邻接表
v0 v2 v1 v3
V0 V1 ^ V2
注：邻接表不唯一，因各个边结点的链入顺序是任意的。
邻接表(出边)
2 3 ^ 1 ^
逆邻接表(入边)
V0 V1 3 ^
0 ^
0 ^ 2 ^
V2
V3
小结： 邻接矩阵法优点： 容易实现图的操作，如：求某顶点的 度、判断顶点之间是否有边（弧）、找顶 点的邻接点等等。 邻接矩阵法缺点： n个顶点需要n*n个单元存储边(弧); 空间效率为O(n2)。 对稀疏图而言尤其浪 费空间。
改进方法：利用邻接表来表示 。
7.2.2 邻接表表示法
对每个顶点Vi建立一个单链表，把与Vi相邻接的所有顶点Vj 链接起来，构成顶点Vi的邻接表。 顶点表结点 边表结点
V3
V4
0 0 arcs= 0 1
1 0 0 0
1 0 0 0
0 0 1 0
V1
V2
V3
V4
如何求顶点 i 的入度？
邻接矩阵的第 i 列非零元素个数。
7.2.1 邻接矩阵表示法
有向图的邻接矩阵
V1 V2 vexs= V1 V2 V3 V4
V1 V2 V3 V4
V3
V4
0 0 arcs= 0 1
1 0 0 0
无向完全图
无向图(树)
有向图
有向完全图
G1的顶点集合为V(G1)={0,1,2,3} 边集合为E(G1)={(0,1),(0,2),(0,3),(1,2),(1,3),(2,3)} G3的顶点集合为V(G3)={0,1,2} 弧的集合为E(G3)={<0,1>,<1,0>,<1,2>} <0,1>表示顶点0到顶点1的一条弧。（有序对）
无向图：修改arcs[i][j]， 同时修改相应的arcs[j][i]; 有向图：只需要修改 arcs[i][j]。 } for(k=0;k<e;k++) { scanf(“%d,%d,%f”,&i,&j,&w); ga->arcs[i][j]=w; ga->arcs[j][i]=w; }
7.2.1 邻接矩阵表示法
vertex
顶点域： 存放顶点 vi 的信息
link
边表头指针： 指向单链表的 第一个结点
adjvex
邻接点域：表 示vi一个邻接 点的位置
next
链域：指向 vi下一个边 或弧的结点
所有顶点表头结点用顺序存储结构存储。
例1：无向图的邻接表
v0 v2 v1
邻接表 0 v0 1 v1 2 v2 3 v3 4 v4
V1 到V4的路径： V1 V4 V1 V2 V3 V4 V1 V2 V5V3 V4
V1
V3 V4
V2
V5
一般情况下，图中的路径不唯一。 路径长度：该路径上边的数目。
7.1 图的概念
回路（环）：第一个顶点和最后一个顶点相同的路径。 简单路径：序列中顶点不重复出现的路径。 简单回路（简单环）：除了第一个顶点和最后一个顶点外，其 余顶点不重复出现的回路。
无向图的邻接矩阵
vexs= V1
V4 V1 V2 V3 V4
V1 V2 V3 V4
V2
V3
0 1 arcs= 0 1
1 0 1 1
0 1 0 0
1 1 0 0
V1
V2
V3 V4
如何判断顶点 i 和 j 之间是否存在边？ 测试邻接矩阵中相应位置的元素arcs[i][j]是否为1。
7.2.1 邻接矩阵表示法