数据结构-图

吹梦到西洲
数据结构

发布于：Jul 21, 2020
次浏览

图的遍历与力扣中的一些题目

前言

每次说到”图”这个字，总是会想起一个名为 六度分割 的理论。

六度分隔理论（英语：Six Degrees of Separation）认为世界上任何互不相识的两人，只需要很少的中间人就能够建立起联系。

图的基本知识

图是一种数据结构，现在应用的越来越广泛，如非关系型数据库Neo4j，但是目前图应用的最广泛的领域应该还是社交网络，被重多互联网公司用来分析用户间的关系，分析人际网络，朋友圈。

图由顶点($vertex$) 和 边($edge$) 来表示，其中顶点用来表示实体，而边则用来表示关系。

图的分类

图可以分为无向图，有向图($Directed\ Graph$)，以及加权图($Weighted\ Graph$)三类。

图的类型

  • 无向图：边之间没有方向，可以假设他们现在没什么特殊的联系，也许就是在Twitter上看到了某人的Tweet。
  • 有向图：边之间有方向，可以假设他们在Twitter上谁谁关注了谁谁。
  • 加权图：边上有权重，可以假设为他们之间已经认识了多久的时间了。

图的表示方式

依然记得本科的数据结构课本上提过图有两种表示方式，分别是邻接矩阵与邻接表。

邻接矩阵

邻接矩阵是一个正方形矩阵，其边长等于结点的个数。矩阵的元素通常为数值。在无向图中是关于主对角线对称的。在下图中，矩阵中的元素为 $1$ 则表示两人之间有关系，为 $0$ 则表示没有关系。

img

用邻接矩阵的方式来表示图的查询效率很高，但是，空间利用率却很低，有时候会变成稀疏矩阵。

邻接表

邻接表是一个列表数组，数组的大小等于图中的顶点数。数组特定索引处的列表表示与该顶点相邻的所有顶点。

img

用邻接矩阵的方式来表示图，比较难以创建，而且查询效率较低，但是空间利用率相对较高。

利用Java实现图

在 $Java$ 里是没有提供图这个数据结构的，通过上面几部分可以知道，图的组成要素为顶点和边，那就手动创建一下吧。

1
2
3
4
5
6
7
8
9
10
11
12
public class Vertex {
    
    private String label;
    
    public Vertex() {}
    
    public Vertex(String label) {
        this.label = label;
    }
    
    // equals() and hashCode() 需要重写
}

上面定义的顶点内部属性为 $String$ ，考虑通用性，是应该设置成泛型的。

接下来就选择使用邻接表的方式来表示图。

1
2
3
4
5
6
7
8
9
10
public class Graph {
    
    private Map<Vertex, List<Vertex>> adjVertices;
    
    public Graph() {}
    
    public Graph(Map<Vertex, List<Vertex>> adjVertices) {
        this.adjVertices = adjVertices;
    }
}

添加/删除顶点

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
/**
* 在顶点集合中增加结点。
*/
public void addVertex(String label) {
    adjVertices.putIfAbsent(new Vertex(label), new ArrayList<>());
}

/**
* 在顶点集合中删除结点。
*/
public void removeVertex(String label) {
    Vertex v = new Vertex(label);
    adjVertices.values().stream().forEach(e -> e.remove(v));
    adjVertices.remove(new Vertex(label));
}

添加/删除边

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
/**
* 创建一条新的边并更新相邻的顶点
*/
public void addEdge(String label1, String label2) {
    Vertex v1 = new Vertex(label1);
    Vertex v2 = new Vertex(label2);
    adjVertices.get(v1).add(v2);
    adjVertices.get(v2).add(v1);
}

/**
* 删除边
*/
public void removeEdge(String label1, String label2) {
    Vertex v1 = new Vertex(label1);
    Vertex v2 = new Vertex(label2);
    List<Vertex> eV1 = adjVertices.get(v1);
    List<Vertex> eV2 = adjVertices.get(v2);
    if (eV1 != null)
        eV1.remove(v2);
    if (eV2 != null)
        eV2.remove(v1);
}

