Download presentation
Presentation is loading. Please wait.
1
第六章 图(一)
2
复习 Huffman树的构造方法 Huffman编码基本规则
3
第六章 图 6.1 图的定义和术语 6.2 图的存储结构 6.3 图的遍历 6.4 图的连通性问题 6.5 有向无环图及其应用
6.6 最短路径
4
本讲主要内容 理论: 主要讲解图的定义和术语、图的存储结构。 实验: 建立无向图(有向图)的邻接矩阵和邻接表算法。
5
6.1 图的定义和术语 图(Graph):图G是由两个集合V(G)和E(G)组成的,记为G=(V,E) 其中:V(G)是顶点的非空有限集
有向图:E(G)是有向边(也称弧)的有限集合,弧是顶点的有序对,记为<v,w>,v,w是顶点,v为弧尾,w为弧头 无向图:E(G)是边的有限集合,边是顶点的无序对,记为(v,w)或(w,v),并且(v,w)=(w,v)
6
E(G1)={(1,2), (1,3), (2,3), (2,4),(2,5), (5,6), (5,7)}
例 2 4 5 1 3 6 G1 图G1中:V(G1)={1,2,3,4,5,6} E(G1)={<1,2>, <2,1>, <2,3>, <2,4>, <3,5>, <5,6>, <6,3>} 例 1 5 7 3 2 4 G2 6 图G2中:V(G2)={1,2,3,4,5,6,7} E(G1)={(1,2), (1,3), (2,3), (2,4),(2,5), (5,6), (5,7)}
7
子图——如果图G(V,E)和图G’(V’,E’),满足:
V’V E’E 则称G’为G的子图 3 5 6 例 2 4 1 G G2
8
边/弧数目 用n 表示图中顶点数目,用e 表示图中边或弧的数目 有向图:0 ≤ e ≤ n(n-1) 有向完全图 e = n(n-1)
稀疏图: e < nlogn 稠密图 例 2 1 3 有向完全图 完全图
9
权、网 权:有些图对应每条边有一相应的数值。这个数值叫该边的权。 网:这种带权的图叫网。 注:不同网络的权有不同的意义:电网的权可以是阻抗,运输网络中的权可以是路程长度,运费等。
10
路径与连通性 邻接点:对无向图G=(V,E),若有(V1,V2)属于E则称V1和V2互为邻接点。
相关边:两个相邻接的点连成的边叫做这两个结点的相关边。 度:与每个顶点相连的边的数叫该点的度。记为TD(V) 无向图中,顶点的度为与每个顶点相连的边数 有向图中,顶点的度分成入度与出度 入度:以该顶点为头的弧的数目,记为ID(V) 出度:以该顶点为尾的弧的数目,记为OD(V) 例 1 5 7 3 2 4 G2 6 顶点5的度:3 顶点2的度:4 例 2 4 5 1 3 6 G1 顶点2入度:1 出度:3 顶点4入度:1 出度:0
11
路径:路径是顶点的序列V={Vi0,Vi1,……Vin},满足(Vij-1,Vij)E 或 <Vij-1,Vij>E(1<jn)
路径长度:指路径上边或弧的数目 回路:第一个顶点和最后一个顶点相同的路径叫~ 简单路径:序列中顶点不重复出现的路径叫~ 简单回路:除了第一个顶点和最后一个顶点外,其余顶点不重复出现的回路叫~
12
路径:1,2,3,5,6,3 路径长度:5 简单路径:1,2,3,5 回路:1,2,3,5,6,3,1 简单回路:3,5,6,3 例 2 4 5 1 3 6 G1 例 1 5 7 3 2 4 G2 6 路径:1,2,5,7,6,5,2,3 路径长度:7 简单路径:1,2,5,7,6 回路:1,2,5,7,6,5,2,1 简单回路:1,2,3,1
13
连通:从顶点V到顶点W有一条路径,则说V和W是连通的
连通图:图中任意两个顶点都是连通的叫~ 连通分量:非连通图的每一个连通部分叫~(极大连通子图) 强连通图:有向图中,如果对每一对Vi,VjV, ViVj,从Vi到Vj 和从Vj到 Vi都存在路径,则称G是~ 强连通分量:有向图中的极大强连通子图 生成树:极小连通子图,一个连通的生成树,它含有图中全部顶点,但只有足以构成树的N-1条边(N顶点个数) 极大、极小是就边数的多少而言的 连通图 例 2 4 5 1 3 6 3 5 6 例 强连通图 例 2 4 5 1 3 6 非强连通图 强连通分量
14
G3 D E I G H K A C B F L J M A C B F L J M A C B F L J M A C B F L J M 连通分量 D E 生成树 I G H K I G H K I G H K 思考:若无向图中有21条边,则: 1) 保持该图不连通至少应具有多少个顶点? 2) 保持该图连通至少有多少个顶点,至多有多少个顶点? 1) m个顶点形成完全图,另一个顶点与这m个顶点不连通 ½ m(m-1)=21 m=7 n=m+1=8 2) 至少有 7 个顶点(完全图),至多有22个顶点(生成树)
15
6.2 图的存储结构 图的存储表示分析 特点:顶点之间的关系是多对多(m : n)
也不适合用多重链表表示。 存储结构:数组表示法(邻接矩阵)、邻接表、多重邻接表、十字链表
16
多重链表 V1 V2 ^ ^ V4 ^ V3 ^ 例 G1 2 4 1 3 例 1 5 3 2 4 G2 ^ V1 V2 V4 ^ V5 ^
17
6.2 图的存储结构-邻接矩阵 数组表示法(邻接矩阵):表示顶点间相联关系的矩阵
定义:设G=(V,E)是有n1个顶点的图,G的邻接矩阵A是具有以下性质的n阶方阵 网的邻接矩阵定义: 其它
18
邻接矩阵 例 G1 2 4 1 3 例 1 5 3 2 4 G2 例 1 4 5 2
7 8 6
19
6.2 图的存储结构-邻接矩阵 无向图/网—对称矩阵 有向图/网—未必是对称矩阵 G3 G2 G1 V1 V2 V1 V2 V1 V2 V3
无向图/网—对称矩阵 有向图/网—未必是对称矩阵 G3 G2 G1 V1 5 V2 V1 V2 V1 V2 4 3 8 7 V3 V6 9 V3 6 1 V3 V4 5 V4 V5 V5 V4 5 V1的度: 第1行或列中值为1的元素个数 V1的出度 V1的入度 V1的出度 ∞ 5 ∞ 7 ∞ ∞ ∞ ∞ 4 ∞ ∞ ∞ 8 ∞ ∞ ∞ ∞ 9 ∞ ∞ 5 ∞ ∞ 6 ∞ ∞ ∞ 5 ∞ ∞ 3 ∞ ∞ ∞ 1 ∞
20
6.2 图的存储结构-邻接矩阵 特点: 无向图的邻接矩阵对称,可压缩存储;有n个顶点的无向图需存储空间为n(n+1)/2
无向图中顶点Vi的度TD(Vi)是邻接矩阵A中第i行元素之和 有向图中, 顶点Vi的出度是A中第i行元素之和 顶点Vi的入度是A中第i列元素之和
21
邻接矩阵法优点: 缺点: 容易实现图的操作,如:求某顶点的度、判断顶点之间是否有边(弧)、找顶点的邻接点等等。仅耗费 O(1) 时间。
n个顶点需要n*n个单元存储边(弧);空间效率为O(n2)。 对稀疏图而言尤其浪费空间。
22
建立无向网络邻接矩阵算法 G vexs[4] arcs[4][4] #define INFINITY 32767
typedef char vertype; typedef struct {vextype vexs[n]; int arcs[n][n]; int vexnum,arcnum; }AMGraph; A B C D vexs[4] ∞ arcs[4][4] G A C B D 无向网络 5 7 1 9 5 7 9 5 7 1 9 1
23
建立无向网络邻接矩阵算法 #define INFINITY 32767 typedef char vertype;
typedef struct {vextype vexs[n]; int arcs[n][n]; int vexnum,arcnum; }AMGraph; Status CreateGraph(AMGraph *G ){ int i,j,w; VexType v1, v2; // 输入顶点数、边数 scanf(“%d%d”, & G-> vexnum, G-> arcnum); for(i = 0; i< G-> vexnum; i++) // 读入所有的顶点 scanf(“%c”, & (*G). vexs[i]); for(i = 0; i < G-> vexnum; i++) //初始化邻接矩阵 for(j = 0; j< G-> vexnum; j++) G-> arcs[i][j] = INFINITY; for(i=0; i< G-> arcnum; i++) { // 输入所有的边 // 输入一条边依附的两个顶点和边上的权值 scanf(“%c%c%d”, &v1, &v2, &w); // 查询两个顶点在图中存储的位置 i = LocateVex(&G, v1); j = LocateVex(&G, v2); G-> arcs[i][j].adj = w; G-> arcs[j][i] = G-> arcs[i][j]; } return OK; } 23/
24
// 查找某个顶点在图中的存储位置(下标),找不到返回-1 int LocateVex(AMGraph *G, VexType vert){
int i; for(i=0; i< G-> vexnum; i++) if(G->vexs[i] = = vert) return i; return -1; } 24/
25
6.2 图的存储结构-邻接表 实现:为图中每个顶点建立一个单链表,第i个单链表中的结点表示依附于顶点Vi的边(有向图中指以Vi为尾的弧)
表结点: typedef struct node { int adjvex; //邻接点域,存放与Vi邻接的点在表头数组中的位置 struct node *next; //链域,指示下一条边或弧 }JD; 头结点: typedef struct tnode { int vexdata; //存放顶点信息 struct node *firstarc; //指示第一个邻接点 }TD; TD ga[M]; adjvex next vexdata firstarc
26
1 2 3 a c d b vexdata firstarc ^ adjvex next 例 G1 b d a c 1 2 3 a c d b vexdata firstarc ^ adjvex next 4 e 例 a e c b d G2
27
从无向图的邻接表可以得到如下结论: 无向图中顶点Vi的度为第i个单链表中的结点数 所有链表中结点数目的一半为图中边数;
占用的存储单元数目为n+2e 。 G2 V1 V2 V3 V4 V1的度 V5 V1 V2 V3 V4 V5 0 1 2 3 4 1 ^ 0 ^
28
逆邻接表:有向图中对每个结点建立以Vi为头的弧的单链表
从有向图的邻接表可以得到如下结论: 顶点Vi的出度为第i个单链表中的结点个数 顶点Vi的入度为整个单链表中邻接点域值是i的结点个数 所有链表中结点数目为图中弧数; 占用的存储单元数目为n+e 。 逆邻接表:有向图中对每个结点建立以Vi为头的弧的单链表 V1的出度 V1的入度 G1 V1 V2 V1 V2 V3 V4 0 1 2 3 3 ^ 0 ^ 2 ^ 逆邻接表—入边表 V1 V2 ^ V3 V4 0 1 2 3 1 ^ 0 ^ 3 ^ 邻接表—出边表 V3 V4
29
邻接表的优点: 邻接表的缺点: 空间效率高;容易寻找顶点的邻接点;
判断任意两顶点间是否有边或弧,需搜索两结点对应的单链表,没有邻接矩阵方便。
30
图的邻接表存储表示: #define MAX_VERTEX_NUM 20 struct ArcNode{
int adjvex; // 该弧所指向的顶点的位置 struct ArcNode *nextarc; // 指向下一条弧的指针 InfoType *info; // 网的权值指针 } ArcNode; // 表结点 typedef struct{ VertexType data; // 顶点信息 ArcNode *firstarc; // 第一个表结点的地址 } VNode, AdjList[MAX_VERTEX_NUM]; // 头结点 typedef struct { AdjList vertices; int vexnum,arcnum; // 图的当前顶点数和弧数 }ALGraph; 30/
31
采用邻接表表示法创建无向图 算法思想: (1)依次读入图的各顶点数据并将其存入到头结点数组中,并将表头结点数组的链域均置“空”;
(2)逐个输入表示边的顶点序号(i,j)。 对于每一个有效的顶点对(i,j) ,动态生成两个结点,它们的顶点域 分别为j,i,并分别插入到第i个和第j个链表(为简便起见,插入的位置为第一个结点之前)中。 31/
32
6.2 图的存储结构-十字链表(有向图) 有向图:邻接表-出边表:求入度不方便; 逆邻接表-入边表 十字链表: 弧结点数==弧数 弧结点:
typedef struct arcnode { int tailvex, headvex; //弧尾、弧头在表头数组中位置 struct arcnode *hlink;//指向弧头相同的下一条弧 struct arcnode *tlink; //指向弧尾相同的下一条弧 }AD; tailvex headvex hlink tlink 顶点结点: typedef struct dnode { int data; //存与顶点有关信息 struct arcnode *firstin;//指向以该顶点为弧头的第一个弧结点 struct arcnode *firstout; //指向以该顶点为弧尾的第一个弧结点 }DD; DD g[M]; data firstin firstout
33
例 b d a c a b c d 1 2 3 0 2 0 1 2 3 2 0 3 2 3 1 3 0 ^ ^ ^ ^ ^ ^ ^ ^
34
6.2 图的存储结构-邻接多重表(无向图) 无向图:邻接表的每条边对应2个表结点 多重邻接表: 边结点数==边数 边结点:
typedef struct node { int mark; //标志域 int ivex, jvex; //该边依附的两个顶点在表头数组中位置 struct node *ilink, *jlink; //分别指向依附于ivex和jvex的下一条边 }JD; mark ivex ilink jvex jlink 顶点结点: typedef struct dnode { int data; //存与顶点有关的信息 struct node *firstedge; //指向第一条依附于该顶点的边 }DD; DD ga[M]; //ga[0]不用 data firstedge
35
例 a e c b d 1 2 3 a c d b 4 e ^ ^ ^ ^ ^
36
小结 图的定义和术语 图(Graph)、有向图、无向图、子图、有向完全图 、完全图、稀疏图、稠密图、权、网、邻接点、相关边、度、路径、路径长度、回路、简单路径、简单回路、连通、连通图、连通分量、强连通图、强连通分量、生成树 图的存储方法 邻接矩阵、邻接表、十字链表 、邻接多重表 重点:图的邻接矩阵和邻接表的存储结构,建立无向网络邻接矩阵和邻接表的算法。
37
作业 1.讨论邻接表与邻接矩阵的异同之处 。 2.编写程序实现有向图的邻接矩阵和邻接表算法。
Similar presentations