什么是图

—

一些理论

• 在线性结构中，数据元素之间满足唯一的线性关系，每个数据元素(除第一个和最后一个外)只有一个直接前驱和一个直接后继；
• 在树形结构中，数据元素之间有着明显的层次关系，并且每个数据元素只与上一层中的一个元素(parent node)及下一层的多个元素(孩子节点)相关；
• 在图形结构中，节点之间的关系是任意的，图中任意两个数据元素之间都有可能相关。

图G由两个集合V(顶点)和E(边)组成，定义为G=(V，E)。

图的分类

—

无向图

有向图

无权图

连接线上没有数值的图可以认为是无权图

有权图

其实所有的图都可以认为是有向图，无向图可以看为是两个方向的有向图

度

无向图

节点V的度是3

有向图分为入度和出度。

V的入度2，出度1。

对应现实生活中图的系统建模

—

比如对交通流量建模，顶点可以表示街道的十字路口，边表示街道。加权的边可以表示限速或者车道的数量。建模人员可以用这个系统来判断最佳路线及最有可能堵车的街道。

任何运输系统都可以用图来建模。比如，航空公司可以用图来为其飞行系统建模。将每个机场看成顶点，将经过两个顶点的每条航线看作一条边。加权的边可以看作从一个机场到另一个机场的航班成本，或两个机场之间的距离，这取决与建模的对象是什么。

包含局域网和广域网（如互联网）在内的计算机网络，同样经常用图来建模。

可以用图来建模的实现系统是消费市场，顶点可以用来表示供应商和消费者。

还有比如朋友圈，朋友的互相关系。

图在内存中的实现

—

概要

• 节点(Vertex) 与 边（Edge）
• 图的表示： 邻接表 和 邻接矩阵（平时工作中很少这样表示）
• 这里可以分为 有向图 和无向图
  无向图是一种特殊的有向图
• 有权图 和 无权图

图的遍历

对节点表示

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<>();
    }
}

对边的表示

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;
    }

对整个图的表示

public class Graph {
    public HashMap<Integer,Node> nodes; // 所有的点
    public HashSet<Edge> edges; // 所有的边


    public Graph() {
        nodes = new HashMap<>();
        edges = new HashSet<>();
    }
}

广度优先遍历（BFS）

public class GraphBFS {
    // 从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);
        System.out.println(start.value);
        while (!queue.isEmpty()){
            Node cur = queue.poll();
            for (Node node:cur.nexts){
                if (!set.contains(node)){
                    queue.add(node);
                    set.add(node);
                    System.out.println(start.value);
                }
            }
        }
    }

深度优先遍历(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 find:cur.nexts){
                if (!set.contains(find)){
                    stack.add(cur);
                    stack.add(find);
                    System.out.println(find.value);
                    break;
                }
            }
        }
    }

最小生成树

—

一般最小生成树有三种解决思想

• kruska:从点开始找到最小的那棵树
• Prim:边开始找最小的那棵树
• Dijkstra:指定一个节点，计算 这个节点到其他节点的最短路径，有点类似全局最优解

代码

kruska 解法

