图论相关算法

图的存储

struct Edge
{
    int to, w;
};

邻接表

vector<Edge> edges[MAXN];
inline void add(int from, int to, int w)
{
    Edge e = {to, w};
    edges[from].push_back(e);
}
// 无向图调用两次add即可
// vector的size方法可以返回其包含的元素个数 用于遍历
for (int i = 0; i < edges[2].size(); i++);
//或者range-base for
for (auto &&e: edges[2])

链式前向星

struct Edge
{
    int to, w, next;
};
int head[MAXN], cnt;
inline void add(int from, int to, int w)
{
    edges[++cnt].w = w; // 新增一条边为cnt + 1的边 边权w
    edges[cnt].to = to; // 该边的终点为to
    edges[cnt].next = head[from]; // 把下一条边 设置为当前起点的第一条边
    head[from] = cnt;
    // 最后两步相当于一个头插 会把新元素插到最前面而不是最后面 
}

// 遍历结束的标志为 edges[i].next = 0 

for (int e = head[2]; e != 0; e = edges[e].next);

感谢金牌✌[pecco的学习笔记](算法学习笔记（目录） - 知乎 (zhihu.com))

最短路

Dijkstra

单源点最短路，不可判负权和环

朴素算法

n, m, s = map(int,input().split())
head = [0] * (n + 1)
cnt = 0
INF = 2 ** 31 - 1
ans = [INF] * (n + 1)
vis = [False] * (n + 1)
edge = {}

for i in range(1, n + 1):
	edge[i] = INF

# 初始化到s点的距离为0
ans[s] = 0

for i in range(1, m + 1):
	a, b, c = map(int, input().split())
    # 重边取最小
    if a in edge:
		edge[a][b] = min(edge[a].get(b, INF), c)
    else:
        edge[a] = {b:c}
pos = s

# pos 未遍历时
while not vis[pos]:
    minn = INF
    # 标记
    vis[pos] = True
    # pos 顶点在边上时
    if pos in edge:
        # 取pos顶点指向的顶点（设为终点（有向图））和权值
        for to, wei in edge[pos].items():
			# 如果终点未访问并且终点的值大于pos+wei 那就更新终点值的最短路
            if not vis[to] and ans[to] > ans[pos] + wei:
                ans[to] = ans[pos] + wei
        # 遍历所有未遍历的点  如果小于minn 就更新minn（最短路） 并且让pos = i（最短子路）
        for i in range(1, n + 1):
			if not vis[i] and ans[i] < minn:
                minn = ans[i]
for i in range(1, n + 1):
    print(ans[i],end=' ')

堆优化

import heapq

n, m, s = map(int, input().split())
# 邻接矩阵
graph = [[] for _ in range(n + 1)]
for _ in range(m):
	u, v, w = map(int, input().split())
    graph[u].append((v,w))
INF = 2 ** 31 - 1
# 距离 初始化为无穷  源点初始化为0
dist = [INF] * (n + 1)
dist[s] = 0
# 先放入源点 第一个参数d表示源点s到当前结点的最短路   第二个参数node表示当前节点编号
q = [(0,s)]
# 队列不空的时候
while q:
	# 取出源点和起点
    d, node = heapq.heappop(q)
    # 当当前最短路小于源点到node的距离时 跳过
    if d > dist[node]:
		continue
    # 从图中取出node结点的终点和权值
    for neighbor, wei in graph[node]:
		if dist[node] + wei < dist[neighbor]:
			dist[neighbor] = dist[node] + wei
             heapq.heappush(q,(dist[neighbor],neighbor))
                
for i in range(1, n + 1):
	print(dist[i],end=' ')

C++版

struct Polar
{
    int dist, id;
    Polar(int dist, int id) : dist(dist), id(id){}
};

struct cmp
{
    bool operator ()(Polar a, Polar b)
    {
        return a.dist > b.dist; //这里是大于 使得距离短的先出队
    }
};
priority_queue<Polar, vector<Polar>, cmp> q;

