图论

C++ 算法 图论
数据结构与算法
发布日期:   2023-08-08
更新日期:   2023-09-09
文章字数:   4.5k
阅读时长:   20 分
阅读次数:  

图论算法

拓扑排序

时间复杂度O（n+m）,空间复杂度O（n） n为顶点数，m为边数

用途：

  1. 计算工序最短用时（经典拓扑+dp）

  2. 有向无环图（DAG）判环

  3. 分级（排序、分层）

计算工序（洛谷P1113杂务）:

int n, x, index, ans;
const int maxn = 10005;
vector<int> G[maxn];    //邻接链表存图
int f[maxn], t[maxn];    //记录总时长，单位时长
int indegree[maxn]; //记录入度
void Topo_sort() {
    queue<int> q;
    for (int i = 1; i <= n; ++i) {
        if (!indegree[i]) {  //入度为0，入队
            q.push(i);
            f[i] = t[i];  //初始化时间
        }
    }
    while (!q.empty()) {
        //先计算该点的时间
        int temp = q.front(); q.pop();
        for (int i = 0; i < G[temp].size(); ++i) {
            --indegree[G[temp][i]]; //子节点的入度全部-1
            f[G[temp][i]] = max(f[G[temp][i]], f[temp] + t[G[temp][i]]); //更新子节点的工序用时
            if (!indegree[G[temp][i]]) q.push(G[temp][i]);   //分层
        }
    }
}
int main() {
    cin >> n; //顶点个数
    for (int i = 1; i <= n; ++i) {
        cin >> index; //工程序号
        cin >> t[index];
        while (cin >> x) {
            if (x == 0) break;
            G[x].push_back(index);  //建图
            ++indegree[index];  //入度+1
        }
    }
    Topo_sort();
    //找出最终答案
    for (int i = 1; i <= n; ++i) ans = max(ans, f[i]);
    cout << ans << endl;
    return 0;
}

DAG判环：只需要新建一个cnt变量来记录队列中pop出来的顶点的个数，设总顶点数为N，若cnt==N，则表明无环，若cnt!=N，则表示有环。

拓扑排序的稳定性

拓扑排序时，若每一次入队的顶点数量均为1，则代表拓扑排序的结果只有一个，排序是稳定的；若每一次入队的顶点的数量不为1，则表示同一阶段有多个入度为0的顶点，这几个顶点的顺序是不固定的，故排序是不稳定的。
题目中若对排序有较严格要求，需要特别注意拓扑排序的稳定性。

Bellman-Ford算法

Bellman-Ford算法使用于求解单源最短路，该算法可以允许负权值边的存在。Bellman-Ford算法算法思想为进行n次松弛操作，每一次松弛操作都枚举每一条边，对该边的两端顶点路径长度进行修改。以此求出最短路径。时间复杂度为O（nm），其中n为顶点数，m为边数。

SPFA算法

SPFA（Shortest Path Faster Algorithm）算法，是Bellman-Ford算法的队列优化版，时间复杂度较为玄学，理论上讲SPFA可以对Bellman-Ford进行常数级别的优化，但是在算法竞赛当中可能出现卡SPFA时间复杂度使其时间复杂度退化为O（nm）的情况，对于不存在负权值边的图来讲，Dijkstra算法在优先队列优化过后效果稳定且时间复杂度优秀，优先选用Dijkstra。但是对于存在负权值边的图来讲，Dijkstra算法会失效，所以还得使用SPFA。

算法模板：

const int maxn = 1e5 + 5;
const int INF = 0x3f3f3f3f;
int n, m, s, a, b, w;
struct node {
    node(int v, int w) {
        vertex = v, weight = w;
    }
    int vertex, weight;
};
vector<node> G[maxn];   //邻接链表存图
int dis[maxn];  //记录最终的距离数组
bool mark[maxn];    //记录顶点是否存在于队列之中
void SPFA(int start) {
    //初始化距离为无穷大，原点为0
    for (int i = 1; i <= n; ++i) dis[i] = INF;
    dis[start] = 0;
    queue<int> q;
    q.push(start);
    mark[start] = 1;    //该顶点已经入队
    while (!q.empty()) {
        int v = q.front(); q.pop();
        mark[v] = 0;        //该顶点出队
        for (int w = 0; w < G[v].size(); ++w) {  //松弛
            if (dis[G[v][w].vertex] > dis[v] + G[v][w].weight) {
                dis[G[v][w].vertex] = dis[v] + G[v][w].weight;
                if (!mark[G[v][w].vertex]) {    //可以松弛并且该顶点没有在队列里面
                    mark[G[v][w].vertex] = 1;        //顶点入队并且进行mark的记录
                    q.push(G[v][w].vertex);
                }
            }
        }
    }
}

