Noob
0%

图基础算法总结

发表于 更新于 分类于 ，

数据结构

对于点稠密的图，可以使用邻接矩阵表示g[n][n]，其中n表示图中的节点数，g[i][j]表示是否存在从i到j的路径（无权图）或者从节点i到节点j的权重（有权图）。

对于边稠密的图，如果是无权图可以使用邻接表List<Integer>[] g表示，其中g[i]表示与节点i邻接的点；如果是有权图，可以使用邻接表’List<Integer, Map<Integer, Integer>> g`或者

1
2
3
4
5
class Edge {
    int to;
    int cost;
}
List<Integer, Edge> g;

两种表示图的数据结构方法的算法分析如下：

ADT 空间复杂度 检查w是否与v邻接 遍历所有与v邻接的点
邻接矩阵 V * V 1 V
连接表 E + V degree(v) degree(v)

搜索

深度优先搜索（DFS）

使用一个标记数组标记已被访问过的节点，每次递归标记当前节点并访问与当前节点邻接的节点。可使用并查集记录dfs过程中节点的前驱节点，需要求源点到某节点路径时，从并查集中恢复即可。

1
2
3
4
5
6
7
void dfs(List<Integer>[] g, boolean[] marked, int cur) {
    marked[cur] = true;
    for(int i : g[cur]) {
        if(!marked[i])
            dfs(g, marked, i);
    }
}

广度优先搜索（BFS）

使用一个队列保存与当前节点距离为1的未访问节点，直到队列为空，BFS可用于无权图中需找最短路径。与DFS类似，BFS也可以通过维护一个并查集记录BFS搜索过程中某节点的前驱节点，需要查找路径时，从并查集中恢复即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
void bfs(List<Integer>[] g, int s) {
    boolean[] marked = new boolean[g.size()];
    Deque<Integer> que = new ArrayDeque<Integer>();
    int[] edgeTo = new int[g.size()];
    
    marked[s] = true;
    que.add(s);
    while(!que.empty()) {
        int cur = que.remove();
        for(int i : g[i]) {
            if(!marked[i]) {
                marked[i] = true;
                edgeTo[i] = cur;
                que.add(i);
            }
        }
    }
}

单源最短路径

单源最短路径是固定一个起点，求它到其它所有点的最短路问题。终点固定的问题叫做两点之间的最短路问题。两点之间的最短路问题复杂度和单源最短路径问题相同，通常当做单源最短路径来求解。

Bellman-Ford算法

维护一个距离数组，初始源点到源点的距离为0其它距离都是无穷大。然后使用递推关系式d[i] = min(d[j] + (j到i的距离))不断松弛距离值。松弛V - 1次（V表示图中顶点个数）即可求出源点s到所有顶点的最短距离值。如果循环次数超过V - 1次后仍然有值更新，则说明图中存在负圈。Bellman-Ford算法时间复杂度O（VE）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Edge {
    int from, cost, to;
}
Edge edge[E];
int dis[V];

boolean shortest_path(int s) {
    for(int i : dis) i = Integer.MAX_VALUE;
    dis[s] = 0;
    for(int i = 0; i < V; ++i) {
        for(int j = 0; j < E; ++j) {
            Edge e = edge[j];
            if(dis[e.from] != Integer.MAX_VALUE && 
                dis[e.to] < dis[e.from] + e.cost) {
                    dis[e.to] = dis[e.from] + e.cost;
                    //第V次仍然更新了，说明存在负圈
                    if(i == V - 1) return true;
                }
        }
    }
}

Dijkstra算法

Bellman-Ford算法中，每次循环都考察每条边的松弛情况，Dijkstra算法对这种情况进行了改进：每次确定一个最短距离的点，从这些点出发更新相邻顶点的最短距离。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
int dis[V];;
boolean marked[V];
Edge[V] g;

void dijkstra(int s) {
    for(int i : dis) i = Integer.MAX_VALUE;
    dis[s] = 0;
    
    while(true) {
        int v = -1;
        for(int i = 0; i < V; ++i)
            if(!marked[i] && (v == -1 || dis[v] > dis[i]))
                v = i;
        if(v == -1) break;
        marked[v] = true;
        for(Edge e : g[v])
            dis[e.to] = Math.min(dis[e.to], dis[v] + e.cost);
    }
}

以上算法时间复杂度为O（V * V + E），可以使用一个优先队列加速最小距离顶点的查找，使得时间复杂度降低到O（VlogV + E）。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Node implements Comparable{
    int v, dis;
    public Node(int v, int dis) {
        this.v = v;
        this.dis = dis;
    }
    
    public int compareTo(Node other) {
        reutrn this.dis - other.dis;
    }
}

void dijkstra(int s) {
    for(int i : dis) i = Integer.MAX_VALUE;
    dis[s] = 0;
    
    Deque<Node> que = new PriorityQueue<Node>();
    que.add(new Node(s, 0));
    
    while(!que.empty()) {
        Node node = que.remove();
        if(node.dis < dis[node.v]) continue;
        int v = node.v;
        for(Edge e : g[v])
            que.add(new Node(e.to, e.cost));
    }
}

Floyd-Warshall算法

Floyd-Warshall算法可以用于求解任意两点间的最短路问题，时间复杂度为O（VVV）。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
int dis[V][V];
void warshall_floyd() {
    for(int i = 0; i < V; ++i) {
        for(int j = 0; j < V; ++j) {
            if(i == j) dis[i][j] = 0;
            else if(g[i][j] != Integer.MAX_VALUE)
                dis[i][j] = g[i][j];
            else dis[i][j] = Integer.MAX_VALUE;
        }
    }
    for(int k = 0; k < V; ++k) {
        for(int i = 0; i < V; ++i) {
            for(int j = 0; j < V; ++j) {
                dis[i][j] = Math.min(dis[i][j], dis[i][k] + dis[k][j]);
            }
        }
    }
}

最小生成树

给定一个无向图，如果它的某个子图中任意两个顶点都相互连通并且是一棵树，那么这棵树就叫做生成树（Spanning Tree）。如果边上有权值，那么使得边权和最小的生成树叫做最小生成树（MST，Minimum Spanning Tree）。

Prim算法

Prim算法和Dijkstra算法非常相似，都是从某个顶点出发，不断添加边的算法。初始时生成树是一个只有一个顶点的树，然后贪心地选取与T相连的最小权值的边，并把它加到树中。不断执行这个过程，直到所有顶点都被添加到树中即可。Prim算法与Dijkstra算法时间复杂度一样，为O（V * V + E），可以使用一个优先队列加速最小距离顶点的查找，使得时间复杂度降低到O（VlogV + E）。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
int dis[V];
boolean marked[V];

int prim() {
    dis[0] = 0;
    int result = 0;
    while(true) {
        int v = -1;
        for(int i = 0; i < V; ++i) {
            if(!marked[i] && (v == -1 || dis[v] < dis[i])
                v = i;
        }
        if(v == -1) break;
        marked[v] = true;
        result += dis[v];
        
        for(int i = 0; i < V; ++i) 
            dis[i] = Math.min(dis[i], g[v][i]);
    }
}

Kruskal算法

Kruskal算法按照边的权值从小到大的顺序排序，然后依次选择边，如果加入新边后生成树不形成环，则加入生成树。可以使用并查集高效判断加入某边后是否会形成环。对于边<u, v>，如果加入边之前u，v不在同一个连通分量中，那么加入边后也不会产生环。反之，如果u和v在同一个连通分量中，那么一定会产生环。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
Edge edges[V];

int kruskal() {
    Arrays.sort(edges);
    init_union(V);
    int result = 0;
    for(int i = 0; i < E; ++i) {
        Edge e = edges[i];
        if(!same(e.u, e.v)) {
            union(e.u, e.v);
            result += e.cost;
        }
    }
    return result;
}