第8章图 图的基本概念 >图的基本运算 >图的基本存储结构 图的遍历 >生成树与最小生成树 >最短路径 >拓扑排序 >关键路径
第８章 图 ➢图的基本概念 ➢ 图的基本运算 ➢生成树与最小生成树 ➢拓扑排序 ➢ 图的基本存储结构 ➢最短路径 ➢关键路径 ➢ 图的遍历
8.1图的基本概 图的定义 图是由一个非空的顶点集合和一个描述顶点之间 多对多关系的边(或弧)集合组成的一种数据结构 它可以形式化地表示为 图=(V,E) 其中v=X∈某个数据对象集},它是顶点的有穷 非空集合;E={(x,y)X,yeV或E={X,y>|X yeV且P(x,y)},它是顶点之间关系的有穷集合 也叫做边集合,P(x,y)表示从x到y的一条单向 通路
8.1 图的基本概念 一、图的定义 图是由一个非空的顶点集合和一个描述顶点之间 多对多关系的边（或弧）集合组成的一种数据结构， 它可以形式化地表示为： 图＝（V，E） 其中V={x|x某个数据对象集}，它是顶点的有穷 非空集合；E={（x，y）|x，yV}或E={<x，y>|x， yV且P（x，y）}，它是顶点之间关系的有穷集合， 也叫做边集合，P（x，y）表示从x到y的一条单向 通路
图的应用举例 例1交通图(公路、铁路) 顶点:地点 边:连接地点的公路 交通图中的有单行道双行道,分别用有向边、无向边表示; 例2电路图 顶点:元件 边:连接元件之间的线路 例3通讯线路图 V3 V4) 顶点:地点 边:地点间的连线 例4各种流程图 如产品的生产流程图 顶点:工序 V2 V3 边:各道工序之间的顺序关系
图的应用举例 例1 交通图（公路、铁路） 顶点：地点 边：连接地点的公路 交通图中的有单行道双行道，分别用有向边、无向边表示； V0 V3 V4 V1 V2 V0 V1 V2 V3 例2 电路图 顶点：元件 边：连接元件之间的线路 例3 通讯线路图 顶点：地点 边：地点间的连线 例4 各种流程图 如产品的生产流程图 顶点：工序 边：各道工序之间的顺序关系
通常,也将图G的顶点集和边集分别记为∨(G) 和E(G)。E(G)可以是空集,若E(G)为空 则图G只有顶点而没有边。 若图G中的每条边都是有方向的,则称G为有向 图。在有向图中,一条有向边是由两个顶点组成的有 序对,有序对通常用尖括号表示。例如,有序对<v, v>表示一条由到v的有向边。有向边又称为弧,弧 的始点称为弧尾,弧的终点称为弧头。若图G中的每 条边都是没有方向的,则称G为无向图。无向图中的 边均是顶点的无序对,无序对通常用圆括号表示
通常，也将图G的顶点集和边集分别记为V（G） 和E（G）。E（G）可以是空集，若E（G）为空， 则图G只有顶点而没有边。 若图G中的每条边都是有方向的，则称G为有向 图。在有向图中，一条有向边是由两个顶点组成的有 序对，有序对通常用尖括号表示。例如，有序对<vi， vj>表示一条由vi到vj的有向边。有向边又称为弧，弧 的始点称为弧尾，弧的终点称为弧头。若图G中的每 条边都是没有方向的，则称G为无向图。无向图中的 边均是顶点的无序对，无序对通常用圆括号表示
例图8-1 有序对<vv 用以为v起点、以v为终点 的有向线段表示,称为有向 边或弧; (a)有向图G1(b)无向图 图81(a)表示的是有向图G1,该图的顶点集和 边集分别为 V(G1)={1,v2,V3,V4 E(G1)=
图8-1 v1 v2 v3 v4 v1 v2 v4 v5 v3 （a）有向图G1（b）无向图 G2 图8.1（a）表示的是有向图G1，该图的顶点集和 边集分别为： V（G1）={v1，v2，v3，v4 } E（G1）={<v1，v2>，<v1，v3>，<v2，v4>，<v3，v2>} 例 有序对<vi ,vj> ： 用以为vi起点、以vj为终点 的有向线段表示，称为有向 边或弧；