// Union-Find Set
  public static class UnionFind {
    // key 某一个节点， value key节点往上的节点
    private HashMap<Node, Node> fatherMap;
    // key 某一个集合的代表节点, value key所在集合的节点个数
    private HashMap<Node, Integer> sizeMap;


    public UnionFind() {
      fatherMap = new HashMap<Node, Node>();
      sizeMap = new HashMap<Node, Integer>();
    }
    
    public void makeSets(Collection<Node> nodes) {
      fatherMap.clear();
      sizeMap.clear();
      for (Node node : nodes) {
        fatherMap.put(node, node);
        sizeMap.put(node, 1);
      }
    }


    private Node findFather(Node n) {
      Stack<Node> path = new Stack<>();
      while(n != fatherMap.get(n)) {
        path.add(n);
        n = fatherMap.get(n);
      }
      while(!path.isEmpty()) {
        fatherMap.put(path.pop(), n);
      }
      return n;
    }


    public boolean isSameSet(Node a, Node b) {
      return findFather(a) == findFather(b);
    }


    public void union(Node a, Node b) {
      if (a == null || b == null) {
        return;
      }
      Node aDai = findFather(a);
      Node bDai = findFather(b);
      if (aDai != bDai) {
        int aSetSize = sizeMap.get(aDai);
        int bSetSize = sizeMap.get(bDai);
        if (aSetSize <= bSetSize) {
          fatherMap.put(aDai, bDai);
          sizeMap.put(bDai, aSetSize + bSetSize);
          sizeMap.remove(aDai);
        } else {
          fatherMap.put(bDai, aDai);
          sizeMap.put(aDai, aSetSize + bSetSize);
          sizeMap.remove(bDai);
        }
      }
    }
  }
  


  public static class EdgeComparator implements Comparator<Edge> {


    @Override
    public int compare(Edge o1, Edge o2) {
      return o1.weight - o2.weight;
    }


  }


  public static Set<Edge> kruskalMST(Graph graph) {
    UnionFind unionFind = new UnionFind();
    unionFind.makeSets(graph.nodes.values());
    // 从小的边到大的边，依次弹出，小根堆！
    PriorityQueue<Edge> priorityQueue = new PriorityQueue<>(new EdgeComparator());
    for (Edge edge : graph.edges) { // M 条边
      priorityQueue.add(edge);  // O(logM)
    }
    Set<Edge> result = new HashSet<>();
    while (!priorityQueue.isEmpty()) { // M 条边
      Edge edge = priorityQueue.poll(); // O(logM)
      if (!unionFind.isSameSet(edge.from, edge.to)) { // O(1)
        result.add(edge);
        unionFind.union(edge.from, edge.to);
      }
    }
    return result;
  }

Prim解法

public static class EdgeComparator implements Comparator<Edge> {


    @Override
    public int compare(Edge o1, Edge o2) {
      return o1.weight - o2.weight;
    }


  }


  public static Set<Edge> primMST(Graph graph) {
    // 解锁的边进入小根堆
    PriorityQueue<Edge> priorityQueue = new PriorityQueue<>(new EdgeComparator());


    // 哪些点被解锁出来了
    HashSet<Node> nodeSet = new HashSet<>();
    
    
    
    Set<Edge> result = new HashSet<>(); // 依次挑选的的边在result里


    for (Node node : graph.nodes.values()) { // 随便挑了一个点
      // node 是开始点
      if (!nodeSet.contains(node)) {
        nodeSet.add(node);
        for (Edge edge : node.edges) { // 由一个点，解锁所有相连的边
          priorityQueue.add(edge);
        }
        while (!priorityQueue.isEmpty()) {
          Edge edge = priorityQueue.poll(); // 弹出解锁的边中，最小的边
          Node toNode = edge.to; // 可能的一个新的点
          if (!nodeSet.contains(toNode)) { // 不含有的时候，就是新的点
            nodeSet.add(toNode);
            result.add(edge);
            for (Edge nextEdge : toNode.edges) {
              priorityQueue.add(nextEdge);
            }
          }
        }
      }
      // break;
    }
    return result;
  }

Dijkstra 普通解法

public static HashMap<Node, Integer> dijkstra1(Node from) {
        HashMap<Node, Integer> distanceMap = new HashMap<>();
        distanceMap.put(from, 0);
        // 打过对号的点
        HashSet<Node> selectedNodes = new HashSet<>();
        Node minNode = getMinDistanceAndUnselectedNode(distanceMap, selectedNodes);
        while (minNode != null) {
            //  原始点  ->  minNode(跳转点)   最小距离distance
            int distance = distanceMap.get(minNode);
            for (Edge edge : minNode.edges) {
                Node toNode = edge.to;
                if (!distanceMap.containsKey(toNode)) {
                    distanceMap.put(toNode, distance + edge.weight);
                } else { // toNode
                    distanceMap.put(edge.to, Math.min(distanceMap.get(toNode), distance + edge.weight));
                }
            }
            selectedNodes.add(minNode);
            minNode = getMinDistanceAndUnselectedNode(distanceMap, selectedNodes);
        }
        return distanceMap;
    }


    public static Node getMinDistanceAndUnselectedNode(HashMap<Node, Integer> distanceMap, HashSet<Node> touchedNodes) {
        Node minNode = null;
        int minDistance = Integer.MAX_VALUE;
        for (Map.Entry<Node, Integer> entry : distanceMap.entrySet()) {
            Node node = entry.getKey();
            int distance = entry.getValue();
            if (!touchedNodes.contains(node) && distance < minDistance) {
                minNode = node;
                minDistance = distance;
            }
        }
        return minNode;
    }

