图
- 1)由点的集合和边的集合构成
- 2)虽然存在有向图和无向图的概念，但实际上都可以用有向图来表达
- 3)边上可能带有权值
图结构的表达
- 1)邻接表法
- 2)邻接矩阵法
- 3)除此之外还有其他众多的方式
图的面试题如何搞定
- 1图的算法都不算难，只不过coding 的代价比较高
- 2)先用自己最熟练的方式，实现图结构的表达
- 3)在自己熟悉的结构上，实现所有常用的图算法作为模板
- 4)把面试题提供的图结构转化为自己熟悉的图结构，再调用模板或改写即可
用代码实现图(点–>边–>图)
package com.harrison.class11; import java.util.ArrayList; // 点结构的描述 public class Node { public int value;// 编号 public int in;// 入度 进到我这个点的边的数量 public int out;// 出度 从我这个点出去的边的数量 public ArrayList<Node> nexts;// 直接邻居 只算出度 public ArrayList<Edge> edges;// 边 从我这个点出发有几条边组成的边的数据结构 放在edges里面 public Node(int value) { this.value=value; in=0; out=0; nexts=new ArrayList<>(); edges=new ArrayList<>(); } }
package com.harrison.class11; 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; } }
package com.harrison.class11; import java.util.HashMap; import java.util.HashSet; public class Graph { public HashMap<Integer,Node> nodes;// key是编号，value是实现的点 public HashSet<Edge> edges; public Graph() { nodes=new HashMap<>(); edges=new HashSet<>(); } }
package com.harrison.class11; public class GrahpGenerator { // 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]; 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; } }
图的宽度优先&深度优先遍历
宽度优先遍历
- 1）利用队列实现
- 2）从源节点开始依次按照宽度进队列，然后弹出
- 3）每弹出一个点，把该节点所有没有进过队列的邻接点放入队列
- 4）直到队列变空
package com.harrison.class11; import java.util.HashSet; import java.util.LinkedList; import java.util.Queue; public class Code01_BFS { // 从node出发，进行宽度优先遍历，只需要用到点结构 public static void bfs(Node node) { if(node==null) { return; } Queue<Node> queue=new LinkedList<>(); // 在二叉树进行宽度优先遍历时不会形成环 // 因为图会形成环，所有必须有个set来确保每个结点只进一次队列 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); } } } } }
深度优先遍历
- 1）利用栈实现
- 2）从源节点开始把节点按照深度放入栈，然后弹出
- 3）每弹出一个点，把该节点下一个没有进过栈的邻接点放入栈
- 4）直到栈变空
package com.harrison.class11; import java.util.HashSet; import java.util.Stack; public class Code02_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)) { stack.add(cur); stack.add(next); set.add(next); System.out.println(next.value); break; } } } } }
图的拓扑排序算法
一定是有向无环图
- 1)在图中找到所有入度为0的点输出
- 2)把所有入度为0的点在图中删掉，继续找入度为0的点输出，周而复始
- 3)图的所有点都被删除后，依次输出的顺序就是拓扑排序
- 要求:有向图且其中没有环
- 应用:事件安排、编译顺序
package com.harrison.class11; import java.util.HashMap; import java.util.LinkedList; import java.util.List; import java.util.Queue; public class Code03_TopologySort { // 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<>(); for(Node node: graph.nodes.values()) { inMap.put(node, node.in); if(node.in==0) { zeroInQueue.add(node); } } List<Node> result=new LinkedList<>(); 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
不能破环连通性
- 1)总是从权值最小的边开始考虑，依次考察权值依次变大的边
- 2)当前的边要么进入最小生成树的集合，要么丢弃
- 3)如果当前的边进入最小生成树的集合中不会形成环，就要当前边,
- 4)如果当前的边进入最小生成树的集合中会形成环，就不要当前边
- 5)考察完所有边之后，最小生成树的集合也得到了
package com.harrison.class11; import java.util.Collection; import java.util.Comparator; import java.util.HashMap; import java.util.HashSet; import java.util.PriorityQueue; import java.util.Set; import java.util.Stack; public class Code04_Kruskal { // Union-Find set 并查集 public static class UnionFind{ // key 某一个结点 value key结点往上的结点 public HashMap<Node, Node> fatherMap; // key 某一个集合的代表结点 value key所在集合的结点个数 public 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); } } public Node findFather(Node n) { Stack<Node> path = new Stack<>(); while (n != fatherMap.get(n)) { path.push(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) { Node aDai = findFather(a); Node bDai = findFather(b); if (aDai != bDai) { int aSetSize = sizeMap.get(aDai); int bSetSize = sizeMap.get(bDai); Node big = aSetSize >= bSetSize ? aDai : bDai; Node small = big == aDai ? bDai : aDai; fatherMap.put(small, big); sizeMap.put(big, aSetSize + bSetSize); sizeMap.remove(small); } } } // 将所有的边按 边的权值大小 从小到大排序 public static class EdgeComparator implements Comparator<Edge>{ @Override public int compare(Edge o1, Edge o2) { // TODO Auto-generated method stub 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
- 1）随便选一个结点解锁，相邻的边也全部解锁，然后选一条权值最小的边
- 2）新解锁的边两侧有新结点，则把新节点给解锁，并把新解锁的边考虑在最小生成树里面；新解锁的边两侧没有新结点，则不将新解锁的边考虑在最小生成树里面
- 3）新解锁的结点所有相邻的边被解锁，已经被考虑在最小生成树里的边不重复解锁，然后在所有相邻的边里选择一条权值最小的边，重复步骤 2）周而复始，一直到把所有的点都解锁完
package com.harrison.class11; import java.util.Comparator; import java.util.HashSet; import java.util.PriorityQueue; import java.util.Set; // undirected graph only public class Code05_Prim { public static class EdgeComparator implements Comparator<Edge>{ @Override public int compare(Edge o1, Edge o2) { // TODO Auto-generated method stub return o1.weight-o2.weight; } } public static Set<Edge> primMST(Graph graph){ // 被解锁的边进入小根堆 PriorityQueue<Edge> priorityQueue=new PriorityQueue<>(new EdgeComparator()); // 哪些点被解锁出来了 HashSet<Node> nodeSet=new HashSet<>(); // 已经考虑的边不要重复考虑 HashSet<Edge> edgeSet=new HashSet<>(); // 依次挑选的边放在result里面 Set<Edge> result=new HashSet<>(); // 随便挑选一个点 for循环只是为了防止森林，但一般不会出现无向图的森林 // 所以for循环也可以不要 for(Node node:graph.nodes.values()) { // node是开始点 if(!nodeSet.contains(node)) { nodeSet.add(node); // 由一个点解锁所有相邻的边 for(Edge edge:node.edges) { if(!edgeSet.contains(edge)) { edgeSet.add(edge); 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) { // 依次解锁相邻的边 if(!edgeSet.contains(nextEdge)) { edgeSet.add(nextEdge); priorityQueue.add(nextEdge); } } } } } break; } return result; } }
Dijkstra
给你一个出发点，求出发点到所有结点的最短距离是多少？如果无法到达某个点，则到这个点的距离是正无穷（一般出现在有向图里面）。
不能有权值为负数的边！！！
package com.harrison.class11; import java.util.HashMap; import java.util.HashSet; import java.util.Map.Entry; // no negative weight public class Code06_Dijkstra { public static HashMap<Node, Integer> dijkstra1(Node from) { /** * from 从from点出发到所有点的最小距离 key：从from出发到达key value：从from出发到达key的最小距离 * 如果在表中，没有T的记录，则代表从from点出发到达T这个点的距离为正无穷 */ HashMap<Node, Integer> distanceMap = new HashMap<>(); distanceMap.put(from, 0); // 已经求过距离的结点，存在selectedNodes中，以后再也不碰 HashSet<Node> selectedNodes = new HashSet<>(); Node minNode = getMinDistanceAndUnselectedNode(distanceMap, selectedNodes); while (minNode != null) { 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 { 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 (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; } 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]); // free C++同学还要把原本堆顶节点析构，对java同学不必 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; } }
