KWAN的解忧杂货铺

# 一.图的概念

# 1.概念

图是由顶点（vertex）和边（edge）组成的数据结构，例如

graph LR
    A--->B
    A--->C
    B--->D
    C--->D
1
2
3
4
5
6

该图有四个顶点：A、B、C、D 以及四条有向边，有向图中，边是单向的

# 2.有向 vs 无向

如果是无向图，那么边是双向的，下面是一个无向图的例子

graph LR
    A---B
    A---C
    B---D
    C---D
1
2
3
4
5

# 3.度

度是指与该顶点相邻的边的数量

graph LR
    A((A))---B((B))
    A---C((C))
    B---D((D))
    C---D
    D---E((E))
    D---F((F))
    E---F
    A & B & C & D & E & F
1
2
3
4
5
6
7
8
9
10

例如上图中

  • A、B、C、E、F 这几个顶点度数为 2
  • D 顶点度数为 4

有向图中，细分为入度和出度，参见下图

graph LR
    A((A))-->B((B))
    A-->C((C))
    B-->D((D))
    C-->D
    D-->E((E))
    D-->F((F))
    E-->F
    A & B & C & D & E & F
1
2
3
4
5
6
7
8
9
10
  • A (2 out / 0 in)
  • B、C、E (1 out / 1 in)
  • D (2 out / 2 in)
  • F (0 out / 2 in)

# 4.权

边可以有权重，代表从源顶点到目标顶点的距离、费用、时间或其他度量。

graph LR
    BJ((北京))
    WH((武汉))
    GZ((广州))
    SH((上海))
    BJ---800km-->WH
    BJ---1900km-->GZ
    BJ---1200km-->SH
    WH---1050km-->GZ
    WH---700km-->SH
1
2
3
4
5
6
7
8
9
10
11

# 5.路径

路径被定义为从一个顶点到另一个顶点的一系列连续边，例如上图中【北京】到【上海】有多条路径

  • 北京 - 上海
  • 北京 - 武汉 - 上海

路径长度

  • 不考虑权重，长度就是边的数量
  • 考虑权重，一般就是权重累加

# 6.环

在有向图中，从一个顶点开始，可以通过若干条有向边返回到该顶点，那么就形成了一个环

graph LR
  A((A))
  B((B))
  C((C))
  D((D))
  E((E))

  A--->B
  B--->C
  C--->D
  D--->E
  E--->A
1
2
3
4
5
6
7
8
9
10
11
12
13

# 7.图的连通性

如果两个顶点之间存在路径，则这两个顶点是连通的，所有顶点都连通，则该图被称之为连通图，若子图连通，则称为连通分量

graph LR
    A --- B
    A --- C
    C --- D
    D --- E
    B --- E
    F --- G
    G --- H
    H --- F
    I --- J
1
2
3
4
5
6
7
8
9
10
11

# 二.DFS 和 BFS

比如说，下面的图

graph LR
    A---B
    A---C
    B---D
    C---D
1
2
3
4
5

用邻接矩阵可以表示为：

  A B C D
A 0 1 1 0
B 1 0 0 1
C 1 0 0 1
D 0 1 1 0
1
2
3
4
5

用邻接表可以表示为：

A -> B -> C
B -> A -> D
C -> A -> D
D -> B -> C
1
2
3
4

有向图的例子

graph LR
    A--->B
    A--->C
    B--->D
    C--->D
1
2
3
4
5
  A B C D
A 0 1 1 0
B 0 0 0 1
C 0 0 0 1
D 0 0 0 0
1
2
3
4
5
A - B - C
B - D
C - D
D - empty
1
2
3
4

# 1.Java 表示

顶点

public class Vertex {
    String name;
    List<Edge> edges;

    // 拓扑排序相关
    int inDegree;
    int status; // 状态 0-未访问 1-访问中 2-访问过，用在拓扑排序

    // dfs, bfs 相关
    boolean visited;

    // 求解最短距离相关
    private static final int INF = Integer.MAX_VALUE;
    int dist = INF;
    Vertex prev = null;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

边

public class Edge {

    Vertex linked;
    int weight;

    public Edge(Vertex linked) {
        this(linked, 1);
    }