Dijkstra算法

使用优先队列优化后时间复杂度O（mlogn），空间复杂度O（n） n为顶点数，m为边数，该算法用于求解单源最短路，条件为图中不存在负权值的边。各个点到1的最短路径就是反向建图后1到各个点的最短路径。

算法模板：（洛谷P4779）

int n, m, s, u, v, w;
const int maxn = 100005;
const int INF = 0x3f3f3f3f;
struct node {
    node(int v, int w) {
        vertex = v, weight = w;
    }
    int vertex, weight;
};
struct cmp { //注意优先队列的优先级定义，小根堆要用大于号
    bool operator()(node n1, node n2) {
        if (n1.weight == n2.weight) return n1.vertex > n2.vertex;
        return n1.weight > n2.weight;
    }
};
vector<node> G[maxn];   //邻接链表存图
int dis[maxn];  //记录最终的距离数组
bool mark[maxn];
void Dijkstra(int start) {
    priority_queue<node, vector<node>, cmp> q;   //优先队列的自定义语法
    //初始化距离为无穷大，原点为0
    for (int i = 1; i <= n; ++i) dis[i] = INF;
    dis[start] = 0;
    node N(start, 0);
    q.push(N);
    while (!q.empty()) {
        node M = q.top(); q.pop();
        //特判两种情况
        if (mark[M.vertex]) continue;    //已访问过的节点不需要再访问
        if (dis[M.vertex] == INF) break;   //图不连通
        mark[M.vertex] = 1;   //标记已访问
        int v = M.vertex;
        //松弛
        for (int w = 0; w < G[v].size(); ++w) {
            if (dis[G[v][w].vertex] > dis[v] + G[v][w].weight) {
                dis[G[v][w].vertex] = dis[v] + G[v][w].weight;
                node K(G[v][w].vertex, dis[G[v][w].vertex]);
                q.push(K);
            }
        }
    }
}

Floyd算法

时间复杂度O（n^3），空间复杂度O（n^2）
限制条件
该算法用于求任意两点之间的最短路径，也可以来求解一个点是否能到达另一个点。dis[][]数组用于存图。算法核心在于中转站的选择，意为在前v个中转站被允许参与中转的情况下，任意两点可以到达的最短路径，枚举中转站的时候也可以用来判断该点是否位于最短路径当中。注意先初始化dis[][]为INF。

for (int i = 1; i <= n; ++i) {
    for (int j = 1; j <= n; ++j) {
        cin >> dis[i][j];
        path[i][j] = -1;
    }
}
//Floyd算法求任意两点最短路径长度
for (int v = 1; v <= n; ++v) {
    for (int u = 1; u <= n; ++u) {
        for (int w = 1; w <= n; ++w) {
            if (dis[u][w] > dis[u][v] + dis[v][w]) {
                dis[u][w] = min(dis[u][w], dis[u][v] + dis[v][w]);
                //  path[u][w]=v;   //记录路径
            }
        }
    }
}

求路径
Floyd算法可以多开一个path的二位数组来存放中转站标号，只需要在dp的时候在下面多加一句path[u][w]=v;即可。
在求路径的时候需要用到递归。

void printPath(int u, int v) {
    if (paht[u][v] == -1) {    //u与v之间已经没有任何中转站，二者已经直接相连了
        cout << "<" << u << "," << v << ">" << endl;
    }
    else {
        int mid = path[u][v]; //中转站
        printPath(u, mid);   //左递归打印u到中转站的路径
        printPath(mid, v);   //有递归打印中转站到v的路径
    }
}

Floyd算法的时间复杂度较高，所允许容纳的节点并不多，可以直接使用邻接矩阵存储，当题目顶点数量n<=100时，可以考虑使用Floyd。

Prim算法

堆优化后时间复杂度O（mlogn），空间复杂度O（n），n为顶点数，m为边数 Prim算法在稠密图上的表现情况比Kruskal优。

