图的遍历及最小生成树讲义—深度优先与广度优先遍历

图的遍历是指从图的某个顶点出发，访问图中所有顶点，并且每个顶点仅被访问一次的过程。在进行图的遍历时，需要对顶点进行标记，一般用一个辅助数组visit[n]来标记顶点的访问状态。当顶点vi未被访问时，visit[i]值为0；当vi已被访问，则visit[i]值为1。常用的图的遍历方法有两种，即深度优先遍历和广度优先遍历。 首先讲解深度优先遍历。从图中某个顶点v出发，首先访问顶点v，然后依次从v的未被访问的邻接点出发，继续对图进行深度优先遍历。对于给定的图G=(V,E)，首先将V中的每个顶点都标记为未被访问，然后选取一个源点v∈V，将v标记为已被访问，再递归地用深度优先搜索方法，依次搜索v的所有邻接点w。如果w未曾被访问过，则以w为新的出发点继续进行深度优先遍历。如果从v出发的所有路径的顶点都已被访问过，则从v的搜索过程结束。此时，如果图中还有未被访问过的顶点（该图有多个连通分量或强连通分量），则再任选一个未被访问过的顶点进行深度优先遍历。 另一种常用的图的遍历方法是广度优先遍历。广度优先遍历从图中某个顶点v开始，首先访问顶点v，然后依次访问v的所有邻接点，接着再以这些邻接点作为起点，继续访问它们的邻接点，依次展开。在进行广度优先遍历时，一般需要借助一个队列来实现。初始时，将v入队，然后依次出队并访问其邻接点，再将邻接点入队，直到队列为空为止。 除了图的遍历，还有一个重要的概念是图的最小生成树。在图论中，一个连通图的生成树是它的一个极小连通子图，它含有图中全部顶点，并且是一棵树。最小生成树是指具有最小权值的生成树。常用的求解最小生成树的算法有Prim算法和Kruskal算法。 Prim算法是一种贪心算法，它从一个顶点出发，逐步构造最小生成树。具体实现过程是从图中的任意一个顶点开始，然后将该顶点加入到最小生成树中，接着找出与当前最小生成树相邻的边中权值最小的边，将其连接的顶点加入到最小生成树中，重复这个过程直到最小生成树中含有图中所有的顶点。 Kruskal算法是另一种求解最小生成树的常用方法。它是以边为出发点进行算法设计的，具体实现过程是将图中的边按权值从小到大进行排序，然后逐个考察边，若该边连接的两个顶点不在同一个连通分量中，则将该边加入最小生成树中并合并这两个连通分量，直到最小生成树中含有图中所有的顶点。 总之，图的遍历和最小生成树是图论中的两个重要概念和算法。通过深度优先遍历和广度优先遍历，可以实现对图的所有顶点进行遍历访问；而通过Prim算法和Kruskal算法，可以求解出图的最小生成树。这两个概念和算法在实际应用中有着广泛的用途，对于解决许多实际问题有着重要的意义。