构造图

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public Graph createGraph() {
    Graph graph = new Graph();
    graph.addVertex("Bob");
    graph.addVertex("Alice");
    graph.addVertex("Mark");
    graph.addVertex("Rob");
    graph.addVertex("Maria");
    graph.addEdge("Bob", "Alice");
    graph.addEdge("Bob", "Rob");
    graph.addEdge("Alice", "Mark");
    graph.addEdge("Rob", "Mark");
    graph.addEdge("Alice", "Maria");
    graph.addEdge("Rob", "Maria");
    return graph;
}

获取某个顶点的邻接点

1
2
3
public List<Vertex> getAdjVertices(String label) {
    return adjVertices.get(new Vertex(label));
}

图的遍历

前面定义好了图的基本结构与方法，是时候开始真正的操作了。

DFS

深度优先遍历从任意根顶点开始，并沿每个分支探索尽可能深的顶点，然后再探索同一级别的顶点。

涉及到深度的用栈，涉及到广度的用队列。这应该没什么疑问吧？

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
/**
* 深度优先遍历
*/
public Set<String> depthFirstTraversal(Graph graph, String root) {
    Set<String> visited = new LinkedHashSet<>();
    Stack<String> stack = new Stack<>();
    stack.push(root);
    while (!stack.isEmpty()) {
        String vertex = stack.pop();
        if (!visited.contains(vertex)) {
            visited.add(vertex);
            for (Vertex v : graph.getAdjVertices(vertex))
                stack.push(v.label);
        }
    }
    return visited;
}

BFS

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public Set<String> breadthFirstTraversal(Graph graph, String root) {
    Set<String> visited = new LinkedHashSet<>();
    Queue<String> queue = new LinkedList<>();
    queue.add(root);
    visited.add(root);
    while (!queue.isEmpty()) {
        String vertex = queue.poll();
        for (Vertex v : graph.getAdjVertices(vertex)) {
            if (!visited.contains(v.label)) {
                visited.add(v.label);
                queue.add(v.label);
            }
        }
    }
    return visited;
}

求图的强连通分量

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
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
import java.util.*;

/**
 * @AUTHOR: raymond
 * @DATETIME: 2020/8/12  08:38
 * DESCRIPTION: 寻找图中的最大强连通分量
 * 采用邻接表表示
 * 算法思想：一个具有最大强连通分量的有向图的逆转图仍然具有相同的强连通分量
 **/
public class KosarajuGraph {

    private int V;

    private LinkedList<Integer>[] adj;

    public KosarajuGraph(int V) {
        this.V = V;
        adj = new LinkedList[V];
        for (int i = 0; i < V; ++i)
            adj[i] = new LinkedList<>();
    }

    /**
     * 添加边 注意只有有向图才有强连通分量
     * @param s 起点
     * @param d 终点
     */
    public void addEdge(int s, int d) {
        adj[s].add(d);
    }

    /**
     * 深度优先遍历工具类
     * @param s 起点
     * @param visitedVertices 访问列表
     */
    public void DFSUtil(int s, boolean[] visitedVertices) {
        visitedVertices[s] = true;
        System.out.print(s + " ");
        int n;

        for (Integer integer : adj[s]) {
            n = integer;
            if (!visitedVertices[n])
                DFSUtil(n, visitedVertices);
        }
    }

    /**
     * 逆转图
     * @return 方向调转之后的图
     */
    public KosarajuGraph transpose() {
        KosarajuGraph g = new KosarajuGraph(V);
        for (int s = 0; s < V; s++) {
            for (Integer integer : adj[s])
                g.adj[integer].add(s);
        }
        return g;
    }

    public void fillOrder(int s, boolean[] visitedVertices, Deque<Integer> stack) {
        visitedVertices[s] = true;
        for (int n : adj[s]) {
            if (!visitedVertices[n])
                fillOrder(n, visitedVertices, stack);
        }
        stack.push(s);
    }

