图的表示方式
图是由一系列点和边的集合构成的，一般有邻接矩阵和邻接表两种表示方式，c/c++可以看我的这篇文章：搜索(1)
这篇文章主要讲java语言中图的相关算法。首先看一下图结构的代码：
class Node {//点集
public int value;
public int in;//入度
public int out;//出度
public ArrayList<Node> nexts;//邻居结点(以我为from的情况下)
public ArrayList<Edge> edges;//从我出发发散出的边集合
public Node(int value) {
this.value = value;
in = 0;
out = 0;
nexts = new ArrayList<>();
edges = new ArrayList<>();
}
}
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;
}
}
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) {
/* matrix = {
* {weight,from,to}
* {weight,from,to}
* ...
* ...
* }
*/
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;
}
}一般来说，图的题目都会给这样的输入，一个n行3列的二维矩阵，每行都代表一个输入，第一列代表边的权重，第二列代表起始点，第三列代表终止点，比方说[2,1,2]就表示从1结点出发到2结点连一条边，该边权重为2
BFS——广度优先搜索
广搜一般由队列完成，广搜的顺序与子节点到初始节点的距离有关，离初始节点越近的子节点会更早被访问
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 cur = queue.poll();
System.out.println(cur.value);
for(Node next:cur.nexts) {
if(!set.contains(next)) {
set.add(next);
queue.add(next);
}
}
}
}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.isEmpty()) {
stack.push(cur);
stack.push(next);
set.add(next);
System.out.println(next.value);
break;
}
}
}
}图的拓扑排序
图的拓扑排序以下图来举例，假设你要学课程A，但是课程A有先导课，必须上完先导课才能上A，因此你必须先上BCD，但是由于BD也有先导课K，所以必须先上K。那么正确的上课顺序就该是KC、BD、A，至于究竟是先上K还是先上C，这个顺序无所谓
说一下拓扑排序的算法流程：找到入度为0的结点，打印，然后删掉该结点，直到图中结点为空
//dirceted graph and no loop
public static List<Node> sortedTopology(Graph graph) {
HashMap<Node,Integer> inMap = new HashMap<>();
Queue<Node> zeroInQueue = new LinkedList<>();
for(Node node : graph.nodes.values()) {//遍历所有的点
inMap.put(node,node.in);//把每个点以及入度登记在inMap里
if(node.in == 0)
zeroInQueue.add(node);//入度为0的点进队
}
List<Node> res = new ArrayList<>();
while(!zeroInQueue.isEmpty()) {
Node cur = zeroInQueue.poll();//从入度为0的点的队列中拿出一个
res.add(cur);
for(Node next : cur.nexts) {//遍历这个结点的所有子结点
inMap.put(next,inMap.get(next) - 1);//子结点的入度减1，相当于删除from点
if(inMap.get(next) == 0)
zeroInQueue.add(next);
}
}
return res;
}图的最小生成树
图的最小生成树算法用于无向图，只选择图中的某些边，达到整体边的权重加起来是最小的，并且各个点之间是连通的，连通的意思是假设[1,2]之间有条边，[2,3]之间有条边，那么[1,3]之间就是连通的，图的最小生成树算法有两个，分别是K算法和P算法，他俩产生的结果都是一样的，只不过决策的过程不一样。
K算法
以上面的图为例，K算法的思想是以边进行考虑，优先选择小权重的边。首先，选择[1,2]之间权重为1的边，然后选择[2,3]之间权重为1的边，然后考虑[1,3]之间权重为2的边，但是如果选了，[1,3]之间就会构成回路，因此不选，然后再看[1,4]之间权重为2的边，选上，最后结束，[1,2,3,4]都是连通的
利用并查集，初始时每个结点自己是一个集合，每次选完边后，更新集合，判断宣布选择某条边，就看该点所在的集合是否已经包含在当前的集合内，如果包含，就不选，如果不包含就选
public static class UnionFind {//并查集
private HashMap<Node,Node> fatherMap;
private HashMap<Node,Integer> rankMap;
public UnionFind() {
fatherMap = new HashMap<Node,Node>();
rankMap = new HashMap<Node,Integer>();
}
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<Node> 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 <= bFrank) {
fatherMap.put(aFather,bFather);
rankMap.put(bFather,aFrank + bFrank);
} else {
fatherMap.put(bFather,aFather);
rankMap.put(aFather,aFrank + bFrank);
}
}
}
}
public static class EdgeComparator implements Comparator<Edge> {
public int compare(Edge o1,Edge o2) {
return o1.weight - o2.weight;
}
}
public static Set<Edge> kruskalMST(Graph graph) {//K算法
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> res = new HashSet<>();
while(!priorityQueue.isEmpty()) {
Edge edge = priorityQueue.poll();
if(!unionFind.isSameSet(edge.from,edge.to)) {
res.add(edge);
unionFind.union(edge.from,edge.to);
}
}
return res;
}P算法
P算法是以点作为考虑，首先随便选一个点x，和这个点相连的所有的边解锁，找到其中权重最小的边，到达另一个结点y，和这个y结点相连的所有边解锁，再在其中找到全职最小的边（包括上面和x相连的所有边）重复下去就能得到答案
public static class EdgeComparator implements Comparator<Edge> {
public int compare(Edge e1,Edge e2) {
return e1.weight - e2.weight;
}
}
public static Set<Edge> PrimMST(Graph graph) {
PriorityQueue<Edge> priorityQueue = new PriorityQueue<>(new EdgeComparator());
HashSet<Node> set = new HashSet<>();
Set<Edge> res = new HashSet<>();
for(Node node : graph.nodes.values()) {
if(!set.contains(node)) {
set.add(node);
for(Edge edge : node.edges) //node的所有的边加入到队列中
priorityQueue.add(edge);
while(!priorityQueue.isEmpty()) {
Edge edge = priorityQueue.poll();//从队列中弹出一个最小的边
Node toNode = edge.to;
if(!set.contains(toNode)) {//toNode如果不在，就加进来
set.add(toNode);
res.add(edge);
for(Edge nextEdge : toNode.edges) //将toNode的所有边加入队列
priorityQueue.add(nextEdge);
}
}
}
}
return res;
}