void Dijkstra(int s)
{
    dist[s] = 0;
    q.push(Polar(0, s));
    while (!q.empty())
    {
        int p = q.top().id;
        q.pop();
        if (vis[p])
            continue;
        vis[p] = 1;
        for (int e = head[p]; e != 0; e = edge[e].next)
        {
            int to = edges[e].to;
            dist[to] = min(dist[to], dist[p] + edges[e].w);
            if (!vis[to])
                q.push(Polar(dist[to], to));
        }
    }
}

链式前向星存图

import heapq
n, m, s = map(int, input().split())

head = [0] * (n + 1)
edge = []

for _ in range(m):
    u, v, w = map(int, input().split())
    # 判重
    exist = False
    i = head[u]
    while i:
        if edge[i][0] == v:
            exist = True
            edge[i] = (v, min(edge[i][1],w), edge[i][2])
            break
        i = edge[i][2]
    if not exist:
        edge.append((v,w,head[u]))
        head[u] = len(edge) - 1

INF = 2 ** 31 - 1
dist = [INF] * (n + 1)
dist[s] = 0

priority_queue = [(0,s)]

while priority_queue:
    d,node = heapq.heappop(priority_queue)
    if d > dist[node]:
        continue
    i = head[node]
    while i:
        neighbor, weight, nextt = edge[i]
        if dist[node] + weight < dist[neighbor]:
            dist[neighbor] = dist[node] + weight
            heapq.heappush(priority_queue, (dist[neighbor],neighbor))
        i = nextt

for i in range(1, n + 1):
    print(dist[i],end=' ')

Bellman-ford

一般用链式前向星或者 邻接表存图 用结构体存结点

首先除起点外所有顶点到起点的距离dis数组初始化为无穷大

遍历每条边 对每条边的两个顶点进行松弛操作 直到不能再松弛

判断负环 如果迭代超过n - 1次还能继续松弛则说明存在负环

每次迭代k如果进行了松弛操作 则一定是经历了k条边的最短路

一共是n个顶点 如果不存在负环 某点到另一个点最多只有n - 1条边

如果迭代k后没有点进行松弛操作 则代表已经找出了所有的最短路 迭代结束跳出循环

struct edge
{
    int v, w;
};
vector<vector<edge>>e(MAXN);
int dis[MAXN];
const int inf = 0x3f3f3f3f;

bool bellman(int n, int s)
{
    memset(dis, 0x3f, sizeof(dist));
    dis[s] = 0;
    bool flag = false;
    
    for (int i = 1; i <= n; i++)
    {
        flag = false;
        for (int u = 1; u <= n; u++)
        {
            if (dis[u] == inf)
                continue;
            for (auto &x : e[u])
            {
                int v = x.v, w = x.w;
                if (dis[v] > dis[u] + w)
                {
                    dis[v] = dis[u] + w;
                    flag = true;
                }
            }
        }
        if (!flag)
            break;
    }
    return flag;
}

spfa

单源点最短路，可判负权和环

“只更新可能更新的点”：

只让当前点能到达的点入队

如果一个点已经在队列中 不重复入队

如果u一条边未更新 那么他的终点不入队

from collections import deque

class edge:
    def __init__(self, v, w):
        self.v = v
        self.w = w
n, m, s = map(int,input().split())

graph = [None] * (n + 1)

for _ in range(m):
	u, v, w = map(int,input().split())
    if graph[u] is None or graph[u].w > w:
		graph[u] = []
    graph[u].append(edge(v,w))
INF = 2 ** 31 - 1
dist = [INF] * (n + 1)
dist[s] = 0

q = deque([s])

# 标记是否在队列中  以及计数 用来判断环
in_queue = [False] * (n + 1)
in_queue[s] = True
enqueue_count = [0]  * (n + 1)
enqueue_count[s] = 1

while q:
    # 取出当前点 
    node = q.popleft()
    in_queue[node] = False
    # 取当前点相连的所有边
    for ed in graph[node]:
        # 取出终点和权值
        v, w = ed.v, ed.w
    	if dist[v] >  dist[node] + w:
            dist[v] = dist[node] + w
            if not in_queue[v]:
                q.append(v)
                in_queue[v] = True
                enqueue_count[v] += 1
                
                if enqueue_count[v] > n:
                    exit(0)
                    

