数学归纳法在数据结构与算法分析设计中的应用
最简单和常见的数学归纳法是证明当n等于任意一个自然数时某命题成立。证明分下面两步：
- 证明当 n= 1 时命题成立。
- 假设 n=m 时命题成立，那么可以推导出在 n=m+1 时命题也成立。（m代表任意自然数）
1. 图
-
设
G=(V, E)为一个有向图或无向图，假定 BFS 以给定结点 之间的距离）。以数学归纳法的方式进行证明，此外还需理解的细节即是，BFS 的方式需借助先进先出的队列，其最核心的两个操作，enqueue 与 dequeue。我们的归纳假设是：对于所有的结点
enqueue(G, u)，从结点 u 进行邻接表搜索时发现了结点 v（u 可以到 v，根据三角不等式性，，因此：
-
证明：任意连通无向图
- 当只有一个顶点时，，显然成立；
- 因为是连通的，故取出一个顶点（，根据数学归纳法，则有：