第七章图
第七章 图
7.1 图的基本概念 7.2 图的存储表示 7.3 图的遍历 7.4最小生成树 7.5 最短路径 7.6有向无环图及其应用
7.1 图的基本概念 7.2 图的存储表示 7.3 图的遍历 7.4 最小生成树 7.5 最短路径 7.6 有向无环图及其应用
图的基本概念 图(Graph)是由顶点集合(Vertex)及顶点间的关系集 合(Edge)组成的一种数据结构： Graph=(V,E) 其中V={x|x某个数据对象} 是顶点的有穷非空集合 E=x,y)Ix,y∈V} 或E=x,yp|xy∈V&&.Path(x,y} 是顶点之间关系的有穷集合
图（Graph）是由顶点集合(Vertex)及顶点间的关系集 合(Edge)组成的一种数据结构： Graph＝( V, E ) 其中 V = { x | x 某个数据对象} 是顶点的有穷非空集合 E = {(x, y) | x, y V } 或E = {<x, y> | x, y V && Path (x, y)} 是顶点之间关系的有穷集合 图的基本概念
。 有向图与无向图 在有向图中，顶点对Sx,y>是有序的： 在无向图中，顶点对（仪，y)是无序的。 2 3 5 3 V4
◼ 有向图与无向图 在有向图中，顶点对 <x, y> 是有序的； 在无向图中，顶点对(x, y)是无序的。 v1 v3 v4 v5 v2 v1 v2 v3 v4
。完全图 若有n个顶点的无向图有n(n-1)/2条边，即 如果图中任意两个顶点之间都存在一条边，则此 图为完全无向图。 若有n个顶点的有向图有n(n-1)条边，即图 中任意两个顶点之间都存在方向相反的两条弧， 则此图为完全有向图
◼ 完全图 若有 n 个顶点的无向图有 n(n-1)/2 条边, 即 如果图中任意两个顶点之间都存在一条边，则此 图为完全无向图。 若有 n 个顶点的有向图有n(n-1) 条边, 即图 中任意两个顶点之间都存在方向相反的两条弧， 则此图为完全有向图