C++版

void SPFA(int s)
{
    queue<int>q;
    q.push(s);
    while (!q.empty())
    {
        int p = q.front();
        q.pop();
        inqueue[p] = 0;
        for (int e = head[p]; e != 0; e = edges[e].next)
        {
            int to = edges[e].to;
            if (dist[to] > dist[p] + edges[e].w)
            {
                pre[to] = p; // 存储路径 
                dist[to] = dist[p] + edges[e].w;
                if (!inqueue[to])
                {
                    inqueue[to] = 1;
                    q.push(to);
                }
            }
        }
    }
}

Floyd

多源最短路

看是否可以是否可以通过k 来更新i到j的最短路 所以k在最外层

INF = 0x3f3f3f3f
n, m = map(int, input().split())

d = [[INF] * (n + 1) for _ in range(n + 1)]

for i in range(1, n + 1):
	d[i][i] = 0
    
for i in range(m):
    a, b, w = map(int, input().split())
    d[a][b] = min(d[a][b], w)
    # 同时要更新另一条边
    d[b][a] = min(d[b][a], w)
    
for k in range(1, n + 1):
    for i in range(1, n + 1):
		for j in range(1, n + 1):
			d[i][j] = min(d[i][j],d[i][k] + d[k][j])
            
for i in range(1, n + 1):
    for j in range(1, n + 1):
        print(d[i][j], end=' ')
    print()

拓扑排序

Kahn

# Kahn算法
from collection import deque
N = 100000
e = [[0] * N for _ in range(N)]
tp = []
din = [0] * N

# 每次从队列取出 让他所有出边减一 当某点入度为0时加入队列  如果最后队列长n则有拓扑序 否则有环
def toposort(n):
	queue = deque()
    for i in range(1, n + 1):
        if din[i] == 0:
			queue.append(i)
    while queue:
        x = queue.popleft()
        tp.append(x)
        for y in e[x]:
            din[y] -= 1
            if din[y] == 0:
				queue.append(y)
return len(tp) == n

n, m = map(int, input().split())
for i in range(m):
    a, b = map(int,input().split())
    e[a].append(b)
    din[b] += 1

if not toposort(n):
    print(-1)
else:
    for x in tp:
		print(x,end=' ')

DFS

N = 100000
e = [[0] * N for _ in range(N)]
tp = [0] * N
c = [0] * N

def dfs(x):
    global tp
    c[x] = -1
    for y in e[x]:
        if c[y] < 0:
            return 0
        elif not c[y]:
            if not dfs(y):
                return 0
    c[x] = 1
    tp.append(x)
    return 1


def toposort():
    global c, tp
    c = [0] * N
    for i in range(1, n + 1):
        if not c[i]:
            if not dfs(i):
                return 0
    tp.reverse()
    return 1

关键路径

# 输入为字典
activities = {}
n = int(input())
for i in range(n):
    name, duration, dependencies = map(int,input().split())
    activities[name] = {'duration':duration, 'dependencies':dependencies}

def cal_early_late_times(activities):
    # 初始化每个工作的最早开始时间和最晚开始时间
    for activity in activities:
        activities[activity]['ES'] = 0
        activities[activity]['LS'] = float('inf')

    # 计算最早开始时间
    # 遍历所有工作 如果依赖于前一项工作 就为前面所有工作的最早开始时间加上持续时间的最大值 如果没有依赖于其他工作则为0
    for activity in activities:
        dependencies = activities[activity]['dependencies']
        if not dependencies:
            activities[activity]['ES'] = 0
        else:
            max_dependency_end = max([activities[dep]['ES'] + activities[dep]['duration'] for dep in dependencies])
            activities[activity]['ES'] = max_dependency_end

    # 计算最后完成的工作的最晚开始时间 为所有工作的最晚的（最早开始时间+持续时间）
    end_activity = max(activities,key=lambda activity: activities[activity]['ES'] + activities[activity]['duration'])
    activities[end_activity]['LS'] = activities[end_activity]['ES'] + activities[end_activity]['duration']
    # 反向计算最晚开始时间
    # 如果不依赖于其他工作 最晚开始时间为最后工作的最晚开始时间-持续时间  否则为最早的最晚开始时间
    for activity in reversed(list(activities.key())):
        dependencies = activities[activity]['dependencies']
        if not dependencies:
            activities[activity]['LS'] = activities[end_activity]['LS'] - activities[activity]['duration']
        else:
            min_dependency_start = min([activities[dep]['LS'] for dep in dependencies])
            activities[activity]['LS'] = min_dependency_start


