第七章图( Graph) 2007.9
第七章 图 (Graph) 2007.9
主要内容 71图的基本概念 72图的存储结构 73图的遍历 74生成树和最小生成树
主要内容 7.1 图的基本概念 7.2 图的存储结构 7.3 图的遍历 7.4 生成树和最小生成树
7.1图的基本概念
7.1 图的基本概念
1.图的定义 图G由两个集合构成,记作G=<E>其中 V( vertex)是顶点的非空有限集合 E(edge)是边的有限集合,而边是顶点对的集合。 VO V2 V3 V4 G1=<V1,E1> V1={vo,v1,V2,w3,v4 E1={(vo,V1),(vo,vy3),(v1,V2),(v,v4),(v2,v3)(v2,v)}
1. 图的定义 G1=<V1,E1> V1={v0 ,v1,v2,v3,v4} E1={(v0,v1),(v0,v3),(v1,v2),(v1,v4),(v2,v3)(v2,v4)} V0 V3 V4 V1 V2 • 图G由两个集合构成，记作G=<V,E> 其中: • V（vertex）是顶点的非空有限集合 • E（edge）是边的有限集合，而边是顶点对的集合
图的应用举例: 例1交通图(公路、铁路) 顶点:地点 边:连接地点的公路 交通图中的有单行道双行道,分别用有向边、无向边表示; 例2电路图 顶点:元件 边:连接元件之间的线路 例3通讯线路图 顶点:地点 边:地点间的连线 例4各种流程图 如产品的生产流程图 顶点:工序 边:各道工序之间的顺序关系
例1 交通图（公路、铁路） 顶点：地点 边：连接地点的公路 交通图中的有单行道双行道，分别用有向边、无向边表示； 例2 电路图 顶点：元件 边：连接元件之间的线路 例3 通讯线路图 顶点：地点 边：地点间的连线 例4 各种流程图 如产品的生产流程图 顶点：工序 边：各道工序之间的顺序关系 图的应用举例：