图

图的存储方式

  1. 邻接表
  2. 邻接矩阵

如何表达图?生成图?

自定义图

public class Graph {
	public HashMap<Integer,Node> nodes;//点集
	public HashSet<Edge> edges;//边集

	public Graph() {
		nodes = new HashMap<>();
		edges = new HashSet<>();
	}
}

Node

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;
		in = 0;
		out = 0;
		nexts = new ArrayList<>();
		edges = new ArrayList<>();
	}
}

Edge

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;
	}
}

转化图举例

N*3的矩阵 [weight,from,to]

	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;
	}

遍历

图的宽度优先遍历

  1. 利用队列实现
  2. 从源节点开始依次按照宽度进队列，然后弹出
  3. 每弹出一个点，把该节点所有没有进过队列的邻接点放入队列
  4. 直到队列变空
	public static void bfs(Node node) {
		if (node == null) {
			return;
		}
		Queue<Node> queue = new LinkedList<>();
		HashSet<Node> 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);
				}
			}
		}
	}

深度优先遍历

  1. 利用栈实现
  2. 从源节点开始把节点按照深度放入栈，然后弹出
  3. 每弹出一个点，把该节点下一个没有进过栈的邻接点放入栈
  4. 直到栈变空
	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的节点，且没有环

循环依赖问题

	// directed graph and no loop
	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);
			}
		}
		//拓扑排序的结果，依次加入
		List<Node> result = new ArrayList<>();
		while (!zeroInQueue.isEmpty()) {
			Node cur = zeroInQueue.poll();
			result.add(cur);//为0的加入result
			for (Node next : cur.nexts) {
				inMap.put(next, inMap.get(next) - 1);//每减少一个出度，将对应节点的入度减一
				if (inMap.get(next) == 0) {//同时检查这个节点是否入度为0
					zeroInQueue.add(next);
				}
			}
		}
		return result;
	}

生成最小生成树

kruskal算法

适用范围:要求无向图

图生成最小生成树：所有点联通；权值最低

思路：将权值最低的边依次加入，检查是否生成环

使用并查集来实现 快速合并、查询操作

image-20220119000601406

	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) {
			priorityQueue.add(edge);
		}
		Set<Edge> 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;
	}

	public static class EdgeComparator implements Comparator<Edge> {

		@Override
		public int compare(Edge o1, Edge o2) {
			return o1.weight - o2.weight;
		}

	}

prime算法

从一个点出发，根据解锁的权重最小的边，依次加入新点

	public static Set<Edge> primMST(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;
	}

Dijkstra算法

规定一个出发点

适用范围：可以有权值为负数的边，但是不能有累加和为负数的环[无限循环则无限小下去]

	public static HashMap<Node, Integer> dijkstra1(Node head) {
		//从head出发到所有点的最小距离
		HashMap<Node, Integer> distanceMap = new HashMap<>();
		distanceMap.put(head, 0);
		HashSet<Node> selectedNodes = new HashSet<>();//已经遍历完所有边求完距离的点 以后再也不碰
		Node minNode = getMinDistanceAndUnselectedNode(distanceMap, selectedNodes);//求一个目前weight最小的点
		while (minNode != null) {
			int distance = distanceMap.get(minNode);
			for (Edge edge : minNode.edges) {
				Node toNode = edge.to;
				if (!distanceMap.containsKey(toNode)) {//如果这个点还没存放进map里，则放进去
					distanceMap.put(toNode, distance + edge.weight);
				}
				distanceMap.put(edge.to, Math.min(distanceMap.get(toNode), distance + edge.weight));//更新这个点到head的最短距离
			}
			selectedNodes.add(minNode);//遍历完后存进set里，再也不碰
			minNode = getMinDistanceAndUnselectedNode(distanceMap, selectedNodes);//再继续取一个遍历，直至selected里面放满
		}
		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;
	}