84图的遍历 遍历定义:从已给的连通图中某一顶点出发,沿着一些边,访 遍图中所有的顶点,且使每个顶点仅被访问一次,就叫做 图的遍历,它是图的 遍历实质:找每个顶点的邻接点的过程。 图的特点:图中可能存在,且图的任一顶点都可能与其它 顶点相通,在访问完某个顶点之后可能会沿着某些边又回 到了曾经访问过的顶点。 怎样避免重复访问? 解决思路:可设置一个辅助数组 visited n],用来标记每个被 访问过的顶点。它的初始状态为0,在图的遍历过程中 旦某一个顶点被访问,就立即改 visited[为1,防止它 被多次访向问。 深度优先搜索 图常用的遍历: 、广度优先搜索
1 一、深度优先搜索 二、广度优先搜索 8.4 图的遍历 遍历定义：从已给的连通图中某一顶点出发，沿着一些边，访 遍图中所有的顶点，且使每个顶点仅被访问一次，就叫做 图的遍历，它是图的基本运算。 遍历实质：找每个顶点的邻接点的过程。 图的特点：图中可能存在回路，且图的任一顶点都可能与其它 顶点相通，在访问完某个顶点之后可能会沿着某些边又回 到了曾经访问过的顶点。 解决思路：可设置一个辅助数组 visited [n ]，用来标记每个被 访问过的顶点。它的初始状态为0，在图的遍历过程中， 一旦某一个顶点i被访问，就立即改 visited [i]为1，防止它 被多次访问。 图常用的遍历： 怎样避免重复访问？
深度优先搜索(DFS) Depth First Search 基本思想:仿树的先序遍历过程 例1:人 DFS结果 v1→v2→→v4-v8 V5→V3-V6→V7 v0八 记 例2: DFS结果 12→v1→V3→V5 V4→V6
2 一、深度优先搜索( DFS ) 基本思想：——仿树的先序遍历过程。 Depth_First Search v1 v1 v2 v3 v8 v6 v7 v4 v5 例1： DFS 结果 → → → → → → → v2 v4 v8 v5 v3 v6 v7 例2： v2 → v1 → v3 → v5 → DFS 结果 v4 → v6 起点 起点 应退回到V8，因为V2已有标 记
深度优先搜索(遍历)步骤 简单归纳: 访问起始点 若v的第1个邹接点没访问过,深度遍历此邻接点; 若当前邻接点已访问过,再找v的第2个邻接点重新遍历。 详细归纳: 在访问图中某一起始顶点ν后,由ν出发,访问它的任一邻接 顶点w1; 再从w出发,访问与w1邻接但还未被访问过的顶点w 然后再从w2出发,进行类似的访问, 如此进行下去,直至到达所有的邻接顶点都被访问过的顶点u 为止 接着,退回一步,退到前一次刚访问过的顶点,看是否还有其 它未被访问的邻接顶点。 则访问此顶点,之后再从此顶点出发,进行与前述 类似的访问 就再退回一步进行搜索。重复上述过程,直到连 通图中所有顶点都被访问过为止
3 深度优先搜索（遍历）步骤： 详细归纳： 在访问图中某一起始顶点 v 后，由 v 出发，访问它的任一邻接 顶点 w1； 再从 w1 出发，访问与 w1邻接但还未被访问过的顶点 w2； 然后再从 w2 出发，进行类似的访问，… 如此进行下去，直至到达所有的邻接顶点都被访问过的顶点 u 为止。 接着，退回一步，退到前一次刚访问过的顶点，看是否还有其 它未被访问的邻接顶点。 如果有，则访问此顶点，之后再从此顶点出发，进行与前述 类似的访问； 如果没有，就再退回一步进行搜索。重复上述过程，直到连 通图中所有顶点都被访问过为止。 简单归纳： • 访问起始点v; • 若v的第1个邻接点没访问过，深度遍历此邻接点； • 若当前邻接点已访问过，再找v的第2个邻接点重新遍历
二、广度优先搜索(BFS) Breadth First Search 基本思想:仿树的层次遍历过程 例1 BFS结果 v1→v2→V3 V4y56-v7v8 起点 BFS结果 层 V3→V2→V1→V6 V4→V5-9→v8→v7 二层 三层
4 二、广度优先搜索( BFS ) 基本思想：——仿树的层次遍历过程。 Breadth_First Search v1 v1 v2 v3 v8 v6 v7 v4 v5 例1： BFS 结果 → → → v2→v3 v4→v5 v6→v7→v8 例2： v3 → BFS 结果 v4 → v5 → 起点 起点 v2 → v1 → v6 → v9 → v8 → v7
广度优先搜索(遍历)步骤: 简单归纳: 在访问了起始点v之后,依次访问v的邻接点; 然后再依次(顺序)访问这些点(下一层)中未被 访问过的邻接点; 直到所有顶点都被访问过为止
5 广度优先搜索（遍历）步骤： 简单归纳： • 在访问了起始点v之后，依次访问 v的邻接点； • 然后再依次（顺序）访问这些点（下一层）中未被 访问过的邻接点； • 直到所有顶点都被访问过为止。 广度优先搜索是一种分层的搜索过程，每向前走一 步可能访问一批顶点，不像深度优先搜索那样有回 退的情况。 因此，广度优先搜索不是一个递归的过程，其算法 也不是递归的
85最小生成树 最小生成树的基本概念 1、生成树:是一个极小连通子图,它含有图中全部项点,但 只有n-1条边。 2、最小生成树:如果无向连通图是一个带权图,那么它的所 有生成树中必有一棵边的权值总和为最小的生成树, 称这棵生成树为最小代价生成树,简称最小生成树
6 8.5 最小生成树 1、生成树：是一个极小连通子图，它含有图中全部顶点，但 只有n-1条边。 2、最小生成树：如果无向连通图是一个带权图，那么它的所 有生成树中必有一棵边的权值总和为最小的生成树， 称这棵生成树为最小代价生成树，简称最小生成树。 一、最小生成树的基本概念
3求最小生成树 目标:在网络的多个生成树中,寻找一个各边权值之和 最小的生成树。 即有权图 首先明确: 使用不同的遍历图的方法,可以得到不同的生成树;从 不同的顶点出发,也可能得到不同的生成树。 ·按照生成树的定义,n个顶点的连通网络的生成树肯定 有个顶点和仅仅m-1条边。 构造最小生成树的准则 ◆必须只使用该网络中的边来构造最小生成树 ◆必须使用且仅使用m-1条边来联结网络中的m个顶点 ◆不能使用产生回路的边
7 3.求最小生成树 首先明确： • 使用不同的遍历图的方法，可以得到不同的生成树；从 不同的顶点出发，也可能得到不同的生成树。 • 按照生成树的定义，n 个顶点的连通网络的生成树肯定 有 n 个顶点和仅仅n-1 条边。 即有权图 构造最小生成树的准则 ❖ 必须只使用该网络中的边来构造最小生成树； ❖ 必须使用且仅使用n-1条边来联结网络中的n个顶点； ❖ 不能使用产生回路的边。 目标：在网络的多个生成树中，寻找一个各边权值之和 最小的生成树
、典型用途: 欲在n个城市间建立通信网,则n个城市应铺n-1条线路;但因 为每条线路都会有对应的经济成本,而n个城市可能有 n(n-1)/2条线路,那么,如何选择条线路使总费用最少? 先建立数学模型: 顶点 表示城市,有n个; 边—表示线路,有n-1条; 显然此连通网是 边的权值一表示线路的经济代价 生成 连通网表n个规市间的通信网 问题抽象:n个顶点的生成树很多,需要从中选一棵代价最 小的生成树,即该树各边的代价之和最小。此树便称为最小 生成树MST
8 欲在n个城市间建立通信网，则n个城市应铺n-1条线路；但因 为每条线路都会有对应的经济成本，而n个城市可能有 n(n-1)/2 条线路，那么，如何选择n–1条线路使总费用最少？ 4、典型用途： 先建立数学模型： 顶点———表示城市，有n个； 边————表示线路，有n–1条； 边的权值—表示线路的经济代价； 连通网——表示n个城市间的通信网。 显然此连通网是 一棵生成树！ 问题抽象：n个顶点的生成树很多，需要从中选一棵代价最 小的生成树，即该树各边的代价之和最小。此树便称为最小 生成树MST
讨论:如何求得最小生成树? 最小生成树(MST)的性质如下: 若U集是的一个非空子集,若(uv是一条最小权值的 边,其中u∈U,v∈VU;则:(u,vo)必在最小生成树上。 设想一下:先把权值最小的边归入生成 树内,逐个递增,舍去回路边,则得到 的很可能就是最小生成树! 对边操作 求MST有多种算法,但最常用的是以下两种: Kruskal(克鲁斯卡尔)算法 Prim(普里姆)算法 对顶点操作 Kruskal算法特点:将边归并,适于求稀疏网的最小生成树。 Prime算法特点:将顶点归并,与边数无关,适于稠密网
9 讨论：如何求得最小生成树？ 最小生成树（MST）的 性质如下： 若U集是V的一个非空子集，若(u0 , v0 )是一条最小权值的 边，其中u0U，v0V-U；则：(u0 , v0 )必在最小生成树上。 设想一下：先把权值最小的边归入生成 树内，逐个递增，舍去回路边，则得到 的很可能就是最小生成树！ 求MST有多种算法，但最常用的是以下两种： ❖ Kruskal（克鲁斯卡尔）算法 ❖ Prim（普里姆）算法 Kruskal算法特点：将边归并，适于求稀疏网的最小生成树。 Prime算法特点: 将顶点归并，与边数无关，适于稠密网。 对边操作 对顶点操作
、普里姆算法 令集合U的初值为U={uo},集合T=}。从所有结点u∈U和 结点v∈VU的带权边中选出具有最小权值的边(u,v),将结 点v加入集合U中,将边(u,v)加入集合T中。如此不断重复, 当U=V时,最小生成树便构造完毕。 示例:归并顶点 最小代价生成树 Pim算法是归并顶点,适用于稠密网
10 二、普里姆算法 1、普里姆（Prim)算法思想 令集合U的初值为U={u0}，集合T={}。从所有结点u∈U和 结点v∈V\U的带权边中选出具有最小权值的边(u,v)，将结 点v加入集合U中，将边(u,v)加入集合T中。如此不断重复， 当U=V时，最小生成树便构造完毕。 2、普利姆（Prim）算法示例： 归并顶点 1 2 3 4 5 6 6 1 6 5 5 5 6 3 4 2 最小代价生成树 1 2 3 4 5 6 1 5 3 4 2 Prim算法是归并顶点，适用于稠密网