第九章 9图的基本概念 92图的存储结构 93图的遍历 94生成树和最小生成树 95最短路径
启迪管理课程 1 9.1 图的基本概念 9.2 图的存储结构 9.3 图的遍历 9.4 生成树和最小生成树 9.5 最短路径 第九章 图
91图的基本概念的定义 图G的定义:由顶点( Vertex)或结点 Node)的一个非空有限集和一个边 (edge)或弧(Arc)的有限集组成。 是否存在“空图”? ●仄点:图中的数据元素,用v表示顶点 的有限非空集 边:两顶点之间的关系,用E表示边的 有限集 ●有向图:图G中的每条边都是有方向的, 则称图为有向图。否则称为无向图
启迪管理课程 2 9.1 图的基本概念－－图的定义 ⚫ 图(G)的定义：由顶点（Vertex)或结点 （Node)的一个非空有限集和一个边 （edge)或弧（Arc)的有限集组成。 是否存在“空图”？ ⚫ 顶点：图中的数据元素，用V表示顶点 的有限非空集 ⚫ 边：两顶点之间的关系，用E表示边的 有限集 ⚫ 有向图：图G中的每条边都是有方向的， 则称图为有向图。否则称为无向图。 V1 V2 V3 V4 G1 V1 V2 V4 V5 V3 G2
91图的基本概念的定义 在有向图,一条边是由两个顶点组成的 有序对,用尖括号表示,如G1中的<v1v2>。 这样的边又称为弧,v1为弧的起点,称为弧 尾(Tai);v2为弧的终点,称为弧头Head) 则图G可表示为:G1(V1,E 其中Vv12V3V4} E{<v1V2>,<V13>,V3,v4>,V4V1 注:<x,y表示优到的一条弧ar,x为弧(taiD y为弧义(head
启迪管理课程 3 在有向图中，一条边是由两个顶点组成的 有序对，用尖括号表示，如G1中的 <v1 ,v2>。 这样的边又称为弧，v1为弧的起点，称为弧 尾（Tail)；v2为弧的终点，称为弧头(Head)。 则图G1可表示为：G1=(V1 ,E1 ) 其中:V1={v1 ,v2 ,v3 ,v4 } E1={<v1 ,v2>,<v1 ,v3>,<v3 ,v4>,<v4 ,v1>} v1 v2 v3 v4 G1 9.1 图的基本概念－－图的定义 注：<x, y>表示从x到y的一条弧(arc),x为弧尾(tail)， y为弧头(head)
91图的基本概念的定义 而在无向图中,一条边是由两个顶点的无序对组成, 用圆括号表示,如G2中的(V1,V2) 图G2可表示为:G2=(v2,E2) 其中:V2={v12345} E2={(v1,2),(v1,v4),(v2,v3),(v2v5),(V3,v4),(3,5) 注:(,y表示从到之门的一条连线,称为边eg A注意:① ⑩ ①②
启迪管理课程 4 v1 v2 v4 v5 v3 G2 而在无向图中，一条边是由两个顶点的无序对组成， 用圆括号表示 ,如G2中的(V1 , V2 )。 图G2可表示为：G2=(V2 ,E2 ) 其中：V2={v1 ,v2 ,v3 ,v4 ,v5 } E2={(v1 ,v2 ),(v1 ,v4 ),(v2 ,v3 ),(v2 ,v5 ),(v3 ,v4 ),(v3 ,v5 )} 9.1 图的基本概念－－图的定义 注：(x, y)表示从x到y之间的一条连线，称为边(edge)
91图的基本概念的基本术语 完全图 假设<v,v>∈E,(则诮,即无顶点到自身的弧;(2) 两顶点间没有多条边的情况 ●有向完全图:有向图中的每两个顶点之间都存在着 方向相反的两条边有n个顶点的有向完全图有n(n-1)边 无向完全图:无向图中的每两个顶点之间都存在着 条边。有n个顶点的无向完全图有mn-1)2边 °稠密图、帮图 3 3 当一个图接近完全图时,则称为稠密图相反,当一个 图含有较少的边数(即当e<<n(n-1)时,则称为稀硫图
启迪管理课程 5 假设<vi ,vj>∈E，(1)则i≠j，即无顶点到自身的弧;(2) 两顶点间没有多条边的情况 ⚫ 有向完全图：有向图中的每两个顶点之间都存在着 方向相反的两条边. ⚫ 无向完全图：无向图中的每两个顶点之间都存在着 一条边。 2 1 3 2 1 3 有向完全图 无向完全图 有n个顶点的有向完全图有 边 有n个顶点的无向完全图有n(n-1)/2 边 n(n-1) 9.1 图的基本概念－－图的基本术语 完全图 当一个图接近完全图时，则称为稠密图。相反，当一个 图含有较少的边数(即当e<<n(n-1))时，则称为稀疏图。 稠密图、稀疏图