用php做的网站论文bing搜索引擎入口
图
- 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 looppublic 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>{@Overridepublic int compare(Edge o1, Edge o2) {// TODO Auto-generated method stubreturn 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>{@Overridepublic int compare(Edge o1, Edge o2) {// TODO Auto-generated method stubreturn 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;}
}