| 左神一周刷爆LeetCode 6 图 | 您所在的位置：网站首页 › 左程云leetcode题单 › 左神一周刷爆LeetCode 6 图 |
左神一周刷爆LeetCode 6 图
|
左神一周刷爆LeetCode
【一周刷爆LeetCode，算法大神左神（左程云）耗时100天打造算法与数据结构基础到高级全家桶教程，直击BTAJ等一线大厂必问算法面试题真题详解】
以点集作为单位，每一个点的直接邻居写在后面。【间接邻居不管】 同样可以表示边有权值的图。 6.1.2 邻接矩阵行列都是同样的点集。 到自己距离为0不直接相邻距离为∞ 6.1.3 如何表达图？生成图？ 表达图Java代码： package class06; import java.util.HashMap; import java.util.HashSet; public class Graph { public HashMap nodes; // Integer编号, Node具体的点 public HashSet edges; // 边 public Graph() { nodes = new HashMap(); edges = new HashSet(); } }图类，由点集和边集构成 package class06; import java.util.ArrayList; public class Node { public int value; // 点上的值【0号节点放个0，a 点放个a 这种】 public int in; // 入度【别人进到自己这个节点的边数】 public int out; // 出度【从自己出去的边数】 public ArrayList nexts; // 从当前自己出发，直接发散出去的邻居点 public ArrayList edges; // 属于当前点的边【出度的边】 public Node(int value) { this.value = value; in = 0; out = 0; nexts = new ArrayList(); edges = new ArrayList(); } }点类 package class06; 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; } }边类 生成图Java代码实现 package class06; public class GraphGenerator { public static Graph createGraph(Integer[][] matrix) { // 给的数据为二维数组 Graph graph = new Graph(); for (int i = 0; i // 第一次遇到某点 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); // 在from 的邻居中加上to fromNode.out++; // from 的出度 + 1 toNode.in++; // to 的入度 + 1 fromNode.edges.add(newEdge); // from点拥有的边加上这个新边 graph.edges.add(newEdge); //图的边集也加上这个新边 } return graph; } } 6.2 图的宽度优先遍历和深度优先遍历 6.2.1 宽度优先BFS 利用队列实现从源节点开始依次按照宽度进队列，然后弹出每弹出一个点，把该节点所有没有进过队列的邻接点放入队列直到队列变空Java实现代码：【一个队列就行了】 // 从一个点node 出发就够了 public static void bfs(Node node) { if (node == null) { return; } Queue queue = new LinkedList(); HashSet map = new HashSet(); // 保证点不重复进队列 queue.add(node); map.add(node); while (!queue.isEmpty()) { Node cur = queue.poll(); // 从队列弹出队头打印 System.out.println(cur.value); for (Node next : cur.nexts) { if (!map.contains(next)) { map.add(next); queue.add(next); } } } } 6.2.2 深度优先DFS 利用栈实现从源节点开始把节点按照深度放入栈，然后弹出每弹出一个点，把该节点下一个没有进过栈的邻接点放入栈直到栈变空Java实现代码： public static void dfs(Node node) { if (node == null) { return; } Stack stack = new Stack(); HashSet 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.push(cur); stack.push(next); set.add(next); System.out.println(next.value); break; } } } } 6.3 拓扑排序算法适用范围：要求有向图，且有入度为0的节点，且没有环 Java代码实现 // directed graph and no loop public static List sortedTopology(Graph graph) { // 一张图进行拓扑排序 HashMap inMap = new HashMap(); // Node：某一个Node，Integer：该Node 剩余的入度 Queue zeroInQueue = new LinkedList(); // 入度为0的点，才能进这个队列 for (Node node : graph.nodes.values()) { // 初始化并且找到了这张图中第一批入度为0的点 inMap.put(node, node.in); if (node.in == 0) { zeroInQueue.add(node); } } List result = new ArrayList(); 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; }大白话，给你一张有向图，怎么确定做事情的顺序能够让所有的点的依赖环境都具备，这就是拓扑排序。 更白的白话，我们安排做项目，做这个工程它依赖前面已经做好的工作才能继续开始工作，这就要我们一定要分出哪些工作是一开始就要做的，做完之后下面要做什么 → 经典拓扑排序问题。 在算法中，就是每次拿出入度为0的点，然后将其点和影响的边都干掉，接着弄下一个入度为0 的点，这就是拓扑排序。 6.4 kruskal算法适用范围：要求无向图【作用：和prim 算法一样，用于生成最小生成树】 最小生成树：在保证整体连通性的前提下，在所有方案中所有边的权值和最小。 K算法Java代码实现：【以边的角度出发，依次选择最小的边，看一件事情，我把这个边加上，有没有形成环，如果没环，就加上，如果搞出环了，就不要这条边】 唯一的谜团：在考察某边的时候，如何知道会不会形成环？【集合查询、集合合并 → 并查集，但是这里左神搞了 一个简单版本实现】 public static class MySets { public HashMap setMap; public MySets(List nodes) { // 初始化的时候，每一个点对应的集合都只有自己 for (Node cur : nodes) { List set = new ArrayList(); set.add(cur); setMap.put(cur, set); } } // 对外提供接口 public boolean isSameSet(Node from, Node to) { // 用户关心的是来去的点在不在同一个集合中 List fromSet = setMap.get(from); List toSet = setMap.get(to); return fromSet == toSet; } public void union(Node from, Node to) { // 将from 集合和 to 集合合并为一个 List fromSet = setMap.get(from); List toSet = setMap.get(to); for (Node toNode : toSet) { fromSet.add(toNode); setMap.put(toNode, fromSet); } } }功能是实现了，但是它没有真正的并查集快【报名左神的课，吃透并查集】 K算法的Java代码实现： public static class EdgeComparator implements Comparator { @Override public int compare(Edge o1, Edge o2) { return o1.weight - o2.weight; } } public static Set kruskalMST(Graph graph) { UnionFind unionFind = new UnionFind(); // 生成一个并查集结构 unionFind.makeSets(graph.nodes.values()); // 初始化 PriorityQueue priorityQueue = new PriorityQueue(new EdgeComparator()); for (Edge edge : graph.edges) { priorityQueue.add(edge); } Set result = new HashSet(); while (!priorityQueue.isEmpty()) { Edge edge = priorityQueue.poll(); if (!unionFind.isSameSet(edge.from, edge.to)) { // 判断来去是否在同一个集合中【O(1)】 result.add(edge); unionFind.union(edge.from, edge.to); // 合并 } } return result; }其实左神老师也给出了真正并查集的实现，代码如下 // Union-Find Set public static class UnionFind { private HashMap fatherMap; private HashMap rankMap; public UnionFind() { fatherMap = new HashMap(); rankMap = new HashMap(); } private Node findFather(Node n) { Node father = fatherMap.get(n); if (father != n) { father = findFather(father); } fatherMap.put(n, father); return father; } public void makeSets(Collection nodes) { fatherMap.clear(); rankMap.clear(); for (Node node : nodes) { fatherMap.put(node, node); rankMap.put(node, 1); } } 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 aFather = findFather(a); Node bFather = findFather(b); if (aFather != bFather) { int aFrank = rankMap.get(aFather); int bFrank = rankMap.get(bFather); if (aFrank fatherMap.put(bFather, aFather); rankMap.put(aFather, aFrank + bFrank); } } } } public static class EdgeComparator implements Comparator { // 自定义比较器 @Override public int compare(Edge o1, Edge o2) { return o1.weight - o2.weight; } } public static Set kruskalMST(Graph graph) { UnionFind unionFind = new UnionFind(); unionFind.makeSets(graph.nodes.values()); PriorityQueue priorityQueue = new PriorityQueue(new EdgeComparator()); for (Edge edge : graph.edges) { priorityQueue.add(edge); } Set result = new HashSet(); while (!priorityQueue.isEmpty()) { Edge edge = priorityQueue.poll(); if (!unionFind.isSameSet(edge.from, edge.to)) { result.add(edge); unionFind.union(edge.from, edge.to); } } return result; } 6.5 prim算法适用范围：要求无向图【从点的角度】 思路：从某点开始，依次“解锁”边， 每次都挑最小权值的，且不重复操作。【一个一个点的加到集合，用一个哈希表就可以实现了，用不上集合的合并等操作】 Java实现代码： public static class EdgeComparator implements Comparator { // 自定义比较器 @Override public int compare(Edge o1, Edge o2) { return o1.weight - o2.weight; } } public static Set primMST(Graph graph) { // 解锁的边进入小根堆 PriorityQueue priorityQueue = new PriorityQueue( new EdgeComparator()); HashSet set = new HashSet(); Set result = new HashSet(); // 依次挑选的边放在result中 for (Node node : graph.nodes.values()) { // 随便挑一个点【其实是处理森林问题】 if (!set.contains(node)) { // Node 是起始点 set.add(node); for (Edge edge : node.edges) { // 由一个点，解锁所有相连的边 priorityQueue.add(edge); } while (!priorityQueue.isEmpty()) { Edge edge = priorityQueue.poll(); // 弹出解锁的边中，最小的边 Node toNode = edge.to; // 可能的一个新的点 if (!set.contains(toNode)) { // 集合中不含有，就是新的点 set.add(toNode); result.add(edge); for (Edge nextEdge : toNode.edges) { priorityQueue.add(nextEdge); // 就算有可能出现一条边被重复处理的情况，但是不影响我们拿在集合中的那个对应边的结果，会直接跳过的 } } } } } return result; } // 请保证graph是连通图 // graph[i][j]表示点i到点j的距离，如果是系统最大值代表无路 // 返回值是最小连通图的路径之和 public static int prim(int[][] graph) { int size = graph.length; int[] distances = new int[size]; boolean[] visit = new boolean[size]; visit[0] = true; for (int i = 0; i int minPath = Integer.MAX_VALUE; int minIndex = -1; for (int j = 0; j minPath = distances[j]; minIndex = j; } } if (minIndex == -1) { return sum; } visit[minIndex] = true; sum += minPath; for (int j = 0; j distances[j] = graph[minIndex][j]; } } } return sum; } 6.6 Dijkstra算法【经典】 6.6.1 经典实现适用范围：没有权值为负数的边【求单源最短路径】 Java代码实现： public static HashMap dijkstra1(Node head) { // 从head 出发到所有点的最小距离 HashMap distanceMap = new HashMap(); //Node: 从head 到Node | Integer: 从head 出发到达Node 的最小距离【如果在表中，没有T的记录，含义是从head 出发到T 这个点的距离为正无穷】 distanceMap.put(head, 0); // head 到自己距离为0 // 已经求过距离的点，放入selectedNodes中，以后再也不碰 HashSet 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); } 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 distanceMap, HashSet touchedNodes) { Node minNode = null; int minDistance = Integer.MAX_VALUE; for (Entry entry : distanceMap.entrySet()) { Node node = entry.getKey(); int distance = entry.getValue(); if (!touchedNodes.contains(node) && distance 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; private HashMap heapIndexMap; private HashMap distanceMap; private int size; public NodeHeap(int size) { nodes = new Node[size]; heapIndexMap = new HashMap(); distanceMap = new HashMap(); this.size = 0; } public boolean isEmpty() { return size == 0; } 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]) int left = index * 2 + 1; while (left 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; } } public static HashMap dijkstra2(Node head, int size) { NodeHeap nodeHeap = new NodeHeap(size); nodeHeap.addOrUpdateOrIgnore(head, 0); HashMap 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; } |
【本文地址】
公司简介
联系我们