const int maxn = 5005;
const int INF = 0x3f3f3f3f;
struct node {
    node(int v, int w) {
        vertex = v, weight = w;
    }
    int vertex, weight;
};
struct cmp {
    bool operator()(node n1, node n2) {
        return n1.weight > n2.weight;
    }
};
int n, m, a, b, w, ans;
bool mark[maxn];
int dis[maxn];  //存与顶点相连的边的长度
vector<node> G[maxn];
void Prim(int start) {
    for (int i = 1; i <= n; ++i) dis[i] = INF;
    dis[start] = 0;
    priority_queue<node, vector<node>, cmp> q;
    node N(start, 0);
    q.push(N);
    while (!q.empty()) {
        node M = q.top(); q.pop();
        //特判
        if (mark[M.vertex]) continue;    //已访问过的节点不需要再访问
        if (dis[M.vertex] == INF) break;   //图不连通
        mark[M.vertex] = 1;   //标记已访问
        int v = M.vertex;
        //松弛
        for (int i = 0; i < G[v].size(); ++i) {
            //需要特判是否重复选择
            if (dis[G[v][i].vertex] > G[v][i].weight && !mark[G[v][i].vertex]) {
                dis[G[v][i].vertex] = G[v][i].weight;
                node P(G[v][i].vertex, G[v][i].weight);
                q.push(P);
            }
        }
    }

}

非连通图的特判可以直接在dis数组中查找是否有INF，以此来判断该图是否连通。

Kruskal算法

时间复杂度O（mlogm），空间复杂度O（n），n为顶点数，m为边数 Kruskal在稀疏图上的表现情况比Prim优。

const int maxn = 5005;
const int INF = 0x3f3f3f3f;
struct edge {    //创建边结构体
    edge(int _u, int _v, int _w) {
        u = _u, v = _v, w = _w;
    }
    int u, v, w;
};
bool cmp(edge e1, edge e2) {
    return e1.w < e2.w;
}
int n, m, a, b, w, cnt, ans;
vector<edge> E; //存储图的所有边
int father[maxn];   //并查集
int _find(int s) { //查
    while (father[s] != s) s = father[s];
    return s;
}
void merge(int s1, int s2) {    //并
    int f1 = _find(s1), f2 = _find(s2);
    father[max(f1, f2)] = father[min(f1, f2)];
}
void Kruskal() {
    for (int i = 1; i <= n; ++i) father[i] = i;    //初始化每一条边为自己的父亲
    //按照每一条边的权重排序
    sort(E.begin(), E.end(), cmp);
    for (int i = 0; i < E.size(); ++i) { //枚举每一条边
        int _u = E[i].u, _v = E[i].v, _w = E[i].w;
        if (_find(_u) != _find(_v)) {
            cnt++;    //计数器，如果最终cnt!=n-1则图不连通
            ans += _w;
            merge(_u, _v);
        }
        if (cnt == n - 1) break; //全部的边找到了就截断函数
    }
}

kruskal中，因为边添加的时候是递增的，只要边能连接得上并且find_father可以保证两个点的father一样的话，则证明加入的这条边是最大值。
如果各顶点自己也有权值的话，可以利用for循环给每一个顶点加上一条边<0,i>，权重为顶点i的自身权重。

正难则反，查并集没有删边操作，花最小代价删边等同于花最大代价建边。

Hierholzer算法

又称插入回路法，用于求解欧拉路和欧拉路径。

时间复杂度O（n+m），空间复杂度O（n），n为顶点数，m为边数。

求解欧拉路的时候需要提前判明该图是否存在欧拉路。判定条件如下：

有向图：

  • 欧拉回路：所有顶点出度入度一致。

  • 欧拉路径：恰好有一个点的出度比入度多1（起点），恰好有一个点的入度比出度多1（终点）。

无向图：

  • 欧拉回路：所有顶点的度数为偶数。

  • 欧拉路径：恰好有两个顶点的度数为奇数。

有向图欧拉路

接下来以邻接链表有向图的欧拉路求解算法进行演示（字典序最小的欧拉路）：

