第9章图 图的基本概念 图的存储结构 主图的实现 要丿图的遍历 和〈最小生成树 识 最短路径 拓扑排序 关键路径
第 9 章 图 图的基本概念 图的存储结构 图的实现 图的遍历 最小生成树 最短路径 拓扑排序 关键路径 主要知识点
9.1图 1图的基本概念 图是由顶点集合及顶点间的关系集合组成的一种数据结构。图 G的定义是:G=(V,E) 其中,V={xx∈某个数据元素集合} E={(x,y),y∈V}或 E={<x,y>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)或<vy> (2)有向图和无向图:在有向图中,顶点对<x,y>是有序 的,顶点对<x,y>称为从顶页点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中,若<u,v>是E(G)中的一条边,则称顶点n邻 接到顶点v,顶点邻接自顶点u,并称边<u,v>和顶点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)有向完全图