图算法

完整代码见：https://github.com/huangliu0909/Graph-Algorithms

基本图算法

深度优先搜索 DFS

使用栈(First-In-Last-Out)，起始点入栈，当栈不为空时，pop，如果这个点未被访问，则标记为已访问，加入结果数组，将与这个点相连的顶点逐个入栈，循环直到栈为空。

   void DFS() {
	stack4DFS = new Stack<Integer>();
	for(int i = 0; i < edges.length; i ++) 
		vertex[i] = -1;
	//start from 0
	stack4DFS.push(0);
	int[] res = new int[edges.length];
	int count = 0;
	while(!stack4DFS.isEmpty()) {
		int now = stack4DFS.pop();
		if(vertex[now] == -1) {
			vertex[now] = 1;
			res[count] = now;
			count ++;
			for(int i = 0; i < edges.length; i ++) {
				if(edges[now][i] > 0) {
					stack4DFS.push(i);
				}
			}
		}
	}
	System.out.print(Arrays.toString(res) + "\n");
}

广度优先搜索 BFS

使用队列(Queue: First-In-First-Out)，将源结点插入队列，当队列非空：队列弹出作为当前遍历的值，将与这个点相连的其它结点都加入队列，重复以上步骤直到队列为空。

   void BFS() {
	queue4BFS = new LinkedList<Integer>();
	for(int i = 0; i < edges.length; i ++) 
		vertex[i] = -1;
	//start from 0
	queue4BFS.add(0);
	vertex[0] = 1;
	int[] res = new int[edges.length];
	int count = 0;
	while(!queue4BFS.isEmpty()) {
		int now = queue4BFS.poll();
		res[count] = now;
		//System.out.print(Arrays.toString(edges[now]));
		count ++;
		for(int i = 0; i < edges.length; i ++) {
			if(edges[now][i] > 0 && vertex[i] == -1) {
				vertex[i] = 1;
				queue4BFS.add(i);
			}
		}
	}
	System.out.print(Arrays.toString(res) + "\n");
}

拓扑排序

有向无环图(Directed Acyclic Graph)的所有顶点的有序线性排列。不断输出并删除入度为0的结点，如果最终无法输出所有结点则该图中存在环。

void topological_sort() {
	for(int i = 0; i < edges.length; i ++) 
		vertex[i] = -1;
	int[] res = new int[edges.length];
	int count = 0;
	while(count != edges.length) {
		for(int i = 0; i < edges.length; i ++) {
			if(vertex[i] == -1) {
				int flag = 0;
				for(int j = 0; j < edges.length; j ++) {
					if(edges[j][i] != Integer.MAX_VALUE) {
						flag = 1;
						break;
					}
				}
				if(flag == 0) { //找到入度为0的结点i
					res[count] = i;
					vertex[i] = 1; //标记为已访问
					break;
				}
			}
		}
		for(int i = 0; i < edges.length; i ++) 
			edges[res[count]][i] = Integer.MAX_VALUE;
		count ++;
	}
	System.out.println(Arrays.toString(res));
}

最小生成树 Minimum Spanning Tree

生成树：连接图的所有结点的无环连通子图，顶点个数=图顶点个数，边个数=图顶点个数-1。减少一条边会使得ST不连通，增加一条边会使得ST出现环。非连通图不存在生成树ST。
最小生成树：边的总权重和最小的生成树。可以通过不断删除最大的e-n+1条边来得到MST。

Kruskal算法

往集合里加入边
对每条边进行排序。使用Find-Set(u)返回u所在树的代表结点，使Union对两棵树进行合并。

void Kruskal() {
	vertex = new int[edges.length];
	for(int i = 0; i < vertex.length; i ++) vertex[i] = i; //每个结点的父节点都初始化为自己
	int[][] e = new int[0][3]; //将边整理为（u，v，w）的形式
	for(int i = 0; i < edges.length; i ++) {
		for(int j = i + 1; j < edges.length; j ++) {
			if(edges[i][j] < Integer.MAX_VALUE)
				e = arrAppend(e, new int[] {i, j, edges[i][j]});
		}
	}
	 Arrays.sort(e, new edgeComp()); 
	 for(int i = 0; i < e.length; i ++) {
		 //System.out.println(Arrays.toString(e[i]));
		 if(find_set(vertex, e[i][0]) != find_set(vertex, e[i][1])) {
			 union(vertex, e[i][0], e[i][1]);
			 System.out.print(e[i][0]);
			 System.out.print(" -- ");
			 System.out.print(e[i][1]);
			 System.out.print(" : ");
			 System.out.print(e[i][2]);
			 System.out.println();
		 }
	 }
}

