什么是图
—
一些理论
在线性结构中，数据元素之间满足唯一的线性关系，每个数据元素(除第一个和最后一个外)只有一个直接前趋和一个直接后继；
在树形结构中，数据元素之间有着明显的层次关系，并且每个数据元素只与上一层中的一个元素(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 Setpublic 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> {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> {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(跳转点) 最小距离distanceint distance = distanceMap.get(minNode);for (Edge edge : minNode.edges) {Node toNode = edge.to;if (!distanceMap.containsKey(toNode)) {distanceMap.put(toNode, distance + edge.weight);} else { // toNodedistanceMap.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;}
本文使用 文章同步助手 同步