    public Edge(Vertex linked, int weight) {
        this.linked = linked;
        this.weight = weight;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

# 2.DFS

public class Dfs {
    public static void main(String[] args) {
        Vertex v1 = new Vertex("v1");
        Vertex v2 = new Vertex("v2");
        Vertex v3 = new Vertex("v3");
        Vertex v4 = new Vertex("v4");
        Vertex v5 = new Vertex("v5");
        Vertex v6 = new Vertex("v6");

        v1.edges = List.of(new Edge(v3), new Edge(v2), new Edge(v6));
        v2.edges = List.of(new Edge(v4));
        v3.edges = List.of(new Edge(v4), new Edge(v6));
        v4.edges = List.of(new Edge(v5));
        v5.edges = List.of();
        v6.edges = List.of(new Edge(v5));

        dfs1(v1);
    }

    private static void dfs2(Vertex v) {
        LinkedList<Vertex> stack = new LinkedList<>();
        stack.push(v);
        while (!stack.isEmpty()) {
            Vertex pop = stack.pop();
            pop.visited = true;
            System.out.println(pop.name);
            for (Edge edge : pop.edges) {
                if (!edge.linked.visited) {
                    stack.push(edge.linked);
                }
            }
        }
    }

    private static void dfs1(Vertex v) {
        v.visited = true;
        System.out.println(v.name);
        for (Edge edge : v.edges) {
            if (!edge.linked.visited) {
                dfs(edge.linked);
            }
        }
    }
}
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

# 3.BFS

public class Bfs {
    public static void main(String[] args) {
        Vertex v1 = new Vertex("v1");
        Vertex v2 = new Vertex("v2");
        Vertex v3 = new Vertex("v3");
        Vertex v4 = new Vertex("v4");
        Vertex v5 = new Vertex("v5");
        Vertex v6 = new Vertex("v6");

        v1.edges = List.of(new Edge(v3), new Edge(v2), new Edge(v6));
        v2.edges = List.of(new Edge(v4));
        v3.edges = List.of(new Edge(v4), new Edge(v6));
        v4.edges = List.of(new Edge(v5));
        v5.edges = List.of();
        v6.edges = List.of(new Edge(v5));

        bfs(v1);
    }

    private static void bfs(Vertex v) {
        LinkedList<Vertex> queue = new LinkedList<>();
        v.visited = true;
        queue.offer(v);
        while (!queue.isEmpty()) {
            Vertex poll = queue.poll();
            System.out.println(poll.name);
            for (Edge edge : poll.edges) {
                if (!edge.linked.visited) {
                    edge.linked.visited = true;
                    queue.offer(edge.linked);
                }
            }
        }
    }
}
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

# 三.拓扑排序

# 1.什么是拓扑排序?

拓扑排序（Topological Sorting）是一种用于有向图（Directed Acyclic Graph，DAG）的节点排序算法。在拓扑排序中，图中的节点被安排成线性顺序，满足以下条件：

  1. 对于任意的有向边 (u, v)，节点 u 在节点 v 之前。
  2. 图中不能包含环路（即，图必须是有向无环图，DAG）。

拓扑排序主要应用于描述一些任务或事件之间的依赖关系，其中每个节点代表一个任务或事件，有向边表示依赖关系。通过拓扑排序，你可以确定任务或事件的执行顺序，以确保没有依赖关系被破坏。

拓扑排序算法通常使用深度优先搜索（DFS）或广度优先搜索（BFS）来实现。算法的基本思想是从入度为 0 的节点开始，逐步移除这些节点及其出边，然后继续处理新的入度为 0 的节点，直到所有节点都被处理。

拓扑排序在许多领域有广泛的应用，包括编译器优化、任务调度、依赖分析、项目管理等。它是一种非常有用的算法，用于解决有向图中的依赖关系问题。

graph LR
	HTML[网页基础] --> WEB
    SE[Java 基础] --> WEB[Java Web]
    DB[数据库] --> Spring
    WEB --> Spring[Spring框架]
    Spring --> Micro[微服务框架]
    Micro --> Project[实战项目]
1
2
3
4
5
6
7

# 2.BFS

public class TopologicalSort {
    public static void main(String[] args) {
        Vertex v1 = new Vertex("网页基础");
        Vertex v2 = new Vertex("Java基础");
        Vertex v3 = new Vertex("JavaWeb");
        Vertex v4 = new Vertex("Spring框架");
        Vertex v5 = new Vertex("微服务框架");
        Vertex v6 = new Vertex("数据库");
        Vertex v7 = new Vertex("实战项目");

        v1.edges = List.of(new Edge(v3)); // +1
        v2.edges = List.of(new Edge(v3)); // +1
        v3.edges = List.of(new Edge(v4));
        v6.edges = List.of(new Edge(v4));
        v4.edges = List.of(new Edge(v5));
        v5.edges = List.of(new Edge(v7));
        v7.edges = List.of();

        List<Vertex> graph = List.of(v1, v2, v3, v4, v5, v6, v7);
        // 1. 统计每个顶点的入度
        for (Vertex v : graph) {
            for (Edge edge : v.edges) {
                edge.linked.inDegree++;
            }
        }
        /*for (Vertex vertex : graph) {
            System.out.println(vertex.name + " " + vertex.inDegree);
        }*/
        // 2. 将入度为0的顶点加入队列
        LinkedList<Vertex> queue = new LinkedList<>();
        for (Vertex v : graph) {
            if (v.inDegree == 0) {
                queue.offer(v);
            }
        }
        // 3. 队列中不断移除顶点，每移除一个顶点，把它相邻顶点入度减1，若减到0则入队
        List<String> result = new ArrayList<>();
        while (!queue.isEmpty()) {
            Vertex poll = queue.poll();
//            System.out.println(poll.name);
            result.add(poll.name);
            for (Edge edge : poll.edges) {
                edge.linked.inDegree--;
                if (edge.linked.inDegree == 0) {
                    queue.offer(edge.linked);
                }
            }
        }
        if (result.size() != graph.size()) {
            System.out.println("出现环");
        } else {
            for (String key : result) {
                System.out.println(key);
            }
        }
    }
}
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

# 3.DFS

public class TopologicalSortDFS {

    public static void main(String[] args) {
        Vertex v1 = new Vertex("网页基础");
        Vertex v2 = new Vertex("Java基础");
        Vertex v3 = new Vertex("JavaWeb");
        Vertex v4 = new Vertex("Spring框架");
        Vertex v5 = new Vertex("微服务框架");
        Vertex v6 = new Vertex("数据库");
        Vertex v7 = new Vertex("实战项目");

        v1.edges = List.of(new Edge(v3));
        v2.edges = List.of(new Edge(v3));
        v3.edges = List.of(new Edge(v4));
        v6.edges = List.of(new Edge(v4));
        v4.edges = List.of(new Edge(v5));
        v5.edges = List.of(new Edge(v7));
        v7.edges = List.of();

        List<Vertex> graph = List.of(v1, v2, v3, v4, v5, v6, v7);
        LinkedList<String> result = new LinkedList<>();
        for (Vertex v : graph) {
            if(v.status==0) {
                dfs(v, result);
            }
        }
        System.out.println(result);
    }

    private static void dfs(Vertex v, LinkedList<String> result) {
        if (v.status == 2) {
            return;
        }
        if (v.status == 1) {
            throw new RuntimeException("发现环");
        }
        v.status = 1;
        for (Edge edge : v.edges) {
            dfs(edge.linked, result);
        }
        v.status = 2;
        result.push(v.name);
    }
}
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

# 4.Kahn

是的，Kahn 算法是一种使用广度优先搜索（BFS）的拓扑排序算法。该算法是由 Arthur Kahn 于 1962 年提出的，用于对有向无环图（DAG）进行拓扑排序。

Kahn 算法的基本思想是不断找到入度为 0 的节点，然后从图中移除这些节点及其出边，直到所有节点都被处理。这个过程与广度优先搜索类似，因此它使用了 BFS 的思想。

Kahn 算法的主要步骤包括：

  1. 初始化一个队列，将所有入度为 0 的节点加入队列。
  2. 从队列中取出一个节点，将其加入拓扑排序的结果中，并移除与该节点关联的出边，相应地更新相关节点的入度。
  3. 重复步骤 2，直到队列为空。

Kahn 算法的时间复杂度为 O(V + E)，其中 V 是图中的节点数，E 是图中的边数。它是一种有效的拓扑排序算法，用于处理有向无环图中的依赖关系。

# 四.习题

# 1.图-相关题目

题目编号 题目标题 算法思想
547 省份数量 DFS、BFS、并查集
797 所有可能路径 DFS、BFS
1584 连接所有点的最小费用 最小生成树
743 网络延迟时间 单源最短路径
787 K 站中转内最便宜的航班 单源最短路径
207 课程表 拓扑排序
210 课程表 II 拓扑排序
上次更新: 10/29/2024, 10:27:50 AM

02-最短路径 →