无向图的算法

无向图是图论中的一类图形，在其图形中，没有任何边的方向性，即每一条边都是既可以由起点延伸到终点，也可以由终点延伸到起点。无向图的算法在图论中有着广泛的应用，并且是求解各种问题的关键之一。本文将从多个角度分析无向图的算法。

1. 基本概念

在无向图中，如果存在一条从点A到点B的边，我们将这条边称为(A,B)或(B,A)，其中A和B是边的两个端点。如果从一个点出发，沿着若干条边可以到达任何一个点，则该图是连通的。如果一个图不是连通的，则可以把它分割成若干个连通子图。而任何一个图都可以被分割成若干棵生成树。

2. 最小生成树

在无向图中，生成树是指一个包含所有节点的无向树，其边权值之和最小。得到最小生成树的算法有Prim算法和Kruskal算法。

（1）Prim算法

Prim算法是通过构造生成树来求解最小生成树的过程。其具体步骤如下：

1）定义一个数组visit[v]用来记录每个节点是否已经被访问过，若已经被访问过，则visit[i]=1，否则visit[i]=0。

2）定义一个数组dist[v]，dist[i]表示当前已经得到的最小生成树中，与节点i距离最小的边的边权值。

3）遍历节点v，初始化visit[v]为0，即未被访问。选择一个起始点s，将visit[s]设为1，dist[s]设为0。

4）将起始点s到所有未访问的节点i之间的边权值存储在数组adj[s][i]中，并将dist[i]赋值为adj[s][i]。遍历剩余的节点，选择dist[i]最小的i，并将visit[i]设为1。然后再通过i节点更新dist数组中的所有节点，得到新的dist。

5）重复第4步，直到visit数组中没有0，也就得到了最小生成树。

（2）Kruskal算法

Kruskal算法是通过找到所有的边来构造生成树的过程，其具体步骤如下：

1）对所有边按照权重排序。

2）从小到大遍历所有的边，如果它连接的两个节点不在同一个连通分量中，那么就把这条边加入生成树中，并将这两个节点合并为一个连通分量。

3）重复步骤2，直到所有的节点都在同一个连通分量中，也就得到了最小生成树。

3. 最短路径

在无向图中，最短路径是指两个节点之间权值之和最小的路径。得到最短路径的算法有Dijkstra算法和Floyd算法。

（1）Dijkstra算法

Dijkstra算法是通过逐个找出节点到源点的最短距离来计算最短路径的过程。其具体步骤如下：

1）定义一个数组visit[v]，表示每个节点是否已经被访问过。一个数组dist[v]，表示从源点到v节点的最短距离，若当前无法从源点到达，则dist[v]=Infinity。

2）从源点s开始，将visit[s]设为1，dist[s]设为0。

3）对于所有未被访问节点i，将源点s到i节点的距离存储在数组adj[s][i]中，也就得到了dist[i]=adj[s][i]。

4）对于所有未被访问的节点，选择dist[i]最小的节点k，并将visit[k]设为1。

5）以k节点为中心，将所有其他节点到源点的距离更新为更短的距离。即dist[v]=min(dist[v],dist[k]+adj[k][v])。

6）重复步骤4和5，直到visit数组中没有0，也就得到了最短路径。

（2）Floyd算法

Floyd算法是一种动态规划算法，可以计算出任意两个节点之间的距离。其具体步骤如下：

1）定义一个数组dist[v][v]，表示从节点i到节点j的最短距离。

2）通过已知边权值构造出邻接矩阵。

3）遍历每一个节点k，以k为中介节点，计算出经过k节点的最短距离。即dist[i][j]=min(dist[i][k]+dist[k][j],dist[i][j])。

4）重复步骤3，直到所有的节点都被当做中介节点，计算出所有节点之间的最短距离。

4.