int find_set(int[] p, int x) {
	if(p[x] == x) return x;
	return find_set(p, p[x]);
}

void union(int[] p, int x1, int x2) {
	int s1 = find_set(p, x1);
	int s2 = find_set(p, x2);
	p[s2] = s1; 
}

int[][] arrAppend(int[][] arr, int[] value) {
       arr = Arrays.copyOf(arr, arr.length + 1);
       arr[arr.length - 1] = value;
       return arr;
   }

class edgeComp implements Comparator<int[]> 
{ 
    // Used for sorting in ascending order of 
    // roll number 
    public int compare(int[] a, int[] b) 
    { 
        return a[2] - b[2]; 
    } 
}

Prim算法

往集合里加入点 $O(E log V)$
首先去掉所有的从自己到自己的环，去掉两节点之间的多条边保留最短的一条。
在连接集合A和A之外的结点的所有边中，选择一条轻量级边加入A中，从而保证每一步所加入的边都必须是使树的总权重增加量最小的边。
从任意结点开始都可以得到唯一的MST。

int findMin(int v, int[] visit, int[] e) {
	//找到e中与v相连的未访问过的距离最近的结点
	int min = Integer.MAX_VALUE;
	int index = -1;
	for(int i = 0; i < e.length; i ++) {
		if(e[i] < min && visit[i] == -1) {
			min = e[i];
			index = i;
		}
	}
	return index;
}

void Prim() {
	minPath = new int[edges.length];
	vertex = new int[edges.length];
	for(int i = 0; i < vertex.length; i ++) vertex[i] = -1;
	int count = 0;
	minPath[count] = 0;
	vertex[minPath[count]] = 1;
	count ++;
	while(count < edges.length) {
		int min = Integer.MAX_VALUE;
		int index_s = -1;
		int index = -1;
		for(int i = 0; i < count; i ++) {
			int e = minPath[i];
			int now = findMin(e, vertex, edges[e]);
			if(now >= 0 && edges[e][now] < min) {
				index_s = e;
				min = edges[e][now];
				index = now;
			}
		}
		minPath[count] = index;
		vertex[minPath[count]] = 1;
		count ++;
	}
	System.out.print(Arrays.toString(minPath) + "\n");
}

单源最短路径

Dijkstra算法 $O(VlgV)$

初始化距离数组dis，大小等于顶点数目，源结点对应0，其它都对应正无穷。在未访问的结点中找到离x的路径最短的结点作为当前结点，用当前结点的邻接矩阵对dis进行更新，将该结点标记为已访问，重复上述步骤。

void Dijkstra(int x) {
	int[] dis = new int[edges.length];
	int[] path = new int[edges.length];
	for(int i = 0; i < edges.length; i ++) dis[i] = Integer.MAX_VALUE;
	dis[x] = 0;//自己到自己的最短路径为0
	path[x] = -1;
	Set<Integer> set = new HashSet<>();
	int count = 0;
	while(count != edges.length) {
		int now = -1; //在未访问的结点中找到离x的路径最短的结点作为当前结点
		int min = Integer.MAX_VALUE;
		for(int i = 0; i < edges.length; i ++) {
			if(!set.contains(i) && dis[i] < min) {
				now = i;
				min = dis[i];
			}
		}
		//用当前结点now的临界边与dis中的路径长度作比较并进行更新
		for(int i = 0; i < edges.length; i ++) {
			if(edges[now][i] != Integer.MAX_VALUE && edges[now][i] + dis[now] < dis[i]) {
				dis[i] = edges[now][i] + dis[now];
				path[i] = now;
			}
		}
		//将now加入已访问的集合中
		set.add(now);
		count ++;
	}
	System.out.print("distance: " + Arrays.toString(dis) + "\n");
	System.out.print("last vertex: " + Arrays.toString(path) + "\n");
}

Bellman–Ford $O(VE)$

