1.最小生成树

1.1.最小生成树的概念

1. 边的权值之和最小的生成树，称为最小生成树
2. 最小生成树不唯一
3. 连通图本身就是一棵树，则它就是最小生成树

1. 最小生成树需连通图，非连通图只能是生成森林

1.2.Prim算法

从某一个顶点开始构建最小生成树，依次加入当前剩余顶点中代价最小的顶点，直到加入所有顶点

时间复杂度：O(| |)

适用：稠密图（E大）

每一轮开始都循环遍历所有节点，找到当前代价最低且并没有加入树的结点，再次遍历，更新各个结点的代价

1.3.Kruskal算法（库鲁斯卡尔）

每次选择代价最小的一条边，使该边的两个顶点相通，但是，如果原本就相通的两个顶点的边就不选，直到所有顶点相通

时间复杂度：O( )

适用：稀疏图（E小）

共执行e轮，每轮判断两个结点是否属于同一个结点

2.最短路径

2.1.BFS

BFS能求无权图的单源最短路径：用额外两个数组分别存储该顶点的前驱和距离源顶点的距离

#define MaxVertexNum 100
void BFS(Graph G, int v){
    Queue Q;
    InitQueue(Q);
    EnQueue(v);
    int q, p;
    //dist数组用来存放当前顶点到源顶点的距离，pre存放当前顶点的前驱顶点
    int dist[MaxVertexNum] = { 0 }, pre[MaxVertexNum] = { 0 };
    bool visited[MaxVertexNum] = { false };
    //源顶点的前驱置为-1
    pre[v] = -1;
    //源顶点标记已访问
    visited[v] = true;
    //cur标记当前距离顶点的距离
    int cur = 0;
    while(!IsEmpty(Q)){
        DeQueue(Q, p);
        cur++;
        for (q = FirstNeighbor(G, p); q >= 0; q = NextNeighbor(G, p, q)){
            if (!visited[q]) {
                //将q设置为已标记
                visited[q] = true;
                //入队q
                EnQueue(Q, p);
                //更新q距离源顶点的距离
                dist[q] = cur;
                //更新q的前驱
                pre[q] = p;
            }//if
        }//for
    }//while
}

BFS算法求最短路径的局限：仅能求无权图或者各条边权值都相同的图

2.2.Dijkstra算法

2.2.1.Dijkstra算法的基本概念

在求最短路径（单源）的过程中，需要新建四个数组：path（存储到此点路径的上个结点）、dist（距离源点的最短距离）、顶点集S和final（标记是否已经找到最短路径）

第一轮以0为源点，更新以0为起点到各个顶点的数据，如果当前还没有道路能通往该顶点（2，3），则前驱为-1，且距离为 ∞，并把源点0的final标记为已找到

                                         第一轮

第二轮以当前未找到最短路径且当前路径最低的顶点，即顶点4，将其final改为已找到。以0→4的路径更新各个顶点数据。

第二轮

第三轮以当前未找到最短路径且当前路径最低的顶点，即顶点1，将其final改为已找到。以0→4→3的路径更新各个顶点数据。

第三轮

第四轮以当前未找到最短路径且当前路径最低的顶点，即顶点3，将其final改为已找到。以0→4→3→1的路径更新各个顶点数据。

第四轮

第四轮以当前未找到最短路径且当前路径最低的顶点，即顶点5，将其final改为已找到。

第五轮

2.2.2.Dijkstra的时间复杂度

每轮都需要遍历两边数组（顶点集），第一遍查找当前距离最短且未被标记的顶点，第二遍更新以该顶点为路径的信息，一共要执行n - 1轮，因此，时间复杂度为O()，即O(

)（与Prime算法的思想很类似）

2.2.3.Dijkstra的不适用情况

当图中边的权值存在负值时，Dijkstra算法并不适用

2.3.Floyd算法

2.3.1.Floyd算法的基本概念

Floyd算法用于计算有向图/无向图的任意两个结点的最短路径

Floyd算法需要新建两个二维数组，A（保存当前最短路径长度）和path（最短路径的前驱）

初始化A和path数组，不允许任何中转

A

path

第一轮：允许在V0中转

A

path

第二轮：允许在V0、V1中转，更新V2→V3、V2→V4

A

path

第三轮：允许在V0、V1、V2中转，更新V0→V1、V0→V4、V0→V3

A

path

第四轮：允许在V0、V1、V2、V3中转，更新V0→V4、V1→V4、V2→V4

A

path

第五轮：允许在V0、V1、V2、V3中转

A

path

2.3.2.Floyd算法的复杂度

空间复杂度：创建两个二维数组O(n2)

时间复杂度：三个for循环O(n3)

2.4.最短路径小结

1. 无权图：BFS、Dijkstra算法、Floyd算法
2. 带权图：Dijkstra算法、Floyd算法
3. 带负权值图：Floyd算法
4. 带负权值回路图：无

 5.时间复杂度：

1. BFS：O(|V^2|)（邻接矩阵）或者O(|V|+|E|)（邻接表）
2. Dijkstra：O(|V^|2)
3. Floyd：O(|V|^3)

  6.通常应用场景：

1. BFS：无权图单源最短路径
2. Dijkstra：有权图单源最短路径（也可以求任意两点路径，重复V次，O(|V|^3）
3. Floyd：有权图各个顶点间最短路径