    public void printSCC() {
        Deque<Integer> stack = new ArrayDeque<>();
        boolean[] visitedVertices = new boolean[V];
        // 1. 初始化访问列表
        for (int i = 0; i < V; i++)
            visitedVertices[i] = false;

        for (int i = 0; i < V; i++) {
            if (!visitedVertices[i])
                fillOrder(i, visitedVertices, stack);
        }

        KosarajuGraph graph = transpose();

        for (int i = 0; i < V; i++)
            visitedVertices[i] = false;

        while (!stack.isEmpty()) {
            int s = stack.pop();
            if (!visitedVertices[s]) {
                graph.DFSUtil(s, visitedVertices);
                System.out.println();
            }
        }
    }

    public static void main(String args[]) {
        KosarajuGraph g = new KosarajuGraph(8);
        g.addEdge(0, 1);
        g.addEdge(1, 2);
        g.addEdge(2, 3);
        g.addEdge(2, 4);
        g.addEdge(3, 0);
        g.addEdge(4, 5);
        g.addEdge(5, 6);
        g.addEdge(6, 4);
        g.addEdge(6, 7);

        System.out.println("Strongly Connected Components:");
        g.printSCC();
    }
}

Kruskal MST

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
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
import java.util.Arrays;

/**
 * @AUTHOR: raymond
 * @DATETIME: 2020/8/12  09:08
 * DESCRIPTION: Kruskal 算法生成最小生成树 O(e*lge)
 * 1. Sort all the edges from low weight to high
 * 2. Take the edge with the lowest weight and add it to the spanning tree.
 *      If adding the edge created a cycle, then reject this edge.
 * 3. Keep adding edges until we reach all vertices.
 **/
public class KruskalGraph {

    private int vertices, edges;

    private Edge[] edge;

    public KruskalGraph(int v, int e) {
        this.vertices = v;
        this.edges = e;
        this.edge = new Edge[edges];
        for (int i = 0; i < e; i++)
            edge[i] = new Edge();
    }

    public int find(Subset[] subsets, int i) {
        if (subsets[i].parent != i)
            subsets[i].parent = find(subsets, subsets[i].parent);
        return subsets[i].parent;
    }

    public void union(Subset[] subsets, int x, int y) {
        int xRoot = find(subsets, x);
        int yRoot = find(subsets, x);

        if (subsets[xRoot].rank < subsets[yRoot].rank)
            subsets[xRoot].parent = yRoot;
        else if (subsets[xRoot].rank > subsets[yRoot].rank)
            subsets[yRoot].parent = xRoot;
        else {
            subsets[yRoot].parent = xRoot;
            subsets[xRoot].rank++;
        }
    }

    /**
     * Kruskal 具体实现
     */
    public void kruskal() {
        Edge[] res = new Edge[vertices];
        int e = 0, i = 0;
        for (i = 0; i < vertices; ++i)
            res[i] = new Edge();

        // 1. 排序
        Arrays.sort(edge);
        Subset[] subsets = new Subset[vertices];
        for (i = 0; i < vertices; ++i)
            subsets[i] = new Subset();

        for (int v = 0; v < vertices; ++v) {
            subsets[v].parent = v;
            subsets[v].rank = 0;
        }
        i = 0;
        while (e < vertices - 1) {
            Edge nextEdge = new Edge();
            nextEdge = edge[i++];
            int x = find(subsets, nextEdge.src);
            int y = find(subsets, nextEdge.dest);
            if (x != y) {
                res[e++] = nextEdge;
                union(subsets, x, y);
            }
        }

        for (i = 0; i < e; ++i)
            System.out.println("src-" + res[i].src + " - " + "dest-" + res[i].dest + " - " + "weight-" + res[i].weight);
    }

