Dijkstra:

Dijkstra求最短路 I

Dijkstra求最短路 II

  • 朴素Dijkstra的算法思想:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

int dijkstra()
{
    memset(dist, 0x3f, sizeof dist); // 初始化，将图中所有的点距离初始为 负无穷，随后在 dijkstra 的算法过程中更新最短距离;
    dist[1] = 0; // 在这里将 标号为 1 的点距离初始为0， 表示 1 号点到 1 号点的距离为 0;
    st[1] = true; // 表示
    for(int i = 0; i < n; i ++)
    {
        int t = -1; // 寻找当前集合中距离最小的点
        /*
        根据 dijkstra 的定义，很容易知道，第一次循环一定会找到 1 号点， 随后根据 1 号点的距离更新其余点的值
        */
        for(int j = 1; j <= n; j ++)
        {
            if( !st[j] && ( t == -1 || dist[t] > dist[j])) // 如果说当前的点 j 尚未被遍历过，并且 
        }
    }
}

BFS:

走迷宫

八数码

  • 广度优先遍历的通用模板:
    1
    2
    3
    4
    5
    6
    7
    8
    while(队列不空)
    {
        auto t = 队头元素
        遍历队头元素所能到达的元素，并加入队列中
        并根据题目维护不同的额外信息
    }

    队列为空时，说明深度遍历已经结束
  • BFS中通常涉及到上下左右方向的枚举，可以直接使用两个数组dx dy来模拟

树和图的DFS:
数的重心

树和图的BFS:
图中点的层次

  1. 树和图的存储方式有邻接表和邻接矩阵两种，稀疏图可以使用邻接表，稠密图则需要使用邻接矩阵存储
  2. 邻接表模板:
    1
    2
    3
    4
    5
    6
    7
    8
    int h[N], e[N], ne[N], idx;
    memset(h, -1, sizeof h);
    void add(int a, int b)
    {   
        e[idx] = b;
        ne[idx] = h[a];
        h[a] = idx ++;
    }
  3. 遍历模板(DFS 与 BFS 类似):
    1
    2
    3
    4
    5
    for(int i = h[u]; i != -1; i = ne[i])
    {
        int j = e[i];
        // 根据DFS BFS的不同，使用不同的具体策略
    }

拓扑排序:
有向图的拓扑序列

  • 在拓扑排序中，需要借助出度、入度的概念维护相应的信息，并借此通过BFS解题。