数据结构-2004-02-06图1.pptVIP

算法与数据结构 第一章 绪 论 第二章 线 性 表 第三章 栈和队列 第四章 串和数组 第五章 二叉树和树 第六章 图和广义表 第七章 排 序 第八章 查 找 第九章 文 件 第六章 图及广义表 6.1 图定义和术语 6.2 图的存储结构 6.3 图的遍历:广度优先,深度优先 6.4 生成树 6.5 最短路径 6.6 拓扑排序 6.7 广义表 背景 * * 6.1 图的定义和术语 北京 天津 上海 公路网 图G是由两个集合V(G)和E(G)组成,记作G=(V,E).其中V(G)是图中顶点的非空有限集合,E(G)是图边的有限集合. 如果图中的边是有方向的,即边是顶点的有序对,则称这样的图为有向图.此时,有向边也称为弧,弧的起点为弧尾,终点为弧头,表示为Vi,Vj.若图中每条边都是没有方向,则为无向图 一. 图的定义 1 2 3 1 2 3 4 J I H G F E A C X B 在一个n个顶点的无向图中,若每个顶点与其他n-1个顶点之间都有边,这样的图称为无向完全图. 在n个顶点的有向图中,若每个顶点与其它的n-1个顶点之间都有弧存在,则称该图为有向完全图 在图中,若Vi,Vj是一条边，则称顶点Vi和顶点Vj是邻接的．并且称该边依附于顶点Vi和顶点Vj上． 度：一个顶点的度是依附于该点的边数． 一. 图的定义 1 2 3 1 2 3 4 J I H G F E A C X B 入度：在有向图中，依附于顶点的弧头数目称为该点的入度． 出度：以某顶点为尾，即依附于该顶点的弧尾数目称为该点的出度． 度：入度与出度之和称之为度． 路径：从顶点Vi到顶点Vj的顶点序列Vi, Vm, …,Vn, Vj,并且＜Ｖs, Vt属于图Ｇ，则该序列称之为一条路径． 路径长：路径上边的数量． 一. 图的定义 1 2 3 1 2 3 4 J I H G F E A C X B 邻接矩阵 6.2 图的存储 C1 C2 C3 C4 C6 C5 C6 C5 C4 C3 C2 C1 邻接表 6.2 图的存储 C1 C2 C3 C4 C6 C5 C1 C2 C3 C4 C5 C6 2 3 4 5 5 6 5 6 ∧ ∧ ∧ ∧ ∧ ∧ 6.3 图的运算:遍历 Algorithm DFS(V) //纵向优先遍历的递归算法,从v点开始 // visit[i]的初值均为0,表示未访问,否则表示已访问 Visit[v] = 1; Write(v); For 每一个点属于v的邻点x do If (visit[x] == 0) DFS(x); 1 2 3 4 5 6 7 8 6.3 图的运算:遍历 Algorithm DFS(V) //纵向优先遍历的非递归算法,从v点开始 // visit[i]的初值均为0,表示未访问,否则表示已访问 入栈,标记表示已访问 循环以下内容 出栈 访问 邻点未标记的进栈,并标记 1 2 3 4 5 6 7 8 6.3 图的运算:遍历 Algorithm BFS(V) //横向优先遍历的非递归算法,从v点开始 // visit[i]的初值均为0,表示未访问,否则表示已访问 入队,置标记 While (队不空) { 出队 访问 未访问的邻接点入队,并置标记 } 1 2 3 4 5 6 7 8 6.4 最小代价生成树 1 定义 2 克鲁斯卡尔方法 3 莱姆方法 1 2 3 4 5 6 6 5 1 3 5 5 6 4 6 2 6.4 最小代价生成树 1 定义(生成树):对于图进行遍历,所有走过的边以及结点构成一棵树,称之为生成树. 1 2 3 4 5 6 1 2 3 4 5 6 广度优先有哪些信誉好的足球投注网站生成树 6.4 最小代价生成树 1 定义(生成树):生成树中代价最小的树称为最小代价生成树. 1 2 3 4 5 6 6 5 1 3 5 5 6 4 6 2 该图的代价为: 6+1+5+5+5+3+6+4+2+6 1 2 3 4 5 6 6 5 1 3 4 该图的代价为: 6+1+5+3+4 6.4 最小代价生成树:原理 从最小的代价以最小成本进行扩充 1 2 3 4 5 6 6 5 1 3 5 5 6 4 6 2 6.4 最小代价生成树:克鲁斯卡尔方法 1将图中的边分为生成树边集E(T)和其他边集E(G),初始状态E(T)为空 2在图中找非E(T)中、未访问过的，而且权重最小的一条边(u,v) 3如果u, v以及边(u,v)加入到生成树T后,构成圈,则舍弃该边,否则,将该边以及点u,v加入T 4 从原图中删除(u,v)边. 5 直到形成树为止 1 2 3 4 5 6 6 5 1 3 5 5 6 4 6 2 6.