    public static void main(String[] args) {
        int vertices = 6; // Number of vertices
        int edges = 8; // Number of edges
        KruskalGraph G = new KruskalGraph(vertices, edges);

        G.edge[0].src = 0;
        G.edge[0].dest = 1;
        G.edge[0].weight = 4;

        G.edge[1].src = 0;
        G.edge[1].dest = 2;
        G.edge[1].weight = 4;

        G.edge[2].src = 1;
        G.edge[2].dest = 2;
        G.edge[2].weight = 2;

        G.edge[3].src = 2;
        G.edge[3].dest = 3;
        G.edge[3].weight = 3;

        G.edge[4].src = 2;
        G.edge[4].dest = 5;
        G.edge[4].weight = 2;

        G.edge[5].src = 2;
        G.edge[5].dest = 4;
        G.edge[5].weight = 4;

        G.edge[6].src = 3;
        G.edge[6].dest = 4;
        G.edge[6].weight = 3;

        G.edge[7].src = 5;
        G.edge[7].dest = 4;
        G.edge[7].weight = 3;
        G.kruskal();
    }

    // 需要比较边的权重大小
    static class Edge implements Comparable<Edge> {
        int src, dest, weight;

        @Override
        public int compareTo(Edge o) {
            return this.weight - o.weight;
        }
    }

    static class Subset { int parent, rank; }

}

Prim MST

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
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
import java.util.Arrays;

/**
 * @AUTHOR: raymond
 * @DATETIME: 2020/8/12  09:33
 * DESCRIPTION: Prim 算法生成最小生成树 O(ElgV)
 * 1. Initialize the minimum spanning tree with a vertex chosen at random.
 * 2. Find all the edges that connect the tree to new vertices, find the minimum and add it to the tree.
 * 3. Keep repeating step 2 until we get a minimum spanning tree.
 **/
public class PrimGraph {

    public void prim(int G[][], int V) {

        int noEdge; // number of edge

        // 创建一个数组，用于跟踪已选择的边。已选为 true，否则为 false.
        boolean[] selected = new boolean[V];

        // 初始化
        Arrays.fill(selected, false);
        noEdge = 0;

        // Step 1: 选择第 0 个结点
        selected[0] = true;

        // 打印边与权重表头
        System.out.println("Edge : Weight");

        // 最小生成树中的边的数量总是会小于 V - 1
        while (noEdge < V - 1) {
            int min = Integer.MAX_VALUE;
            int x = 0; // row number
            int y = 0; // col number

            for (int i = 0; i < V; i++) {
                // 对于集合 S 中的每个顶点，找到这个顶点的所有邻接顶点，
                if (selected[i]) {
                    for (int j = 0; j < V; j++) {
                        // 未被选择并且两点之间存在边
                        if (!selected[j] && G[i][j] != 0) {
                            // 比较 Step 1 中选择的顶点与其邻接点之间的距离
                            if (min > G[i][j]) {
                                min = G[i][j];
                                x = i;
                                y = j;
                            }
                        }
                    }
                }
            }
            System.out.println(x + " - " + y + " :  " + G[x][y]);
            // 如果顶点已经在集合 S 中，丢弃。
            // 否则选择另一个与 Step 1 选出的顶点最近的顶点
            selected[y] = true;
            noEdge++;
        }
    }

    public static void main(String[] args) {
        PrimGraph g = new PrimGraph();

        // number of vertices in graph
        int V = 5;

        // 创建一个 5x5 大小的二维邻接矩阵
        int[][] G = { { 0, 9, 75, 0, 0 },
                      { 9, 0, 95, 19, 42 },
                      { 75, 95, 0, 51, 66 },
                      { 0, 19, 51, 0, 31 },
                      { 0, 42, 66, 31, 0 } };

        g.prim(G, V);
    }
}

图的Java库

博客内容遵循 署名-非商业性使用-相同方式共享 4.0 国际 (CC BY-NC-SA 4.0) 协议

本文永久链接是：http://raymond-zhao.top/2020/07/21/2020-07-21-DS-Graph/

更新于：Jun 20, 2021

图

评论