欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

图算法总结一

程序员文章站 2022-05-21 16:14:19
...

图算法总结一

图算法用到的节点、边、图以及图的生成类:
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.out++;
			fromNode.nexts.add(toNode);
			fromNode.edges.add(newEdge);
			toNode.in++;
			graph.edges.add(newEdge);
		}
		return graph;
	}
}

深度优先遍历

1,利用栈实现
2,从源节点开始把节点按照深度放入栈,然后弹出
3,每弹出一个点,把该节点下一个没有进过栈的邻接点放入栈
4,直到栈变空

public class 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.push(next);
					stack.push(cur);
					set.add(next);
					System.out.println(next.value);
					break;
				}
			}
		}
	}
}

宽度优先遍历

1,利用队列实现
2,从源节点开始依次按照宽度进队列,然后弹出
3,每弹出一个点,把该节点所有没有进过队列的邻接点放入队

4,直到队列变空

public class BFS {
	public static void bfs(Node node) {
		if (node == null) {
			return;
		}
		Queue<Node> queue = new LinkedList<Node>();
		HashSet<Node> set = new HashSet<Node>();
		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)) {
					queue.add(next);
					set.add(next);
				}
			}
		}
	}
}

最小生成树-Prim算法

Prim算法的核心步骤是:在带权连通图中,从图中某一顶点v开始,此时集合U={v},重复执行下述操作:在所有u∈U,w∈V-U的边(u,w)∈E中找到一条权值最小的边,将(u,w)这条边加入到已找到边的集合,并且将点w加入到集合U中,当U=V时,就找到了这颗最小生成树。

public class 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> prim(Graph graph) {
		PriorityQueue<Edge> queue = new PriorityQueue<>(new EdgeComparator());
		HashSet<Node> set = new HashSet<>();
		Set<Edge> result = new HashSet<Edge>();
		for (Node nodes : graph.nodes.values()) {
			if (!set.contains(nodes)) {
				set.add(nodes);
				for (Edge edge : nodes.edges) {
					queue.add(edge);
				}
				while (!queue.isEmpty()) {
					Edge edge = queue.poll();
					Node toNode = edge.to;
					if (!set.contains(toNode)) {
						set.add(toNode);
						result.add(edge);
						for (Edge nextEdge : toNode.edges) {
							queue.add(nextEdge);
						}
					}
				}
			}
		}
		return result;

	}
}
最小生成树-Kruskal算法

Kruskal算法的执行步骤:

假设 G=(V,{E}) 是一个含有 n 个顶点的连通网,则按照克鲁斯卡尔算法构造最小生成树过程为:先构造一个只含 n 个顶点,而边集为空的子图,若将该子图中各个顶点看成是各棵树上的根结点,则它是一个含有 n 棵树的一个森林。之后,从网的边集 E 中选取一条权值最小的边,若该条边的两个顶点分属不同的树,则将其加入子图,也就是说,将这两个顶点分别所在的两棵树合成一棵树;反之,若该条边的两个顶点已落在同一棵树上,则不可取,而应该取下一条权值最小的边再试之。依次类推,直至森林中只有一棵树,也即子图中含有 n-1条边为止。

public class Kruskal {
	public static class UnionFindSet {

		public HashMap<Node, Node> fatherMap;
		public HashMap<Node, Integer> sizeMap;

		public UnionFindSet() {
			fatherMap = new HashMap<>();
			sizeMap = new HashMap<>();
		}

		public void makeSets(Collection<Node> nodes) {
			fatherMap.clear();
			sizeMap.clear();
			for (Node node : nodes) {
				fatherMap.put(node, node);
				sizeMap.put(node, 1);
			}
		}

		public Node findHead(Node node) {
			if (node == null) {
				return null;
			}
			Node father = fatherMap.get(node);
			while (father != node) {
				father = findHead(father);
			}
			fatherMap.put(node, father);
			return father;
		}

		public boolean isSameSet(Node a, Node b) {
			return findHead(a) == findHead(b);
		}

		public void union(Node a, Node b) {
			if (a == null || b == null) {
				return;
			}
			Node aHead = fatherMap.get(a);
			Node bHead = fatherMap.get(b);
			if (aHead != bHead) {
				int aSetSize = sizeMap.get(aHead);
				int bSetSize = sizeMap.get(bHead);
				if (aSetSize <= bSetSize) {
					fatherMap.put(aHead, bHead);
					sizeMap.put(bHead, aSetSize + bSetSize);
				} else {
					fatherMap.put(bHead, aHead);
					sizeMap.put(aHead, aSetSize + bSetSize);
				}
			}
		}
	}

	public static class EdgeComparator implements Comparator<Edge> {
		@Override
		public int compare(Edge o1, Edge o2) {
			return o1.weight - o2.weight;
		}

	}

	public static Set<Edge> kruskal(Graph graph) {
		UnionFindSet union = new UnionFindSet();
		union.makeSets(graph.nodes.values());
		PriorityQueue<Edge> priorityQueue = new PriorityQueue<>(new EdgeComparator());
		Set<Edge> result = new HashSet<>();
		for (Edge edge : graph.edges) {
			priorityQueue.add(edge);
		}
		while (!priorityQueue.isEmpty()) {
			Edge edge = priorityQueue.poll();
			if (!union.isSameSet(edge.from, edge.to)) {
				result.add(edge);
				union.union(edge.from, edge.to);
			}
		}
		return result;

	}
}

拓扑排序

由AOV网构造拓扑序列的拓扑排序算法主要是循环执行以下两步,直到不存在入度为0的顶点为止。

(1) 选择一个入度为0的顶点并输出之;

(2) 从网中删除此顶点及所有出边;

循环结束后,若输出的顶点数小于网中的顶点数,则输出“有回路”信息,否则输出的顶点序列就是一种拓扑序列。

public class TopologySort {
	public static List<Node> topologySort(Graph graph) {
		HashMap<Node, Integer> map = new HashMap<>();
		Queue<Node> zeroInNodeQ = new LinkedList<Node>();
		for (Node node : graph.nodes.values()) {
			map.put(node, node.in);
			if (node.in == 0) {
				zeroInNodeQ.add(node);
			}
		}
		List<Node> result = new ArrayList<>();
		while (!zeroInNodeQ.isEmpty()) {
			Node cur = zeroInNodeQ.poll();
			result.add(cur);
			for (Node next : cur.nexts) {
				map.put(next, map.get(next) - 1);
				if (map.get(next) == 0) {
					zeroInNodeQ.add(next);
				}
			}
		}
		return result;
	}
}