10. 图

图的表达方式：

• 邻接表法
• 邻接矩阵法
• 二维数组表示法

图结构的定义

1. 节点的定义描述 ```java import java.util.ArrayList;

/**

• 图的点结构描述 */ public class Node { public int value; // 节点值 public int in; // 入度 public int out; // 出度 public ArrayList nexts; // 从自己出发到达的邻居节点 public ArrayList edges; // 从自己出发构成的边

  public Node(int value) {

   this.value = value;
   in = 0;
   out = 0;
   nexts = new ArrayList<>();
   edges = new ArrayList<>();

  } }

2. 边结构描述
```java
/**
 * 图的边结构描述
 */
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. 图结构描述 ```java import java.util.HashMap; import java.util.HashSet;

/**

• 图：由点集和边集构成的结构 */ public class Graph { public HashMap nodes; // integer和node一一对应 public HashSet edges;

  public Graph() {

   nodes = new HashMap<>();
   edges = new HashSet<>();

  } } 将图结构转换为熟悉的图结构java /**

• 图结构转换，将二维数组转换为自己熟悉的图结构 */ public class GraphGenerator {

  // matrix 所有的边 // N*3 的矩阵 // [weight, from节点上面的值，to节点上面的值] // // [ 5 , 0 , 7] // [ 3 , 0, 1] // public static Graph createGraph(int[][] matrix) {

   Graph graph = new Graph();
   for (int i = 0; i < matrix.length; i++) {
        // 拿到每一条边， matrix[i] 
       int weight = matrix[i][0];
       int from = matrix[i][1];
       int to = matrix[i][2];
       // 判断是from和to值对应的节点是否建过，如果没建过，向图节点集中添加建立节点。
       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);
       // 拿出from和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;

  } }

<a name="vFdZA"></a>
## BFS
```java
// 从node出发，进行宽度优先遍历
public static void bfs(Node start) {
    if (start == null) {
        return;
    }
    Queue<Node> queue = new LinkedList<>();
    HashSet<Node> set = new HashSet<>();
    queue.add(start);
    set.add(start);
    while (!queue.isEmpty()) {
        Node cur = queue.poll();// 出队再打印
        System.out.println(cur.value);
        for (Node next : cur.nexts) {
            if (!set.contains(next)) { // 判断cur的后继节点是否遍历过，没有遍历入队，遍历过pass
                set.add(next);
                queue.add(next);
            }
        }
    }
}

DFS

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.value);
    while (!stack.isEmpty()) {
        Node cur = stack.pop();
        for (Node next : cur.nexts) {
            if (!set.contains(next)) {  // 如果发现set中邻居节点没有注册，弹出节点进栈，邻居节点进栈，邻居节点注册，打印。结束
                stack.push(cur);
                stack.push(next); //
                set.add(next);  // 注册
                System.out.println(next.value);
                break;
            }
        }
    }
}

拓扑排序

// directed graph and no loop
public static List<Node> sortedTopology(Graph graph) {
    // key 为某个节点   value 剩余的入度
    HashMap<Node, Integer> inMap = new HashMap<>();
    // 只有剩余入度为0的点，才进入这个队列
    Queue<Node> zeroInQueue = new LinkedList<>();

    // 寻找图初始状态入度为0的节点
    for (Node node : graph.nodes.values()) {
        inMap.put(node, node.in);
        if (node.in == 0) {
            zeroInQueue.add(node);
        }
    }

    List<Node> result = new ArrayList<>();
    while (!zeroInQueue.isEmpty()) {
        Node cur = zeroInQueue.poll();
        result.add(cur);
        // 消除该点所有的影响
        for (Node next : cur.nexts) {
            // 邻居节点入度-1
            inMap.put(next, inMap.get(next) - 1);
            if (inMap.get(next) == 0) {
                zeroInQueue.add(next);
            }
        }
    }
    return result;
}