左神算法-基础06-图
图的存储方式
-
邻接表
-
邻接矩阵
如何表达图?生成图?
//图的节点
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;
this.in = 0;
this.out = 0;
this.nexts = new ArrayList<>();
this.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<>();
}
}
//图的生成
public class GraphGenerator {
public static Graph createGraph(Integer[][] matrix) {
Graph graph = new Graph();
for (int i = 0; i < matrix.length; i++) {
Integer weight = matrix[i][0];
Integer from = matrix[i][1];
Integer 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;
}
}
图的宽度优先遍历
-
利用队列实现
-
从源节点开始依次按照宽度进队列，然后弹出
-
每弹出一个点，把该节点所有没有进过队列的邻接点放入队列
-
直到队列变空
public static void bfs(Node node) { if (node == null) { return; } Queue<Node> queue = new LinkedList<>(); HashSet<Node> map = new HashSet<>(); map.add(node); queue.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); } } } }
广度优先遍历
-
利用栈实现
-
从源节点开始把节点按照深度放入栈，然后弹出
-
每弹出一个点，把该节点下一个没有进过栈的邻接点放入栈
-
直到栈变空
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.push(cur); stack.push(next); set.add(next); System.out.println(next.value); break; } } } }
拓扑排序算法
适用范围：要求有向图，且有入度为0的节点，且没有环
public static List<Node> sortedTopology(Graph graph) {
//key: 某一个node
//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);
}
}
//拓扑排序的结果以此加入result
List<Node> 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;
}
kruskal算法
适用范围：要求无向图
//类并查集结构
public static class MySets{
public HashMap<Node, List<Node>> setMap;
public MySets(Collection<Node> nodes) {
for (Node node : nodes) {
List<Node> set = new ArrayList<Node>();
set.add(node);
setMap.put(node, 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){
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;
}
}
public static Set<Edge> kruskalMST(Graph graph) {
MySets sets = new MySets(graph.nodes.values());
PriorityQueue<Edge> priorityQueue = new PriorityQueue<>(new EdgeComparator());
for (Edge edge : graph.edges) {
priorityQueue.add(edge);
}
HashSet<Edge> result = new HashSet<>();
while(!priorityQueue.isEmpty()) {
Edge edge = priorityQueue.poll();
if (!sets.isSameSet(edge.from, edge.to)) {
result.add(edge);
sets.union(edge.from, edge.to);
}
}
return result;
}
prim算法
适用范围：要求无向图
public static class EdgeComparator implements Comparator<Edge> {
@Override
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> set = new HashSet<>();
//依次挑选的边在result里
Set<Edge> result = new HashSet<>();
for (Node node : graph.nodes.values()) {
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;
}
Dijkstra算法
适用范围：没有权值为负数的环
public static HashMap<Node, Integer> dijkstra(Node head) {
//从head出发到所有点的最小距离
//key：从head出发到达key
//value：从head出发到达key的最小距离
//如果在表中，没有T的记录，含义是从head出发到达T这个点的距离为正无穷
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> 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;
}