资源描述：
《数据结构 教学课件 ppt 作者 李学刚电子课件源代码 单元5 图.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、数据结构教学目标【知识目标】了解图的有关概念掌握图的邻接矩阵和邻接表的存储表示方法掌握图的遍历，深度优先搜索遍历和广度优先搜索遍历的算法掌握最小生成树的求解过程和算法【能力目标】具有恰当的选择图作为数据的逻辑结构的能力具有应用图解决实际问题的能力引例描述——城市间公路网建设最经济方案有6个城市（上海、苏州、常州、南京、扬州、南通），已知城市间拟建公路的建设费用，如图5-1所示，要建设一个连接6个城市的交通网，使得任意两个城市间都可以直接或间接互达，使总的费用最少。请问：如何建造6个城市间的公路网？演示执行21．图（Graph）的二元组定义图G由两个集合V和E组成，记为：G=(V
2、，E)其中：V是有限的非空集合，V中的元素称为顶点（Vertex）或结点，E是V中顶点偶对(vi,vj)的集合，E中的元素称为边（Edge）。说明：图G的顶点集和边集也可记为V(G)和E(G)。E(G)可以是空集，若为空，则图G只有顶点没有边；图中的边(vi,vj)描述了两个顶点之间是相关的。5.1图的概念知识储备【示例】在图5-2中的图G1中：集合V＝{v1,v2,v3,v4,v5}；集合E＝{(v1,v2),(v1,v4),(v2,v3),(v2,v5),(v3,v4),(v3,v5)}。V1V4V2V5V3图5-2无向图G122．无向图和有向图（1）无向图（Undirec
3、tedGraph）若图G中的每条边都是没有方向的，则称G为无向图。无向图中边的表示：无向图中的边均是顶点的无序对，无序对通常用圆括号表示，无序对(vi,vj)和(vj,vi)表示图中的同一条边。（2）有向图（DirectedGraph）若图G中的每条边都是有方向的，则称G为有向图。有向图中边的表示：有向图中的边是由顶点的有序对组成，有序对通常用尖括号表示，有序对和表示的是图中不同的边。有向边也称为弧，边的始点称为弧尾，终点称为弧头。2说明：①若(v1，v2)或是E(G)中的一条边，则要求v1≠v2；②不允许一条边在图中重复出现；③不允许
4、在同一个图中既有有向边又有无向边。如图5-3所示图G2是一个有向图：G2=(V2,E2)，V2={v1,v2,v3,v4}，E2={,,,}（3）完全图（CompleteGraph）①无向完全图：若G是具有n个顶点e条边的无向图，则顶点数与边数的关系为0≤e≤n(n-1)/2。把恰有n(n-1)/2条边的无向图称为无向完全图。②有向完全图：若G是具有n个顶点e条边的有向图，则顶点数与边数的关系为0≤e≤n(n-1)。把恰有n(n-1)条边的有向图称为有向完全图。23．图的边和顶点的关系（1）无向边和顶点关系若(vi,vj)
5、是一条无向边，则称顶点vi和vj互为邻接顶点，或称vi和vj相邻接；并称(vi,vj)依附或关联于顶点vi和vj，或称(vi,vj)与顶点vi和vj相关联。（2）有向边和顶点关系若是一条有向边，则称顶点vi邻接到vj，顶点vi邻接于顶点vj；并称边关联于vi和vj或称与顶点vi和vj相关联。（3）顶点的度①无向图中顶点v的度：无向图中顶点v的度是关联于该顶点的边的数目，记为D(v)。②有向图顶点v的入度：有向图中，以顶点v为终点的边的数目称为v的入度，记为ID(v)。③有向图顶点v的出度：有向图中，以顶点v为始点的边的数目，称为v的出度
6、，记为OD(v)④有向图顶点v的度：有向图中，顶点v的度定义为该顶点的入度和出度之和，即D(v)=ID(v)+OD(v)。⑤无论有向图还是无向图，顶点数n、边数e和度数之间有如下关系：【示例】在图5-2无向图G1中有：D(v1)=2，D(v2)=3，D(v3)=3，D(v4)=2，D(v5)=2。在图5-3有向图G2中有：ID(v1)=1，OD(v1)=2，D(v1)=3；ID(v2)=1，OD(v2)=0，D(v2)=1；ID(v3)=1，OD(v3)=1，D(v3)=2；ID(v4)=1，OD(v4)=1，D(v4)=2。V1V3V2V4图5-3有向图G2V1V4V2V5V
7、3图5-2无向图G14．子图（SubGraph）设G=(V，E)是一个图，若V‘是V的子集，E’是E的子集，且E‘中的边所关联的顶点均在V’中，则G‘=(V’，E‘)也是一个图，并称其为G的子图。5．路径（1）无向图的路径在无向图G中，若存在一个顶点序列vp，vi1，vi2，…，vim，vq，使得(vp,vi1)，(vi1,vi2)，…，(vim,vq)均属于E(G)，则称该序列为顶点vp到vq的一条路径。（2）有向图的路径在有向图G中，若存在一个顶点序列vp，vi1，vi2，…，vim，v