Dijkstra 自定义堆优化解法

public static class NodeRecord {
    public Node node;
    public int distance;


    public NodeRecord(Node node, int distance) {
      this.node = node;
      this.distance = distance;
    }
  }


  public static class NodeHeap {
    private Node[] nodes; // 实际的堆结构
    // key 某一个node， value 上面堆中的位置
    private HashMap<Node, Integer> heapIndexMap;
    // key 某一个节点， value 从源节点出发到该节点的目前最小距离
    private HashMap<Node, Integer> distanceMap;
    private int size; // 堆上有多少个点


    public NodeHeap(int size) {
      nodes = new Node[size];
      heapIndexMap = new HashMap<>();
      distanceMap = new HashMap<>();
      size = 0;
    }


    public boolean isEmpty() {
      return size == 0;
    }


    // 有一个点叫node，现在发现了一个从源节点出发到达node的距离为distance
    // 判断要不要更新，如果需要的话，就更新
    public void addOrUpdateOrIgnore(Node node, int distance) {
      if (inHeap(node)) {
        distanceMap.put(node, Math.min(distanceMap.get(node), distance));
        insertHeapify(node, heapIndexMap.get(node));
      }
      if (!isEntered(node)) {
        nodes[size] = node;
        heapIndexMap.put(node, size);
        distanceMap.put(node, distance);
        insertHeapify(node, size++);
      }
    }


    public NodeRecord pop() {
      NodeRecord nodeRecord = new NodeRecord(nodes[0], distanceMap.get(nodes[0]));
      swap(0, size - 1);
      heapIndexMap.put(nodes[size - 1], -1);
      distanceMap.remove(nodes[size - 1]);
      nodes[size - 1] = null;
      heapify(0, --size);
      return nodeRecord;
    }


    private void insertHeapify(Node node, int index) {
      while (distanceMap.get(nodes[index]) < distanceMap.get(nodes[(index - 1) / 2])) {
        swap(index, (index - 1) / 2);
        index = (index - 1) / 2;
      }
    }


    private void heapify(int index, int size) {
      int left = index * 2 + 1;
      while (left < size) {
        int smallest = left + 1 < size && distanceMap.get(nodes[left + 1]) < distanceMap.get(nodes[left])
            ? left + 1
            : left;
        smallest = distanceMap.get(nodes[smallest]) < distanceMap.get(nodes[index]) ? smallest : index;
        if (smallest == index) {
          break;
        }
        swap(smallest, index);
        index = smallest;
        left = index * 2 + 1;
      }
    }


    private boolean isEntered(Node node) {
      return heapIndexMap.containsKey(node);
    }


    private boolean inHeap(Node node) {
      return isEntered(node) && heapIndexMap.get(node) != -1;
    }


    private void swap(int index1, int index2) {
      heapIndexMap.put(nodes[index1], index2);
      heapIndexMap.put(nodes[index2], index1);
      Node tmp = nodes[index1];
      nodes[index1] = nodes[index2];
      nodes[index2] = tmp;
    }
  }


  // 改进后的dijkstra算法
  // 从head出发，所有head能到达的节点，生成到达每个节点的最小路径记录并返回
  public static HashMap<Node, Integer> dijkstra2(Node head, int size) {
    NodeHeap nodeHeap = new NodeHeap(size);
    nodeHeap.addOrUpdateOrIgnore(head, 0);
    HashMap<Node, Integer> result = new HashMap<>();
    while (!nodeHeap.isEmpty()) {
      NodeRecord record = nodeHeap.pop();
      Node cur = record.node;
      int distance = record.distance;
      for (Edge edge : cur.edges) {
        nodeHeap.addOrUpdateOrIgnore(edge.to, edge.weight + distance);
      }
      result.put(cur, distance);
    }
    return result;
  }