算法与数据结构—图

如何存储微博、微信等这些社交网络的好友关系

顶点（vertex）：图中的元素我们就叫作顶点（vertex） 边：图中的一个顶点可以与任意其他顶点建立连接关系。我们把这种建立的关系叫作边（edge）。 度（degree），就是跟顶点相连接的边的条数。 有向图：图的边有方向，比如用户A关注了用户B，但是B没关注A

• 入度：指向点的边数，如微博的粉丝数
• 出度：从该点指出去的边数，如微博的关注数

无向图：边没有方向 带权图：图的每条边带有权重。比如QQ记录两个好友间的亲密度。

图存储

邻接矩阵存储

邻接矩阵的底层依赖一个二维数组。有n个点，就是n行n列的矩阵，对于无向图来说，如果顶点 i 与顶点 j 之间有边，就将 A[i][j] 和 A[j][i] 标记为 1； 对于有向图来说，如果顶点 i 到顶点 j 之间，有一条箭头从顶点 i 指向顶点 j 的边，就将 A[i][j] 标记为 1。 带权重的就把1乘以权重 特点：简单、直观，但是比较浪费存储空间

邻接表存储

有点像散列表；顶点位于一个表（数组）中，每个顶点对应一条链表，链表中存储的是与这个顶点相连接的其他顶点。有向图只存指向的点。 邻接表中存储微博关注数没问题，但是获取粉丝数就比较麻烦。逆邻接表存储粉丝的点 特点：节省空间，但是耗时（也可以对链表进行改造成树来提高搜寻效率）

广度优先搜索算法(BFS)

即先查找离起始顶点最近的，然后是次近的，依次往外搜索。 从起点开始，一层一层往外推进搜索（类似波纹扩展开）。遍历所有的边，时间复杂度为O(E), E为图的边数。

深度优先搜索算法(DFS)

利用回溯算法的思想，（当发现路走不通时可以反悔，回去重新选择，而回溯的本质其实是枚举）；DFS每条边最多被访问两次，一次遍历一次回退。时间复杂度为O(E), E为图的边数。

内存主要是 visited、prev 数组和递归调用栈。isited、prev 数组的大小跟顶点的个数 V 成正比，递归调用栈的最大深度不会超过顶点的个数，总的空间复杂度就是 O(V)。

import java.util.LinkedList;
import java.util.Queue;

//无向图
public class Graph {
	private int v; //顶点数
	private LinkedList<Integer> adj[]; //邻接表,存储相邻节点
	boolean found = false;
	
	public Graph(int v) {
		this.v = v;
		adj = new LinkedList[v];
		for (int i = 0; i < v; i++) {
			adj[i] = new LinkedList<>();
		}
	}
	
	public void addEdge(int s, int t) {
		adj[s].add(t);
		adj[t].add(s);
	}
	
	//广度优先搜索, 从顶点s开始到t的路径
	public void bfs(int s, int t) {
		if (s == t) return;
		
		//记录已访问点解, visited[s]=true;表示s已访问过
		boolean[] visited = new boolean[v];		
		Queue<Integer> queue = new LinkedList<>();	//记录已访问，但是还需要通过该点往后搜索的点
		queue.add(s);
		int[] prev = new int[v];	//用于记录到达该节点的来源节点
		
		for (int i = 0; i < v; i++) {//初始化
			prev[i] = -1;
		}
		
		while (queue.size() != 0) {
			int w = queue.poll();	//从待访问的队列中取出一个点
			for (int i = 0; i < adj[w].size(); i++) {
				int q = adj[w].get(i);	//遍历w点的邻接点表
				if (!visited[q]) {
					
					prev[q] = w;	//记录来到p点的前一个点w
					if (q == t) {
						//找到时，打印出来
						print(prev, s, t);
						return;
					}
					visited[q] = true;	//更新q点的访问状态
					queue.add(q);
				}
			}
		}
		
	}
	
	//深度优先遍历
	public void dfs(int s, int t) {
		found = false;
		boolean[] visited = new boolean[v];
		int[] prev = new int[v];	//用于记录到达该节点的来源节点
		for (int i = 0; i < v; i++) {//初始化
			prev[i] = -1;
		}
		recurDfs(s, t, visited, prev);
		print(prev, s, t);
	}
	
	//递归遍历（深度搜索）
	private void recurDfs(int w, int t, boolean[] visited, int[] prev) {
		if (found) return;	//退出递归条件
		if (w == t) {
			found = true;
		}
		visited[w] = true;
		for (int i = 0; i < adj[w].size(); i++) {
			int q = adj[w].get(i);
			if (!visited[q]) {
				prev[q] = w;
				recurDfs(q, t, visited, prev);
			}
		}
	}
	
	//递归打印s到t的路径
	private void print(int[] prev, int s, int t) {
		if (s == t) {
			System.out.print(s);
			return;
		}
		print(prev, s, prev[t]);
		System.out.print(", ");
		System.out.print(t);
	}
	
}

拓扑排序

多个任务，有的任务之间有依赖关系，怎么排序 任务A依赖B，B依赖C，D依赖B，排序为：CBAD或者CBDA。 通过有向图来建模，任务对应一个顶点，如果任务A依赖B，则顶点A指向顶点B。最终建成一个有向无环图，有环则拓扑排序无法工作。如果顶点的入度为0，则表示顶点没有依赖，可以先执行。 拓扑排序就是基于有向无环图的一个算法。

