什么是圖

—

一些理論

• 在線性結(jié)構(gòu)中，數(shù)據(jù)元素之間滿足唯一的線性關(guān)系，每個數(shù)據(jù)元素(除第一個和最后一個外)只有一個直接前趨和一個直接后繼；

• 在樹形結(jié)構(gòu)中，數(shù)據(jù)元素之間有著明顯的層次關(guān)系，并且每個數(shù)據(jù)元素只與上一層中的一個元素(parent node)及下一層的多個元素(孩子節(jié)點(diǎn))相關(guān)；

• 在圖形結(jié)構(gòu)中，節(jié)點(diǎn)之間的關(guān)系是任意的，圖中任意兩個數(shù)據(jù)元素之間都有可能相關(guān)。

圖G由兩個集合V(頂點(diǎn))和E(邊)組成，定義為G=(V，E)。

圖的分類

—

無向圖

有向圖

無權(quán)圖

????連接線上沒有數(shù)值的圖可以認(rèn)為是無權(quán)圖

有權(quán)圖

其實所有的圖都可以認(rèn)為是有向圖，無向圖可以看為是兩個方向的有向圖

度

無向圖

節(jié)點(diǎn)V的度是3

有向圖分為入度和出度。

V的入度2，出度1。

對應(yīng)現(xiàn)實生活中圖的系統(tǒng)建模

—

比如對交通流量建模，頂點(diǎn)可以表示街道的十字路口，邊表示街道。加權(quán)的邊可以表示限速或者車道的數(shù)量。建模人員可以用這個系統(tǒng)來判斷最佳路線及最有可能堵車的街道。

任何運(yùn)輸系統(tǒng)都可以用圖來建模。比如，航空公司可以用圖來為其飛行系統(tǒng)建模。將每個機(jī)場看成頂點(diǎn)，將經(jīng)過兩個頂點(diǎn)的每條航線看作一條邊。加權(quán)的邊可以看作從一個機(jī)場到另一個機(jī)場的航班成本，或兩個機(jī)場之間的距離，這取決與建模的對象是什么。

包含局域網(wǎng)和廣域網(wǎng)（如互聯(lián)網(wǎng)）在內(nèi)的計算機(jī)網(wǎng)絡(luò)，同樣經(jīng)常用圖來建模。

可以用圖來建模的實現(xiàn)系統(tǒng)是消費(fèi)市場，頂點(diǎn)可以用來表示供應(yīng)商和消費(fèi)者。

還有比如朋友圈，朋友的互相關(guān)系。

圖在內(nèi)存中的實現(xiàn)

—

概要

• 節(jié)點(diǎn)(Vertex)?與?邊（Edge）

• 圖的表示：?鄰接表?和?鄰接矩陣（平時工作的很少這樣表示）

• 鄰接表的表示

• 鄰接矩陣

• 這里可以分為?有向圖?和無向圖
  無向圖是一種特殊的有向圖

• 有權(quán)圖?和?無權(quán)圖

圖的遍歷

對節(jié)點(diǎn)表示

public class Node {    public int value;    public int in; //入度    public int out; //出度    public ArrayList<Node> nexts; //相鄰節(jié)點(diǎn)    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;//權(quán)重    public Node from; //開始節(jié)點(diǎn)    public Node to; // 結(jié)束節(jié)點(diǎn)    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; // 所有的點(diǎn)    public HashSet<Edge> edges; // 所有的邊    public Graph() {        nodes = new HashMap<>();        edges = new HashSet<>();    }}

廣度優(yōu)先遍歷（BFS）

public?class?GraphBFS?{    // 從node 出發(fā)，進(jìn)行廣度    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);                }            }        }    }

深度優(yōu)先遍歷(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:從點(diǎn)開始找到最小的那棵樹

• Prim:邊開始找最小的那棵樹

• Dijkstra:指定一個節(jié)點(diǎn)，計算 這個節(jié)點(diǎn)到其他節(jié)點(diǎn)的最短路徑，有點(diǎn)類似全局最優(yōu)解

代碼

kruska 解法

// Union-Find Set  public static class UnionFind {    // key 某一個節(jié)點(diǎn)， value key節(jié)點(diǎn)往上的節(jié)點(diǎn)    private HashMap<Node, Node> fatherMap;    // key 某一個集合的代表節(jié)點(diǎn), value key所在集合的節(jié)點(diǎn)個數(shù)    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) {    // 解鎖的邊進(jìn)入小根堆    PriorityQueue<Edge> priorityQueue = new PriorityQueue<>(new EdgeComparator());    // 哪些點(diǎn)被解鎖出來了    HashSet<Node> nodeSet = new HashSet<>();                Set<Edge> result = new HashSet<>(); // 依次挑選的的邊在result里    for (Node node : graph.nodes.values()) { // 隨便挑了一個點(diǎn)      // node 是開始點(diǎn)      if (!nodeSet.contains(node)) {        nodeSet.add(node);        for (Edge edge : node.edges) { // 由一個點(diǎn)，解鎖所有相連的邊          priorityQueue.add(edge);        }        while (!priorityQueue.isEmpty()) {          Edge edge = priorityQueue.poll(); // 彈出解鎖的邊中，最小的邊          Node toNode = edge.to; // 可能的一個新的點(diǎn)          if (!nodeSet.contains(toNode)) { // 不含有的時候，就是新的點(diǎn)            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);        // 打過對號的點(diǎn)        HashSet<Node> selectedNodes = new HashSet<>();        Node minNode = getMinDistanceAndUnselectedNode(distanceMap, selectedNodes);        while (minNode != null) {            //  原始點(diǎn)  ->  minNode(跳轉(zhuǎn)點(diǎn))   最小距離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?自定義堆優(yōu)化解法

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; // 實際的堆結(jié)構(gòu)    // key 某一個node， value 上面堆中的位置    private HashMap<Node, Integer> heapIndexMap;    // key 某一個節(jié)點(diǎn)， value 從源節(jié)點(diǎn)出發(fā)到該節(jié)點(diǎn)的目前最小距離    private HashMap<Node, Integer> distanceMap;    private int size; // 堆上有多少個點(diǎn)    public NodeHeap(int size) {      nodes = new Node[size];      heapIndexMap = new HashMap<>();      distanceMap = new HashMap<>();      size = 0;    }    public boolean isEmpty() {      return size == 0;    }    // 有一個點(diǎn)叫node，現(xiàn)在發(fā)現(xiàn)了一個從源節(jié)點(diǎn)出發(fā)到達(dá)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;    }  }  // 改進(jìn)后的dijkstra算法  // 從head出發(fā)，所有head能到達(dá)的節(jié)點(diǎn)，生成到達(dá)每個節(jié)點(diǎn)的最小路徑記錄并返回  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;  }

本文使用 文章同步助手 同步