本文作者：yxc

来源: AcWing

原文地址：https://www.acwing.com/blog/content/405/

常用算法模板——搜索与图论

树与图的存储

// (1) 邻接矩阵：
// 存储边 a->b
g [a][b]

// (2) 邻接表：
// 对于每个点k，开一个单链表，存储k所有可以走到的点。h[k]存储这个单链表的头结点
int h[N], e[N], ne[N], idx;

// 添加一条边a->b
void add(int a, int b) {
    e[idx] = b, ne[idx] = h[a], h[a] = idx++;
}

// 初始化
idx = 0;
memset(h, -1, sizeof h);

树与图的遍历

(1) 深度优先遍历

int n, G[1000][1000];
bool vis[1000] = {false};

void dfs(int u) {
    vis[u] = true;  // vis[u] 表示点u已经被遍历过
    // 对 u 的一些操作
    for (int v = 0; v < n; v++) {
        if (vis[v] == false && G[u][v] != INF) dfs(v);
    }
}

(2) 广度优先遍历

int n, G[1000][1000];
bool vis[1000] = {false};

void bfs(int u) {
    queue<int> q;
    q.push(u);      //将初始结点u入队
    vis[u] = true;  // 标记为访问

    while (!q.empty()) {
        int u = q.front();  // 取出队首元素
        q.pop();            // 队首元素出队
        for (int v = 0; v < n; v++) {
            if (vis[v] == false && G[u][v] != INF) {  // 未入队的结点全部入队
                vis[v] = true;      // 标记为访问
                q.push(v);
            }
        }
    }
}

拓扑排序

vector<int> G[1000];  //邻接表
int n, inDegree[1000];

bool toposort() {
    int num = 0;  // 记录加入拓扑序列的顶点数
    queue<int> q;
    for (int i = 0; i < n; i++)
        if (inDegree[i] == 0) q.push(i);  // 将入度为0的顶点入队
    while (!q.empty()) {
        int u = q.front();  // 取出队首元素
        q.pop();            // 队首元素出队
        for (int i = 0; i < G[u].size(); i++) {
            int v = G[u][i];                  // u的后继v
            inDegree[v]--;                    // v的入度减1
            if (inDegree[v] == 0) q.push(v);  // 入度为0则入队
        }
        num++;  // 加入拓扑排序
    }
    return num == n;
}

朴素 dijkstra 算法

时间复杂度 $O(n^2+m)$, n 表示点数，m 表示边数

int n, G[1000][1000];
int d[1000]; // 起点到各点的距离
bool vis[1000] = {false};
const int INF = 0x3fffffff;

void Dijlstra(int s) {  // s为起点
    fill(d, d + 1000, INF);
    d[s] = 0;                      // 起点到自身的距离为0
    for (int i = 0; i < n; i++) {  // 循环n次
        int u = -1;     // 寻找距离最小的点
        for (int j = 0; j < n; j++) {
            if (vis[j] == false && (u == -1 || d[u] > d[j]))
                u = j;
        }
        vis[u] = true;
        for (int v = 0; v < n; v++)
            d[v] = min(d[v], d[u] + G[u][v]);  // 以u为中介点
    }
}

堆优化版 dijkstra

时间复杂度 $O(mlogn)$, n 表示点数，m 表示边数

typedef pair<int, int> PII;
struct Node {
    int v, dis;
};
vector<Node> G[1000];  //邻接表
int n, d[1000];
bool vis[1000] = {false};
const int INF = 0x3fffffff;

