图
基本概念
- 图的表示方式
（1）邻接表
（2）邻接矩阵 - 实现方法
Graph public static class Graph{ //点集（编号 + 点） public HashMap<Integer, Node> nodes; //边集 public HashSet<Edge> edges; public Graph(){ //构造函数 nodes = new HashMap<>(); edges = new HashSet<>(); } }
Node public static 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<>(); } }
Edge public static 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 static Graph createGraph(Integer[][] matrix){ //将邻接矩阵转化为邻接表 Graph graph = new Graph(); for (int i = 0; i < matrix.length; i++){ //遍历邻接矩阵 //matrix[i][0]存的是出发点 //matrix[i][1]存的是结束点 //matrix[i][2]存的是权值 Integer from = matrix[i][0]; Integer to = matrix[i][1]; Integer weight = 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; }
广度优先 bfs
- 利用队列实现
- 从源点出发依次按照广度进入队列，然后弹出
- 每弹出一个节点，把与该节点所有没有进过队列的邻接点放入队列
- 直到队列为空
注意点：要判断节点是否已经遍历过，可以给节点添加一个数据项进行记录，也可以利用HashSet或者数组进行记录
public static void bfs (Node node){ if (node == null){ return; } Queue<Node> queue = new LinkedList<>(); //防止点重复 HashSet<Node> set = new HashSet<>(); queue.add(node); set.add(node); while (!queue.isEmpty()){ Node p = queue.poll(); //bfs在出队后输出（操作） System.out.println(p.value); for (Node next : p.nexts){ //遍历与p相连的节点 if (!set.contains(next)){ //判断是否遍历过该点 set.add(next); queue.add(next); } } } }
深度优先 dfs
- 利用栈实现
- 从源点出发把节点按照深度放入栈，然后弹出
- 每弹出一个节点，就把该节点下一个没有进过栈的节点入栈
- 直到栈为空
注意点：bfs是在出队后对节点进行操作；dfs是在入栈时对节点进行操作
public static void dfs (Node node){ if (node == null){ return; } Stack<Node> stack = new Stack<>(); //防止点重复 HashSet<Node> set = new HashSet<>(); stack.push(node); set.add(node); //dfs先入栈后直接输出（操作） System.out.println(node.value); while (!stack.isEmpty()){ Node p = stack.pop(); for (Node next : p.nexts){ //遍历与p相连的节点，找到一个后直接跳出循环 if (!set.contains(next)){ //判断是否遍历过该点 //先将p重新放入栈，方便回溯 stack.push(p); //next入栈 stack.push(next); set.add(next); System.out.println(next.value); break; } } } }
拓扑排序
思路：找入度为0的节点，删去该节点以及相关联的边，重复操作，若有环存在则拓扑排序失败
方法：使用HashMap结构建立点与其对应入度边的关系，使用队列存依次储入度为0的节点，在图中删除入度为0的节点以及相关联的边，更新对应点的入度，重复操作
public static List<Node> sortedTopology(Graph graph){ //key：某一个node //value：该node的入度 // 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 ArrayList<>(); while (!zeroInQueue.isEmpty()){ //删除点 Node p = zeroInQueue.poll(); result.add(p); for (Node next : p.nexts){ //剩余点的更新 //inMap.put(next, inMap.get(next) - 1); next.in--; if (next.in == 0){ zeroInQueue.add(next); } } } return result; }
kruskal算法
- 思路：在不构成环的前提下每次选择权值最小的边，构成最小生成树
- 难点：如何判断是否有环生成？
- 解决方法：开始每个点都是一个集合，若选择了某两个点构成的边，则将这两个点组成新的集合。每次选择边使，边的两个点不能同时在一个集合中
- 具体实现：
（1）实现一个MySets类，其中使用List <>集合实现点集合；使用HashMap建立点与集合间的关系；再实现集合中查找点的方法与合并俩个集合的方法。
（2）实现一个比较器，对边的权值进行判断，使用堆排序
public static Set<Edge> kruskal(Graph graph){ //集合处理类 MySets mySets = new MySets((List<Node>) graph.nodes.values()); //比较器类，使用堆排序 PriorityQueue<Edge> priorityQueue = new PriorityQueue<>(new EdgeComparator()); for (Edge edge : graph.edges){ //将边加入堆中 priorityQueue.add(edge); } //存入结构的集合 Set<Edge> result = new HashSet<>(); while (!priorityQueue.isEmpty()){ //按照权值较小的先遍历 Edge edge = priorityQueue.poll(); if (!mySets.isSameSet(edge.from, edge.to)){ //出发点与结束点是否相同的判断 result.add(edge); //合并集合 mySets.union(edge.from, edge.to); } } return result; } public static class MySets{ //集合的处理 //建立点和所在集合的关系 public HashMap<Node, List<Node>> setMap; public MySets(List<Node> nodes){ //构造方法，将每个点放入一个集合，并建立点与集合的关系 for (Node p : nodes){ List<Node> set = new ArrayList<Node>(); set.add(p); setMap.put(p, set); } } public boolean isSameSet(Node from, Node to){ //判断边的出发点与结束点是否在同一集合中 List<Node> fromSet = setMap.get(from); List<Node> toSet = setMap.get(to); return fromSet == toSet; } public void union(Node from, Node to){ //合并集合，将toSet集合的点放入fromSet中 List<Node> fromSet = setMap.get(from); List<Node> toSet = setMap.get(to); for (Node toNode : toSet){ fromSet.add(toNode); setMap.put(toNode, fromSet); } } } public static class EdgeComparator implements Comparator<Edge>{ @Override public int compare(Edge o1, Edge o2) { return o1.weight - o2.weight; } }
Prim算法
- 思路：在不构成环的前提下，先确定一个点，选择连接该点权值最小的边，将选择的边的另一个点加入确定点的集合再次选择与确定点有关边中权值最小的
- 难点：如何判断是否有环生成？
- 解决方法：每次只有一个点加入，只需要一个确定点的集合，每次加入点前，判断是否在集合中便可
- 具体实现：
（1）使用HashSet进行确定点的存储与判断
（2）实现一个比较器，对边的权值进行判断，使用堆排序
public static Set<Edge> prim(Graph graph){ //比较器类，使用堆排序 PriorityQueue<Edge> priorityQueue = new PriorityQueue<>(new EdgeComparator()); //确定点的集合 HashSet<Node> set = new HashSet<>(); //结果的保存 Set<Edge> result = new HashSet<>(); for (Node node : graph.nodes.values()){ //随便挑选一个点，防止非连通图的出现使用for遍历 if (!set.contains(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; } public static class EdgeComparator implements Comparator<Edge>{ @Override public int compare(Edge o1, Edge o2) { return o1.weight - o2.weight; } }
Dijkstra算法
思路：在确定出发点的情况下，只使用目前确定点的边，选取确定边中权值最小的边，将结束点加入确定点的集合，再次更新确定点到不同点的权值，重复选取，加入
public static HashMap<Node, Integer> dijkstra(Node head){ //从head出发到所有点的最小距离 //返回值中key：到达的点 //value：从head到key的最短长度（权值） //如果表中没有key的记录，含义是head出发到那个点的距离是正无穷 HashMap<Node, Integer> distanceMap = new HashMap<>(); distanceMap.put(head, 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> selectedNodes){ //求最小的距离并且没有被选择过的点 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 (!selectedNodes.contains(node) && distance < minDistance){ //该点不在selectedNodes中并且距离最小 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; //堆的底层结构：数组 private HashMap<Node, Integer> headIndexMap; //查节点在堆上的位置（数组下标） private HashMap<Node, Integer> distanceMap; //node到head的最短距离 private int size; //记录堆的大小 public NodeHeap(int size){ //初始化 nodes = new Node[size]; //size参数为了申请数组空间使用 headIndexMap = new HashMap<>(); distanceMap = new HashMap<>(); this.size = 0; //堆中目前为空 } public boolean isEmpty(){ //判断为空的方法 return size == 0; } private boolean isEntered(Node node){ //判断node是否进入过堆 return headIndexMap.containsKey(node); } private boolean inHeap(Node node){ //判断node目前是否在堆上 //进入堆后又出堆的使其下标headIndexMap中的记录变成 -1 return isEntered(node) && headIndexMap.get(node)!= -1; } private void swap(int index1, int index2){ //在堆中以及headIndexMap上两节点位置的调整 headIndexMap.put(nodes[index1], index2); headIndexMap.put(nodes[index2], index1); Node temp = nodes[index1]; nodes[index1] = nodes[index2]; nodes[index2] = temp; } 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; } } public void addOrUpdateOrIgnore(Node node, int distance){ //加入节点后的更新操作 if (inHeap(node)){ //如果node在堆上 distanceMap.put(node, Math.min(distance, distanceMap.get(node))); //distance的更新 insertHeapify(node, headIndexMap.get(node)); //更新后距离可能变小，上移操作 } if (!isEntered(node)){ //如果节点没有进入过堆 //新建记录 nodes[size] = node; headIndexMap.put(node, size); distanceMap.put(node, distance); insertHeapify(node, size); size++; } //进入过堆，但现在不在堆上，说明长度以及确定无需操作 } public NodeRecord pop(){ //堆的弹出方法 //将堆顶元素按照NodeRecord类封装返回 NodeRecord nodeRecord = new NodeRecord(nodes[0], distanceMap.get(nodes[0])); //堆的更新 headIndexMap.put(nodes[0], -1); //进入堆后又出堆的使其下标headIndexMap中的记录变成 -1 distanceMap.remove(nodes[0]); //在distanceMap中删除记录 swap(0, size - 1); //堆顶与最后一个元素交换 nodes[size - 1] = null; //空间释放 heapify(0, --size); //下移过程重新使堆平衡 return nodeRecord; } } public static HashMap<Node, Integer> dijkstra(Node head, int size){ //从head出发，生成到达每个节点的最小路径记录 //自定义堆 NodeHeap nodeHeap = new NodeHeap(size); nodeHeap.addOrUpdateOrIgnore(head, 0); HashMap<Node, Integer> result = new HashMap<>(); while (!nodeHeap.isEmpty()){ //遍历当前可到达节点 //NodeRecord 节点 + 距离类 NodeRecord record = nodeHeap.pop(); //堆顶 Node p = record.node; int distance = record.distance; for (Edge edge : p.edges){ //边的更新 nodeHeap.addOrUpdateOrIgnore(edge.to, edge.weight + distance); } result.put(p, distance); } return result; }