对n个点做(n - 1)次遍历，每一轮遍历需要检查所有的边。原理比Dijkstra简单，但时间复杂度更高。
Dijkstra不适用于边权重为负的有向图，Bellman-Ford可用于此类图，且更适用于分布式系统。
初始化距离数组dis，大小等于顶点数目，源结点对应0，其它都对应正无穷。对每个边uv进行遍历，如果$dis[v]>dis[u]+w(u,v)$，则更新$dis[v]>dis[u]+w(u,v)$。

void Bellman_Ford(int x){
	int[] dis = new int[edges.length];
	int[] path = new int[edges.length];
	path[x] = -1;
	for(int i = 0; i < edges.length; i ++) dis[i] = Integer.MAX_VALUE;
	dis[x] = 0;//自己到自己的最短路径为0
	for(int k = 0; k < edges.length - 1; k ++) {
		for(int i = 0; i < edges.length; i ++) {
			for(int j = 0; j < edges.length; j ++) {
				if( dis[i] != Integer.MAX_VALUE && edges[i][j] != Integer.MAX_VALUE) {	
					if(dis[j] > dis[i] + edges[i][j]) {
						dis[j] = dis[i] + edges[i][j];
						path[j] = i;
					}
				}
			}
		}
	}
	System.out.print("distance: " + Arrays.toString(dis) + "\n");
	System.out.print("last vertex: " + Arrays.toString(path) + "\n");
}

Floyd Warshall $O(V^3)$

解决所有点对之间的最短路径问题：简单粗暴的三层循环。根据dis[i][k]+dis[k][j]对dist[i][j]进行更新。

void Floyd_Warshall() {
	int[][] dis = new int[edges.length][edges.length];
	for(int i = 0; i < edges.length; i ++)
		for(int j = 0; j < edges.length; j ++)
			dis[i][j] = edges[i][j];
	for(int k = 0; k < edges.length; k ++)
		for(int i = 0; i < edges.length; i ++)
			for(int j = 0; j < edges.length; j ++)
				if(dis[i][k] != Integer.MAX_VALUE && dis[k][j] != Integer.MAX_VALUE)
					dis[i][j] = Math.min(dis[i][j], dis[i][k] + dis[k][j]);
	for(int[] x : dis)
		System.out.println(Arrays.toString(x));
}

图搜索策略

爬山算法 Hill Climbing

用贪心确定搜索方向，是优化的深度优先搜索
用启发式测度来排序节点
扩展的顺序：对兄弟进行比较
子节点按照测度f(n)从大到小入栈

Best-First搜索

优化的广度&深度优先
比较所有子节点和兄弟结点的深度
在一些情况下，如果我们可以预先计算出每个节点到终点的距离，则我们可以利用这个信息更快的到达终点。如果起点和终点之间存在障碍物，则最佳优先算法找到的很可能不是最短路径。

路径规划A*算法

用Best-First进行搜索，某些情况下一旦找到解，则解为优化解，无需搜索整个解空间。
如果图满足dis(A, G) < dis(A, D) + h(D, g)，即a到g的实际值大于a到g的估计值，则A*算法一定能找到优化解。

https://zhuanlan.zhihu.com/p/54510444

• 初始化open_set和close_set；
• 将起点加入open_set中，并设置优先级为0（优先级最高）；
• 如果open_set不为空，则从open_set中选取优先级最高的节点n：
  • 如果节点n为终点，则：
    • 从终点开始逐步追踪parent节点，一直达到起点；
    • 返回找到的结果路径，算法结束；
  • 如果节点n不是终点，则：
    • 将节点n从open_set中删除，并加入close_set中；
    • 遍历节点n所有的邻近节点：
      • 如果邻近节点m在close_set中，则：
        • 跳过，选取下一个邻近节点
      • 如果邻近节点m也不在open_set中，则：
        • 设置节点m的parent为节点n
        • 计算节点m的优先级
        • 将节点m加入open_set中

Branch-and-Bound策略

1. 用评价函数构造一个堆H，首先构造由根组成的单元素堆
2. if rH的根r是目标结点 then 停止
3. 从H中删除r，把r的子节点插入H
4. if H为空 then 失败；else goto 2

完整代码见：https://github.com/huangliu0909/Graph-Algorithms