void Dijlstra(int s) {  // s为起点
    fill(d, d + 1000, INF);
    d[s] = 0;  // 起点到自身的距离为0
    priority_queue<PII, vector<PII>, greater<PII>> heap;
    heap.push({0, s});  // first存储距离，second存储节点编号

    while (!heap.empty()) {
        auto t = heap.top();  // 取堆顶元素
        heap.pop();
        int pos = t.second, dist = t.first;
        if (vis[pos] == true) continue;
        vis[pos] = true;                           // 标记为访问
        for (int i = 0; i < G[pos].size(); i++) {  // 遍历pos的邻接元素
            int v = G[pos][i].v;                   // 邻接的顶点编号
            if (d[v] > dist + G[pos][i].dis) {
                d[v] = dist + G[pos][i].dis;
                heap.push({d[v], v});  // 入堆
            }
        }
    }
}

Bellman-Ford 算法

时间复杂度 $O(nm)$, n 表示点数，m 表示边数

struct Node {
    int v, dis;
};
vector<Node> G[1000];  //邻接表
int n, d[1000];
const int INF = 0x3fffffff;

bool Bellman(int s) {  // s为起点
    fill(d, d + 1000, INF);
    d[s] = 0;                          // 起点到自身的距离为0
    for (int i = 0; i < n - 1; i++) {  // 执行n-1轮操作
        for (int u = 0; u < n; u++) {  // 每次操作遍历所有边
            for (int j = 0; j < G[u].size(); j++) {
                int v = G[u][j].v;      // 邻接边序号
                int dis = G[u][j].dis;  //邻接边权
                if (d[v] > dis + d[u]) {
                    d[v] = dis + d[u];
                }
            }
        }
    }
    // 判断负环
    for (int u = 0; u < n; u++) {  // 对所有边进行判断
        for (int j = 0; j < G[u].size(); j++) {
            int v = G[u][j].v;      // 邻接边序号
            int dis = G[u][j].dis;  //邻接边权
            if (d[v] > dis + d[u]) {
                return false;
            }
        }
    }
    return true;
}

spfa 算法

时间复杂度 平均情况下 $O(m)$，最坏情况下 $O(nm)$, n 表示点数，m 表示边数

struct Node {
    int v, dis;
};
vector<Node> G[1000];  //邻接表
int n, d[1000];
bool inq[1000] = {false};  // 顶点是否在队列中
const int INF = 0x3fffffff;

void spfa(int s) {  // s为起点
    fill(d, d + 1000, INF);
    queue<int> q;
    q.push(s);
    inq[s] = true;
    d[s] = 0;  // 起点到自身的距离为0

    while (!q.empty()) {
        int u = q.front();  // 取队首元素
        q.pop();            // 出队
        inq[u] = false;     // u不在队列中
        for (int j = 0; j < G[u].size(); j++) {
            int v = G[u][j].v;      // 邻接边序号
            int dis = G[u][j].dis;  //邻接边权
            if (d[v] > dis + d[u]) {
                d[v] = dis + d[u];
                if (!inq[v]) {  // 如果v不在队列中
                    q.push(v);
                    inq[v] = true;
                }
            }
        }
    }
}

spfa 判断图中是否存在负环

struct Node {
    int v, dis;
};
vector<Node> G[1000];             //邻接表
int n, d[1000], num[1000] = {0};  // num记录顶点入队次数
bool inq[1000] = {false};         // 顶点是否在队列中
const int INF = 0x3fffffff;

bool spfa(int s) {  // s为起点
    fill(d, d + 1000, INF);
    queue<int> q;
    q.push(s);
    inq[s] = true;
    num[s]++;
    d[s] = 0;  // 起点到自身的距离为0

    while (!q.empty()) {
        int u = q.front();  // 取队首元素
        q.pop();            // 出队
        inq[u] = false;     // u不在队列中
        for (int j = 0; j < G[u].size(); j++) {
            int v = G[u][j].v;      // 邻接边序号
            int dis = G[u][j].dis;  //邻接边权
            if (d[v] > dis + d[u]) {
                d[v] = dis + d[u];
                if (!inq[v]) {  // 如果v不在队列中
                    q.push(v);
                    inq[v] = true;
                    num[v]++;
                    if (num[v] >= n) return false;
                }
            }
        }
    }
    return true;
}

floyd 算法

