数据结构第7章 图(第一讲).pptVIP

第七章 图(第一讲) 第7章 图 教学内容： 1、图的基本概念 2、图的存储结构（邻接矩阵、邻接表）； 3、图的遍历（深度优先有哪些信誉好的足球投注网站、广度优先有哪些信誉好的足球投注网站）； 4、最小生成树（kruskul算法、prim算法）； 5、最短路径（dijkstra算法、floyd算法）; 6、AOV网络与拓扑排序； 7、AOE网络与关键路径。 引言 图（Graph）是一种较线性表和树更为复杂的数据结构。 图形结构中，结点之间 的关系可以是任意的，任意两个数据元素之间都可能相关。 应用广泛: 如电路网络分析、交通运输、管理与线路的铺设、印刷电路板与集成电路的布线等众多直接与图有关的问题，它们必须用图的有关方法进行处理； 另外像工作的分配、工程进度的安排、课程表的制订、关系数据库的设计等许多实际问题，如果间接地用图来表示，处理起来比较方便。 问题的提出 假设有”平顶山”、”郑州”、”洛阳”、”许昌”、”漯河”五城市的交通图如下,完成如下要求： 1：对任意输入的两个城市，输出它们之间的直接距离，有则输出实际距离，无则输出道路不直接相通。 2：对任意一个城市，输出都能够直接通达哪些城市，距离多少？ 第7章 图 7.1 图的定义和术语 7.2 图的存储结构 7.3 图的遍历操作 7.4 图的连通性问题 7.5 有向无环图及其应用 7.6 最短路径 复习并回答问题 1、以下图为例，理解图的相关术语，并回答有关问题。 11、生成树、生成森林： 一个连通图(无向图)的生成树是一个极小连通子图，它含有图中全部n个顶点和只有足以构成一棵树的n-1条边，称为图的生成树。 关于无向图的生成树的几个结论： ◆ 一棵有n个顶点的生成树有且仅有n-1条边； ◆ 如果一个图有n个顶点和小于n-1条边，则是非连通图； 第7章 图 7.1 图的定义和术语 7.2 图的存储结构 7.3 图的遍历操作 7.4 图的连通性问题 7.5 有向无环图及其应用 7.6 最短路径 插入或删除顶点 InsertVex(G, v); //在图G中增添新顶点v。 DeleteVex(G, v); // 删除G中顶点v及其相关的弧。 插入和删除弧 InsertArc(G, v, w); // 在G中增添弧v,w，若G是无向的， //则还增添对称弧w,v。 DeleteArc(G, v, w); //在G中删除弧v,w，若G是无向的， //则还删除对称弧w,v。 遍 历 DFSTraverse(G, v, Visit()); //从顶点v起深度优先遍历图G，并对每 //个顶点调用函数Visit一次且仅一次。 BFSTraverse(G, v, Visit()); //从顶点v起广度优先遍历图G，并对每 //个顶点调用函数Visit一次且仅一次。 7.2 图的存储表示 一、图的数组(邻接矩阵)存储表示 二、图的邻接表存储表示 三、有向图的十字链表存储表示 四、无向图的邻接多重表存储表示 7.2.1 邻接矩阵存储方法 邻接矩阵是表示顶点之间相邻关系的矩阵。设G=(V,E)是具有n(n＞0)个顶点的图,顶点的顺序依次为(v1,…,vn),则G的邻接矩阵A是n阶方阵,其定义如下： (1) 如果G是无向图,则： A[i][j]= 1:若(vi,vj)∈E(G) 0:其他 (2) 如果G是有向图,则： A[i][j]= 1:若vi,vj∈E(G) 0:其他 对称矩阵 如果是网（即带权图）呢？ (3) 如果G是带权无向图,则： A[i][j]= wij :若vi≠vj且(vi,vj)∈E(G) ∞:其他 (a) 带权无向图 3 5 4 1 2 6 a b c d e 3 (b) 邻接矩阵 ∞ 6 2 ∞ ∞ 6 ∞ 3 4 3 2 3 ∞ 1 ∞ ∞ 4 3 ∞ 5 ∞ 3 ∞ 5 ∞ (b) 邻接矩阵 ∞ 6 2 ∞ ∞ ∞ ∞ ∞ ∞ 3 ∞ 3 ∞ 1 ∞ ∞ 4 ∞ ∞ 5 ∞ ∞ ∞ ∞ ∞ (a) 带权有向图 3 5 4 1 2 6 a b c d e 3 (4) 如果G是带权有向图,则： A[i][j]= wij :若vi≠vj且vi,vj∈E(G) ∞:其他 思考题： 　　对于有n个顶点e条边的无向图，邻接矩阵表示时有多少个元素，多少个非0元素？ 　　对于有n个