const int maxn = 1000005;
int n, m, u, v, start = 1;
bool flag = true; //判定图是否满足要求，默认满足欧拉图要求
int indegree[maxn], outdegree[maxn]; //入度出度
vector<int> G[maxn];    //邻接链表存图
stack<int> ans; //存路径
void judge_path() {
    int cnt1 = 0, cnt2 = 0;  //出度比入度多的顶点个数，入度比出度多的顶点个数
    for (int i = 1; i <= n; ++i) {
        if (indegree[i] == outdegree[i]) continue; //出度入度相等
        if (indegree[i] + 1 == outdegree[i]) {   //起点
            cnt1++;
            start = i;    //记录起点
        }
        else if (indegree[i] == outdegree[i] + 1) cnt2++;    //终点
        else {  //其他条件不满足欧拉图要求
            flag = false;
            break;
        }
    }
    if (!((cnt1 == 1 && cnt2 == 1) || (cnt1 == 0 && cnt2 == 0))) flag = false;   //欧拉路径和欧拉回路情况判定
}
void dfs(int s) {
    for (vector<int>::iterator it = G[s].begin(); it != G[s].end();) {
        int next = *it;   //取点
        it = G[s].erase(it);  //删边
        dfs(next);  //深搜继续
    }
    ans.push(s);    //无法再搜索了，此时记录节点，回溯
}
int main() {
    cin >> n >> m;  //点数和边数
    for (int i = 1; i <= m; ++i) {
        cin >> u >> v;
        G[u].push_back(v);  //建图
        ++outdegree[u]; //记录出度
        ++indegree[v];  //记录入度
    }
    juede_path();   //判定该图是否为欧拉图
    if (!flag) {
        cout << "No" << endl;
    }
    else {
        //排序
        for (int i = 1; i <= n; ++i) {
            sort(G[i].begin(), G[i].end());
        }
        dfs(start);
    }
    //输出
    while (!ans.empty()) {
        int temp = ans.top();
        cout << temp << ' ';
        ans.pop();
    }
    return 0;
}

无向图欧拉路

无向图欧拉路，使用了并查集特判图是否连通。

const int maxn = 10005;
int n, m, a, b, start = 1;
bool flag = true; //默认满足欧拉图要求
int degree[maxn], father[maxn];    //顶点的度，father为并查集，用于判断图是否连通
vector<int> G[maxn];
stack<int> ans;
struct edge {    //边结构体，用于记录无向边的信息
    edge(int _u, int _v) { u = _u, v = _v; }
    bool operator<(edge e1)const {
        if (u == e1.u) return v < e1.v;
        return u < e1.u;
    }
    int u, v;
};
set<edge> E;    //储存边的信息
int _find(int s) {    //查
    while (father[s] != s) s = father[s];
    return s;
}
void _merge(int s1, int s2) {        //并
    int f1 = _find(s1), f2 = _find(s2);
    father[max(f1, f2)] = father[min(f1, f2)];
}
void judge_path() {
    int cnt = 0;
    for (int i = 1; i <= n; ++i) {
        father[i] = i;    //初始化并查集数组
        if (degree[i] & 1) {
            cnt++;  //度数为奇数的点
            start = i;
        }
    }
    for (set<edge>::iterator it = E.begin(); it != E.end(); it++) {    //并
        edge tmp = *it;
        _merge(tmp.u, tmp.v);
    }
    for (int i = 1; i <= n; ++i) {
        int f = _find(i);
        if (f != 1) {    //判断图不连通
            flag = false;
            break;
        }
    }
    if (!(cnt == 0 || cnt == 2)) flag = false;    //度数有除了0和2以外的，不是欧拉图
//    if (cnt == 2 && !(degree[1] & 1)) flag = false;
}
void dfs(int start) {
    for (int i = 0; i < G[start].size(); ++i) {
        edge _find(min(start, G[start][i]), max(start, G[start][i]));
        set<edge>::iterator it = E.find(_find);
        if (it != E.end()) {   //边存在
            E.erase(it);
            dfs(G[start][i]);
        }
    }
    ans.push(start);    //回溯
}
int main() {
    cin >> n >> m;
    for (int i = 0; i < m; ++i) {
        cin >> a >> b;
        G[a].push_back(b);
        G[b].push_back(a);
        E.insert(edge(min(a, b), max(a, b)));    //储存边
        degree[a]++;
        degree[b]++;
    }
    judge_path();
    if (!flag) {    //无法画出欧拉路
        cout << "-1" << '\n';
    }
    else {
        //排序，保证路径的字典序最小
        for (int i = 1; i <= n; ++i) {
            sort(G[i].begin(), G[i].end());
        }
        dfs(start);
        while (!ans.empty()) {
            int temp = ans.top();
            cout << temp << ' ';
            ans.pop();
        }
    }
    return 0;
}

Tarjan算法

强连通分量（Strongly Connected Components）

若有向图中有两个点 i 与 j 可以相互到达，则称这两个点强连通，如果图中任意两个点都强连通，则该图称为强连通图。任意一个点自己和自己是强连通的。

非强连通有向图的极大强连通子图称为该图的强连通分量。

根据定义，两个点一定是强连通的，当且仅当它们在同一个环内。环上所有的点都互相强连通。

Tarjan算法求强连通分量

讲解视频（传送门）

算法思路

