图的存储方式

  • 邻接表法，每个点记录自己的直接邻居，以点集作为单位
  • 邻接矩阵

题目中给的结构不是常见的结构，将其转换为常见的结构再调用算法

数据结构

  • 图
1
2
3
4
5
6
7
8
9
public class Graph {
    // 点集、边集
    public HashMap<Integer, Node> nodes;
    public HashSet<Edge> edges;
    public Graph(){
        nodes = new HashMap<>();
        edges = new HashSet<>();
    }
}
  • 点
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public class Node {
    public int value;
    public int in;      //入度
    public int out;     //出度
    public ArrayList<Node> nexts;   // 直接邻居
    public ArrayList<Edge> edges;   // 点属于的边

    public Node(int value) {
        this.value = value;
        in = 0;
        out = 0;
        nexts = new ArrayList<>();
        edges = new ArrayList<>();
    }
}
  • 边
1
2
3
4
5
6
7
8
9
10
11
public class Edge {
    public int weight;
    public Node from;
    public Node to;

    public Edge(int weight, Node from, Node to) {
        this.weight = weight;
        this.from = from;
        this.to = to;
    }
}

图的生成

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
// from to weight矩阵
public static Graph createGraph(Integer[][] matrix) {
    Graph graph = new Graph();

    for (int i = 0; i < matrix.length; i++) {
        Integer from = matrix[i][0];
        Integer to = matrix[i][1];
        Integer weight = matrix[i][2];
        if (!graph.nodes.containsKey(from)){
            graph.nodes.put(from, new Node(from));
        }
        if (!graph.nodes.containsKey(to)){
            graph.nodes.put(to, new Node(to));
        }
        Node fromNode = graph.nodes.get(from);
        Node toNode = graph.nodes.get(to);
        Edge newEdge = new Edge(weight, fromNode, toNode);
        fromNode.nexts.add(toNode);
        fromNode.out ++ ;
        toNode.in++;
        fromNode.edges.add(newEdge);
        graph.edges.add(newEdge);
    }
    return graph;
}

图的遍历

图的深度优先DFS

  1. 利用栈实现
  2. 从源节点开始把节点按照深度放入栈,然后弹出
  3. 每弹出一个点,把该节点下一个没有进过栈的邻接点放入栈
  4. 直到栈变空
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
public static void dfs(Node node) {
    if (node == null) {
        return;
    }
    Stack<Node> stack = new Stack<>();
    HashSet<Node> set = new HashSet<>();
    stack.add(node);
    set.add(node);
    System.out.println(node.nexts);
    while (!stack.isEmpty()) {
        Node cur = stack.pop();
        for (Node next : cur.nexts) {
            if (!set.contains(next)) {
                stack.push(cur);
                stack.push(next);
                set.add(next);
                System.out.println(next.value);
                break;
            }
        }
    }
}

图的广度优先BFS

  1. 利用队列实现
  2. 从源节点开始依次按照宽度进队列，然后弹出
  3. 每弹出一个点,把该节点所有没有进过队列的邻接点放入队列
  4. 直到队列变空
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public static void bfs(Node node){
    if (node == null){
        return;
    }
    Queue<Node> queue = new LinkedList<>();
    HashSet<Node> set = new HashSet<>();
    queue.add(node);
    set.add(node);
    while (!queue.isEmpty()){
        Node cur = queue.poll();
        System.out.println(cur.value);
        for (Node next : cur.nexts){
            if (!set.contains(next)){
                set.add(next);
                queue.add(next);
            }
        }
    }
}

拓扑排序

要求①有向图②有入度为0的节点③没有环，可以判断有向图是否有环

分析：在程序编译时，往往会有头文件互相依赖的情况，在图中箭头被指向的节点可以看做依赖于指向它的节点。如a依赖于b,c,d，而b又依赖c,k;d依赖k，那么拓扑排序的输出顺序是不依赖别的点的先输出。先输出k,c,删去k,c这时没有别的节点指向b,d了，输出b,d，最后，节点只剩下a再输出。
在图中可以用入度表示依赖情况，入度为零就是没有别的点指向它，可以先输出。输出后其指向的节点入度减一视为删去输出的点。

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
public static List<Node> sortedTopology(Graph graph){
    // key node
    // value 剩余的入度
    HashMap<Node, Integer> inMap = new HashMap<>();
    Queue<Node> zeroInQueue = new LinkedList<>();
    for (Node node : graph.nodes.values()){
        inMap.put(node, node.in);
        if (node.in == 0){
            zeroInQueue.add(node);
        }
    }
    //拓扑排序的结果，依次加入result
    List<Node> result = new ArrayList<>();
    while (!zeroInQueue.isEmpty()){
        Node cur = zeroInQueue.poll();
        result.add(cur);
        for (Node next : cur.nexts){
            inMap.put(next, inMap.get(next)-1);
            if (inMap.get(next) == 0){
                zeroInQueue.add(next);
            }
        }
    }
    return result;
}

最小生成树

定义：使无向图所有节点连通且权重最小的边集，是最小权重生成树的简称。
算法：kruskal算法、prim算法

kruskal算法