# 最早开始时间=最晚开始时间即为关键路径
def cal_critical_path(activities):
    critical_path = []
    for activity in activities:
        if activities[activity]['ES'] == activities[activity]['LS']:
            critical_path.append(activity)
    return critical_path

Tarjan

例题

class Solution:
    def criticalConnections(self, n: int, connections: List[List[int]]) -> List[List[int]]:
        graph = defaultdict(list)
        for con in connections:
            graph[con[0]].append(con[1])
            graph[con[1]].append(con[0])

        
        idx = [-1] * n
        res = []

        def dfs(curnode, curid, parent):
            idx[curnode] = curid

            for nextnode in graph[curnode]:
                if nextnode == parent:
                    continue
                elif idx[nextnode] == -1:
                    idx[curnode] = min(dfs(nextnode,curid + 1, curnode),idx[curnode])
                else:
                    idx[curnode] = min(idx[curnode],idx[nextnode])

            # 说明存在环
            if idx[curnode] == curid and curnode != 0:
                res.append((parent, curnode))
            # 记得返回idx
            return idx[curnode]
        

        dfs(0,0,-1)
        return res

最小生成树

Prim

朴素算法

const int N = 100010;
const int inf = 0x3fffffff;
struct edge
{
    int v, w;
};
vector<edge>e;
int ans = 0, cnt = 0;
int d[N];
bool vis[N];
bool prim(int s)
{
    for (int i = 0; i <= n; i++)
    	d[i] = inf;
    d[s] = 0;
    for (int i = 1; i <= n; i++)
    {
        int u = 0;
        for (int j = 1; j <= n; j++)
            if(!vis[j] && d[j] < d[u])u = j;
        vis[u] = true;
        ans += d[u];
        // 非连通图到u距离还是无穷  判断是否连通
        if (d[u] != inf) cnt ++;
        for (auto ed: e[u])
        {
            int v = ed.v, w = ed.w;
            if (d[v] > w)d[v] = w;
		}
    }
    return cnt == n;
}

堆优化

#include <queue>
/*
堆的第一个元素是他的边权 仅仅用来排序 没有其他任何作用 因为在使用到边权的时候 会使用d[u] 而不会使用q.top().first
所以直接建大根堆 放负边权即可
*/
priority_queue<pair<int, int>>q;
bool prim(int s)
{
    for (int i = 0; i <= n; i++)d[i] = inf;
   	d[s] = 0;
    q.push({0, s});
    while (!q.size())
    {
        int u = q.top().second;
        q.pop();
        if (vis[u])continue;// 先取出的必小 后取出的大 直接不看了
        vis[u] = 1;
        ans += d[u];
        cnt ++;
        for (auto ed: e[u])
        {
            int v = ed.v, w = ed.w;
            if (d[v] > w)
            {
                d[v] = w;
                q.push({-d[v], v});
            }
        }
    }
    return cnt == n;
}

Kruskal

int ans = 0, cnt = 0;
int n, m;
const int N = 100010;
struct edge
{
    int u, v, w;
    bool operator < (const edge& t)const 
    {
        return w < t.w;
    }
}e[N];
int fa[N];
int find(int x)
{
	if (x == fa[x])
        return x;
    return fa[x] = find(fa[x]);
}
bool kruskal()
{
    sort(e, e + m);
    for (int i = 0; i <= n; i++)p[i] = i;
    for (int i = 0; i < n; i++)
    {
        int x = find(e[i].v);
        int y = find(e[i].u);
        if(x != y)
        {
            fa[x] = y;
            ans += e[i].w;
            cnt++;
        }
    }
    return cnt == n - 1;
}