第9章图 图的基本概念 图的存储结构 主图的实现 要丿图的遍历 和〈最小生成树 识 最短路径 拓扑排序 关键路径
第 9 章 图 图的基本概念 图的存储结构 图的实现 图的遍历 最小生成树 最短路径 拓扑排序 关键路径 主要知识点
9.1图 1图的基本概念 图是由顶点集合及顶点间的关系集合组成的一种数据结构。图 G的定义是:G=(V,E) 其中,V={xx∈某个数据元素集合} E={(x,y),y∈V}或 E={kx,y∈Ⅴ并且Path(x,y 其中,(x,y)表示从x到y的一条双向通路,即(x,y)是 无方向的;Path(x,y)表示从x到y的一条单向通路,即 Path(x,y)是有方向的。 向题:图的特点
9.1 图 1.图的基本概念 图是由顶点集合及顶点间的关系集合组成的一种数据结构。图 G的定义是： G =（V，E） 其中，V = {x|x∈某个数据元素集合} E ={(x，y)|x，y∈V} 或 E = {＜x， y＞|x，y∈V并且Path(x， y)} 其中，（x，y）表示从 x到 y的一条双向通路，即（x，y）是 无方向的；Path（x，y）表示从 x到 y的一条单向通路，即 Path（x，y）是有方向的。 问题：图的特点
图有许多复杂结构,本课程只讨论最基本的图,因此, 本章讨论的图中不包括从自身到自身的边存在的图,以 及带自身环的图 (a)
图有许多复杂结构，本课程只讨论最基本的图，因此， 本章讨论的图中不包括从自身到自身的边存在的图，以 及带自身环的图 B C A A B C D (a) (b)
基本术语 (1)顶点和边:图中的结点一般称作顶点,图中的第个顶 点记做v。两个顶点v和v相关联称作顶点v和v之间有一条边, 图中的第条边记做c,=(vv)或 (2)有向图和无向图:在有向图中,顶点对是有序 的,顶点对称为从顶页点x到顶点y的一条有向边,有向图 中的边也称作弧;在无向图中,顶点对(x,y)是无序的,顶点 对(x,y)称为与顶点x和顶点y相关联的一条边 (3)完全图:在有n个顶点的无向图中,若有n(n-1)2条边, 即任意两个顶点之间有且只有一条边,则称此图为无向完全图 在有n个顶点的有向图中,若有n(mx-1)条边,即任意两个顶点 之间有且只有方向相反的两条边,则称此图为有向完全图
基本术语： （1）顶点和边：图中的结点一般称作顶点，图中的第i个顶 点记做vi。两个顶点vi和vj相关联称作顶点vi和vj之间有一条边， 图中的第k条边记做ek，ek =（vi , vj）或＜vi , vj＞。 （2）有向图和无向图：在有向图中，顶点对＜x, y＞是有序 的，顶点对＜x, y＞称为从顶点x到顶点y的一条有向边，有向图 中的边也称作弧；在无向图中，顶点对（x, y）是无序的，顶点 对（x, y）称为与顶点x和顶点y相关联的一条边。 （3）完全图：在有n个顶点的无向图中，若有n(n-1)/2条边， 即任意两个顶点之间有且只有一条边，则称此图为无向完全图 ；在有n个顶点的有向图中，若有n(n-1)条边，即任意两个顶点 之间有且只有方向相反的两条边，则称此图为有向完全图
3 3 (a)无向完全图 (b)无向图 (c)有向图 (d)有向完全图 (4)邻接顶点:在无向图G中,若(u,u)是E(O中的一条边 ,则称和v互为邻接顶点,并称边(u,)依附于顶点u和v; 在有向图G中,若是E(G)中的一条边,则称顶点n邻 接到顶点v,顶点邻接自顶点u,并称边和顶点u和顶 点关联
（4）邻接顶点：在无向图G中，若（u,v）是E(G)中的一条边 ，则称u和v互为邻接顶点，并称边（u,v）依附于顶点u和v； 在有向图G中，若＜u,v＞是E(G)中的一条边，则称顶点u邻 接到顶点v，顶点v邻接自顶点u，并称边＜u,v＞和顶点u和顶 点v相关联。 。 0 1 3 2 0 1 2 3 4 5 6 0 1 2 0 1 2 3 (a)无向完全图 (b)无向图 (c)有向图 (d)有向完全图
(5)顶点的度:顶点v的度是与它相关联的边的条数,记作 TD(v)。顶点的度=入度+出度 (6)路径:在图G=(V,E)中,着从顶点出发有一组边使可到 达页点%,则称质点v到顶点的顶点序列为从顶点到顶点v 的路径 (7)权:有些图的边附带有数据信息,这些附带的数据信息 称为权。带权的图也称作网络或网。 (8)路径长度:对于不带权的图,一条路径的路径长度是指 该路径上的边的条数;对于带权的图,一条路径的路径长度是 指该路径上各个边权值的总和。 (9)子图:设有图G={VE和图G2={V2E2},着VV2,且 EE2,则称图G2是图G的子图
（5）顶点的度：顶点v的度是与它相关联的边的条数，记作 TD(v)。顶点的度 = 入度 + 出度。 （6）路径：在图G=(V,E)中，若从顶点vi出发有一组边使可到 达顶点vj，则称顶点vi到顶点vj的顶点序列为从顶点vi到顶点vj 的路径 （7）权：有些图的边附带有数据信息，这些附带的数据信息 称为权。带权的图也称作网络或网。 （8）路径长度：对于不带权的图，一条路径的路径长度是指 该路径上的边的条数；对于带权的图，一条路径的路径长度是 指该路径上各个边权值的总和。 （9）子图：设有图G1={V1 ,E1 }和图G2={V2 ,E2 }，若V1V2，且 E1 E2，则称图G2是图G1的子图
B 10 60 12 6 L(3)7 15 3 35 6 E 16 施工进度图 交通网络图
2 1 3 5 4 6 7 8 7 9 6 10 6 127 15 16 3 B A C D E 60 30 45 75 80 40 35 施工进度图 交通网络图
(10)连通图和强连通图:在无向图中,若从顶点v到顶点 有路径,则称顶点和顶点是连通的。如果图中任意对页 点都是连通的,则称该图是连通图 在有向图中,若对于任意一对顶点v和顶点v(vv;)都存在 路径,则称图G是强连通图。 (11)生成树:一个连通图的最小连通子图称作该图的生成 树。有n个顶点的连通图的生成树有n个顶点和m-1条边。 生成树一般是对无向图来讨论。 (12)简单路径和回路:若路径上各顶点v,2…,n互不重复 ,则称这样的路径为简单路径;着路径上第一个顶点v与最后 一个顶点v重合,则称这样的路径为回路或环
（10）连通图和强连通图：在无向图中，若从顶点vi到顶点vj 有路径，则称顶点vi和顶点vj是连通的。如果图中任意一对顶 点都是连通的，则称该图是连通图。 在有向图中，若对于任意一对顶点vi和顶点vj（vi ≠vj）都存在 路径，则称图G是强连通图。 （11）生成树：一个连通图的最小连通子图称作该图的生成 树。有n个顶点的连通图的生成树有n个顶点和n-1条边。 生成树一般是对无向图来讨论。 （12）简单路径和回路：若路径上各顶点v1 ,v2 ,…,vm ,互不重复 ，则称这样的路径为简单路径；若路径上第一个顶点v1与最后 一个顶点vm重合，则称这样的路径为回路或环
2图的抽象数据类型 数据集合:由一组顶点集合v和一组边e集合组成。当为带 权图时每条边上权w还构成权集合Ww 操作集合: (1)初始化 Initiate(G,n (2)插入顶点 Insertvertex( G, vertex) (3)插入边 InsertEdgeG,vL,V2, weight) (4)删除边 Delete Edge(G,v1v2) (5)删除顶点 Delete vertex(G, vertex) (6)第一个邻接顶点 GetFirstvex(G,y) (7)下一个邻接顶点 GetNextvex(G,intv1,v2) (8)遍历 Depth FirstSearch(G
数据集合：由一组顶点集合{vi }和一组边{ej }集合组成。当为带 权图时每条边上权wj还构成权集合{wj }。 操作集合： （1）初始化Initiate(G, n) （2）插入顶点 InsertVertex(G, vertex) （3）插入边InsertEdgeG, v1, v2, weight) （4）删除边DeleteEdge(G, v1, v2) （5）删除顶点DeleteVertex(G, vertex) （6）第一个邻接顶点GetFirstVex(G, v) （7）下一个邻接顶点GetNextVex(G, int v1, v2) （8）遍历DepthFirstSearch(G) 2.图的抽象数据类型
92图的存储结构 图的存储结构主要有邻接矩阵和邻接表两种。 1.图的邻接矩阵存储结构 假设图G=(V,E有n个顶点,即{v,…,n},E可用如下 形式的矩阵4描述,对于中的每一个元素an,满足 若(vv)∈E或∈E 否则 由于矩阵A中的元素a1表示了顶点v和顶点v之间边的关系, 或者说,A中的元素a表示了顶点和页点(0产m1)的 邻接关系,所以矩阵A称作邻接矩阵
9.2 图的存储结构 图的存储结构主要有邻接矩阵和邻接表两种。 1.图的邻接矩阵存储结构 = 否则 若 或 0 1 (v ,v ) E v ,v E a i j i j ij 假设图G=(V,E)有n个顶点，即V={v0 ,v1 ,…,vn-1 }，E可用如下 形式的矩阵A描述，对于A中的每一个元素aij，满足： 由于矩阵A中的元素aij表示了顶点vi和顶点vj之间边的关系， 或者说，A中的元素aij表示了顶点vi和顶点vj（0≤j≤n-1）的 邻接关系，所以矩阵A称作邻接矩阵