该算法有两个数组比较重要，第一个是时间戳数组dfn[]，该数组是用来记录对应节点第一次被访问的顺序。另一个是追溯值数组low[]，该数组表示了从对应节点出发，所能够访问到的最早时间戳，以便方便我们进行强连通分量的判断。

算法分三步：

  1. 入：指从 x 节点发起Tarjan算法时，记录 x 对应的时间戳，并将 x 入栈。

  2. 回：我们对 x 发起Tarjan算法，对 x 的子节点 y 进行遍历，分以下三种情况：

    • 如果 y 还未被访问，则继续对 y 进行深搜。回溯到 x 的时候，我们需要利用 y 的low值来更新 x 的low值。

    • 如果 y 已经被访问并且 y 在栈中，说明了 y 是 x 的祖先节点或者左子树节点，这个时候我们直接利用 y 的dfn值来更新 x 的low值。

    • 如果 y 已经访问并且不在栈中，表示 y 已经是属于另一个强连通分量，不需要对其进行其他处理了。

  3. 离：在处理完 x 之后，判断 x 是否为一个强连通分量的入口，如果是，则出栈，并且记录相对应的强连通分量。

根据算法过程容易注意到，因为回溯，所以越往后搜索到的点强连通分量编号越靠前。

代码

洛谷P2863

#include<iostream>
#include<vector>
using namespace std;
const int maxn = 1e4 + 5;
int n, m, a, b, ans;
vector<int> G[maxn];	//邻接链表存图
bool instk[maxn];		//判断元素是否在栈中
int stk[maxn], top;	//stk为手写栈，top为栈顶指针
int dfn[maxn], low[maxn], tot;	//时间戳，low值，对应的标记
int scc[maxn], siz[maxn], cnt;	//对应的节点属于哪一个强连通分量，对应的强连通分量的大小，强连通分量的编号
void Tarjan(int x) {
	//入
	dfn[x] = low[x] = ++tot;	//初始化时间戳和追溯值
	stk[++top] = x, instk[x] = 1;	//元素入栈
	//回
	for (int i = 0; i < G[x].size(); ++i) {
		int y = G[x][i];
		if (!dfn[y]) {	//子节点没被访问，访问子节点
			Tarjan(y);	
			low[x] = min(low[x], low[y]);	//利用子节点的追溯值来更新自己的追溯值
		}
		else if (instk[y]) {	//子节点已经在栈中
			low[x] = min(low[x], dfn[y]);	//子节点的时间戳来更新自己的追溯值
		}
	}
	//离
	if (dfn[x] == low[x]) {	//如果该节点是某一个SCC的入口，则对这个SCC进行处理
		int tmp; ++cnt;
		do {
			tmp = stk[top--]; instk[tmp] = 0;	//取栈顶元素，出栈
			scc[tmp] = cnt;	//该顶点属于第cnt个SCC
			++siz[cnt];	//第cnt个SCC的大小加1
		} while (tmp != x);
	}
}
int main() {
	cin >> n >> m;
	for (int i = 1; i <= m; ++i) {
		cin >> a >> b;
		G[a].push_back(b);
	}
	for (int i = 1; i <= n; ++i) {
		if (!dfn[i]) Tarjan(i);	//如果这个顶点没被访问过，就从它开始发起Tarjan算法
	}
	for (int i = 1; i <= cnt; ++i) {
		if (siz[i] > 1) ++ans;
	}
	cout << ans;
	return 0;
}

Tarjan算法缩点

Tarjan算法的缩点一般是在利用Tarjan算法求出SCC之后进行的操作，通常是对一个节点 i 访问它的子节点 j ，而后判断两个节点是否属于同一个SCC，如果不属于同一个SCC，则记录相应的入度出度，或者直接建新图。

//缩点处理出度入度
for (int i = 1; i <= n; ++i) {
	for (int j = 0; j < G[i].size(); ++j) {
		if (scc[i] != scc[G[i][j]]) {
			din[scc[G[i][j]]]++;	//入度++
			dout[scc[i]]++;		//出度++
		}
	}
}
//缩点建新图
for (int i = 1; i <= n; ++i) {
	for (int j = 0; j < G[i].size(); ++j) {
		if (scc[i] != scc[G[i][j]])
			new_G[scc[i]].push_back(scc[G[i][j]]);	//建新图
	}
}
文章作者: 热心市民灰灰
文章链接: http://example.com/2023/08/08/tu-lun/
版权声明: 本博客所有文章除特別声明外，均采用 CC BY 4.0 许可协议。转载请注明来源 热心市民灰灰 !
C++ 算法 图论
  目录