时间复杂度是 $O(n^3)$, n 表示点数

// 初始化：
for (int i = 0; i < n; i++)
    for (int j = 0; j < n; j++)
        if (i == j)
            d[i][j] = 0;
        else
            d[i][j] = INF;

// d[a][b]表示a到b的最短距离
void floyd() {
    for (int k = 0; k < n; k++)
        for (int i = 0; i < n; i++)
            for (int j = 0; j < n; j++) {
                d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
            }
}

朴素版 prim 算法

时间复杂度是 $O(n^2+m)$, n 表示点数，m 表示边数

int n, G[1000][1000];
int d[1000];  // 起点到各点的距离
bool vis[1000] = {false};
const int INF = 0x3fffffff;

int prim() {  // 默认0号点为初始点
    fill(d, d + 1000, INF);
    d[0] = 0;                      // 起点到自身的距离为0
    int ans = 0;                   // 最小生成树边权之和
    for (int i = 0; i < n; i++) {  // 循环n次
        int u = -1, MIN = INF;     // 寻找距离最小的点
        for (int j = 0; j < n; j++) {
            if (vis[j] == false && d[j] < MIN) {
                u = j;
                MIN = d[j];
            }
        }
        if (u == -1) return -1;  // 找不到说明其他点与起点不连通
        vis[u] = true;
        ans += d[u];  // 加入距离最小的边
        for (int v = 0; v < n; v++) {
            if (vis[v] == false) {
                d[v] = min(d[v], G[u][v]);  // 以u为中介点
            }
        }
    }
    return ans;
}

Kruskal 算法

时间复杂度是 $O(m \log m)$, n 表示点数，m 表示边数

int n, m;  // n 表示点数，m 表示边数
int father[1000];
const int INF = 0x3fffffff;
struct edge {
    int u, v;  // 边序号
    int cost;  // 边权
} E[1000];
bool cmp(edge a, edge b) { return a.cost < b.cost; }
int findFather(int x) {  // 并查集核心操作
    if (father[x] != x) father[x] = findFather(father[x]);
    return father[x];
}

int Kruskal() {
    int ans = 0, num = 0;                       // ans为边权和，num为生成树边数
    for (int i = 0; i < n; i++) father[i] = i;  // 并查集初始化
    sort(E, E + m, cmp);                        // 按边权从小到大排序
    for (int i = 0; i < m; i++) {               //枚举所有边
        int u = findFather(E[i].u);
        int v = findFather(E[i].v);
        if (u != v) {       //如果不在一个集合
            father[u] = v;  //合并
            ans += E[i].cost;
            num++;
            if (num == n - 1) break;
        }
    }
    if (num != n - 1) return -1;
    return ans;
}

染色法判别二分图

时间复杂度是 $O(n + m)$, n 表示点数，m 表示边数

int n;                  // n表示点数
vector<vector<int>> G;  // 邻接表
int color[n];           // 表示每个点的颜色，-1表示未染色，0表示白色，1表示黑色
bool dfs(int u, int c) {
    // u表示当前节点，c表示当前点的颜色
    color[u] = c;
    // 遍历u的邻接节点
    for (int i = 0; i < G[u].size(); i++) {
        int v = G[u][i];
        // 如果相邻节点未染色
        if (color[v] == -1) {
            // 将相邻的点染成相反的颜色
            if (!dfs(v, !c)) return false;
        } else if (color[v] == c)
            //结点v已经着色，且和结点u颜色冲突
            return false;
    }
    return true;
}
bool check() {
    memset(color, -1, sizeof(color));
    bool flag = true;
    for (int i = 0; i < n; i++)
        // 如果当前节点未染色
        if (color[i] == -1)
            if (!dfs(i, 0)) {
                flag = false;
                break;
            }
    return flag;
}

相关内容

• 常用算法模板——常见算法
• 常用算法模板——数据结构
• 常用算法模板——数学知识
• 常用算法模板——搜索与图论