深度优先搜索算法：从顶点vi出发探索无向图

在本篇关于图及其算法的教程中，我们主要探讨了图的基本概念、不同类型以及相关的术语。首先，图是一种数学结构，由两个集合构成：顶点集V(G)和边集E(G)。对于有向图，边是有序对<v,w>，表示从顶点v到顶点w的方向性连接；而对于无向图，边是无序对(v,w)，表示两个顶点之间的双向联系。 有向完全图和无向完全图是特定类型的图，前者有n(n-1)条边，所有顶点间都有方向明确的连接，后者有n(n-1)/2条边，所有顶点间通过无向边相连。"权"这个概念指的是与图中边或弧相关的数值，赋予了图以权重，使得图成为网络，如加权图。 子图的概念强调了新图G'与原图G的关系，当G'的顶点和边都包含在G中时，G'被视为G的子图。邻接点和依附概念涉及顶点间的直接连接，无向图中，若(v, v')在边集中，则称它们为邻接点，而边本身被认为是依附于这两个顶点的。在有向图中，除了考虑普通度数外，还需区分入度（指指向该顶点的边数）和出度（指从该顶点出发的边数）。 顶点的度数在图论中非常重要，它是衡量一个顶点连接性的指标。在无向图中，度数即为与该顶点相连的边的数量，而在有向图中，度数包括入度和出度。图中的路径是一系列相连的顶点，路径长度则是沿着路径的边数或边的权重总和。回路或环指的是起点和终点重合的路径，它在图的连通性和循环性质中扮演关键角色。 深度优先搜索(DFS)算法在这里是一个关键部分，函数DFSm从给定顶点vi开始，标记其为已访问，然后递归地访问其未访问的邻接点。通过这种方式，我们可以遍历整个图，并且深度优先搜索常用于寻找最短路径、连通分量等问题的解决。 这篇文档深入浅出地介绍了图的理论基础和一种重要的图遍历方法，这对于理解和应用图算法，特别是在计算机科学、网络设计和机器学习等领域，都是十分重要的基础知识。