Kahn 算法

际上用的是贪心算法思想 先从图中，找出一个入度为 0 的顶点（输出），并且把这个顶点从图中删除，并且此点可达的顶点入度减1，重复如此，直到所有的顶点都被输出。 怎么计算顶点的入度（以邻接表存储）: 遍历邻接表统计。 时间复杂度O(V+E), V为顶点数，E为边数

import java.util.LinkedList;
//拓扑排序
public class Topology {
	public static void main(String[] args) {
		Topology t = new Topology();
		t.test();
	}
	
	public void test() {
		//{0,1,2,3,4,5,6,7,8} 8个任务
		Graph g = new Graph(9);
		//添加依赖关系
		g.addEdge(5, 2);
		g.addEdge(0, 2);
		g.addEdge(8, 2);
		g.addEdge(2, 6);
		g.addEdge(6, 4);
		g.addEdge(1, 3);
		g.addEdge(7, 3);
		g.addEdge(3, 5);
		topoSortByKahn(9, g);
	}
	
	//拓扑排序，Kahn算法  0->1->7->8->3->5->2->6->4
	public void topoSortByKahn(int v, Graph g) {
		//用于统计每个点的入度
		int[] inDegree = new int[v];
		for (int i = 0; i < v; i++) {
			//统计每个点的入度
			for (int j = 0; j < g.adj[i].size(); j++) {
				int w = g.adj[i].get(j);
				inDegree[w]++;
			}
		}
		
		//把入度为零的点放入队列
		LinkedList<Integer> queue = new LinkedList<>();
		for (int i = 0; i < v; i++) {
			if (inDegree[i] == 0)
				queue.add(i);
		}
		
		while (!queue.isEmpty()) {
			//删除入度为0的点
			int i = queue.remove();
			System.out.print("->" + i);
			//同时，把指向的点入度减1
			for (int j = 0; j < g.adj[i].size(); j++) {
				int w = g.adj[i].get(j);
				inDegree[w]--;
				if (inDegree[w] == 0)
					queue.add(w);
			}
		}
	}
		
	public class Graph {
		private int v;	//顶点数
		private LinkedList<Integer> adj[]; //邻接表实现图
		
		public Graph(int v) {
			this.v = v;
			adj = new LinkedList[v];	//初始化每个顶点
			for (int i = 0; i < v; i++) {
				adj[i] = new LinkedList<>();
			}
		}
		
		//任务s先于t执行
		//添加一个依赖(边)顶点s指向t，t的入度增加1，
		public void addEdge(int s, int t) {
			adj[s].add(t);
		}
		
	}
}

图的中环检测: 记录访问过的点，如果再次出现，说明出现了环。

，

最短路径

深度优先搜索和广度优先搜索主要应用无无权图的搜索。

要找出起点 s 到终点 t 的最短路径，最简单的方法是，过回溯穷举所有从 s 到达 t 的不同路径，找出最短的。但是回溯算法效太低。指数级。Dijkstra 算法在此基础之上，利用动态规划的思想，对回溯搜索进行了剪枝，对回溯搜索进行了剪枝，继续往外扩展搜索。动态规划相较于回溯搜索，只是换了一个实现思路，但它实际上也考察到了所有从起点到终点的路线，才能得到最优解。

地图计算线路：最短路线、最少用时和最少红绿灯。 解决问题需要先建模，即把问题抽象成具体的数据结构。

次优路径

Dijkstra 最短路径算法的执行耗时会很多。超级大的地图和海量的寻路请求，算法的执行效率太低。实际上，像出行路线规划、游戏寻路，一般都是在兼顾计算效率下的次优解。

A* 算法

A* 算法是对 Dijkstra 算法的优化和改造 Dijkstra 算法有点儿类似 BFS 算法，它每次找到跟起点最近的顶点，往外扩展。

要找出起点 s 到终点 t 的最短路径，最简单的方法是，过回溯穷举所有从 s 到达 t 的不同路径，找出最短的。但是回溯算法效太低。指数级。Dijkstra 算法在此基础之上，利用动态规划的思想，对回溯搜索进行了剪枝，对回溯搜索进行了剪枝，继续往外扩展搜索。动态规划相较于回溯搜索，只是换了一个实现思路，但它实际上也考察到了所有从起点到终点的路线，才能得到最优解。

Dijkstra 优先最近的点，层层外扩，甚至到能那个点在终点的反方向；而A* 算法是通过顶点到起点的距离，和顶点到终点的距离之和小的优先考察（还可以放优先级队列）。 由于顶点到终点的确切距离位置，我们近似评估计算，即用曼哈顿距离（即两点间横纵坐标差之和），之所以用它是因为欧几里得距离计算平方根开销大。

//曼哈顿距离计算
int hManhattan(Vertex v1, Vertex v2) { // Vertex 表示顶点，后面有定义
  return Math.abs(v1.x - v2.x) + Math.abs(v1.y - v2.y);
}

A* 算法是一旦遍历到终点就结束。Dijkstra 还是要考察所有的点和线路。