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