博客

图是一种非线性数据结构，图的存储有两种方式，邻接矩阵和邻接表。

邻接矩阵存储方法的缺点是比较浪费空间，但是优点是查询效率高，而且方便矩阵运算。

邻接表存储方法中每个顶点都对应一个链表，存储与其相连接的其他顶点。尽管邻接表的存储方式比较节省存储空间，但链表不方便查找，所以查询效率没有邻接矩阵存储方式高。针对这个问题，邻接表还有改进升级版，即将链表换成更加高效的动态数据结构，比如平衡二叉查找树、跳表、散列表等。

图的搜索方式有两种深度优先和广度优先

广度优先搜索





深度优先搜索

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<>();
		}
	}
	
	public void addEdge(int s,int t) {
		adj[s].add(t);
		adj[t].add(s);
	}
	
	/**
	 * 广度优先搜索：最短路径
	 * 它其实就是一种“地毯式”层层推进的搜索策略，即先查找离起始顶点最近的，然后是次近的，依次往外搜索。
	 * @param s 起始点
	 * @param t 终止点
	 * 时间复杂度：O(E),E表示图的边数
	 * 空间复杂度：O(V)，V表示图的顶点数
	 */
	public void bfs(int s,int t) {
		if(s==t) return;
		
		boolean[] visited = new boolean[v];
		Queue<Integer> queue = new LinkedList<>();
		int[] prev = new int[v];
		for(int i=0;i<v;i++) {
			prev[i] = -1;
		}
		
		visited[s] = true;
		queue.add(s);
		while(!queue.isEmpty()) {
			int w = queue.poll();
			for(int i=0;i<adj[w].size();i++) {
				int q = adj[w].get(i);
				if(!visited[q]) {
					prev[q] = w;
					if(q==t) {
						print(prev,s,t);
						return;
					}
					visited[q] = true;
					queue.add(adj[w].get(i));
				}
			}
		}
	}
	
	/**
	 * 广度优先遍历查找维度为3的好友
	 * @param s
	 * @param dep
	 */
	public void bfs_3(int s,int dep) {
		int[] deep = new int[v];
		boolean[] visited = new boolean[v];
		Queue<Integer> queue = new LinkedList<>();
		int[] prev = new int[v];
		for(int i=0;i<v;i++) {
			prev[i] = -1;
		}
		
		visited[s] = true;
		deep[s] = 0;
		
		queue.add(s);
		while(!queue.isEmpty()) {
			int w = queue.poll();
			for(int i=0;i<adj[w].size();i++) {
				int q = adj[w].get(i);
				if(!visited[q]) {
					prev[q] = w;
					deep[q] = deep[w]+1;
					if(deep[q]==dep) {
						print(prev,s,q);
						System.out.println();
					}else if(deep[q] >= 4) {
						return;
					}
					visited[q] = true;
					queue.add(adj[w].get(i));
				}
			}
		}
	}
	
	private void print(int[] prev,int s,int t) {
		if(t != s && prev[t] != -1) {
			print(prev,s,prev[t]);
		}
		System.out.print(t+"->");
	}
	
	private boolean found = false;
	/**
	 * 深度优先搜索
	 * 最直观的例子就是“走迷宫”。假设你站在迷宫的某个岔路口，然后想找到出口。你随意选择一个岔路口来走，走着走着发现走不
	 * 通的时候，你就回退到上一个岔路口，重新选择一条路继续走，直到最终找到出口。这种方法就是一种深度优先搜索策略。
	 * @param s
	 * @param t
	 * 时间复杂度：O(E)
	 * 空间复杂度：O(V)
	 */
	public void dfs(int s,int t) {
		boolean[] visited = new boolean[v];
		int[] prev = new int[v];
		for(int i=0;i<v;i++) {
			prev[i] = -1;
		}
		
		recurDFS(prev,visited,s,t);
		print(prev,s,t);
	}
	
	public void recurDFS(int prev[],boolean[] visited,int w,int t) {
		if(found) return;
		
		visited[w] = true;
		
		if(w==t) {
			found = true;
			return;
		}
		
		for(int i = 0;i<adj[w].size();i++) {
			int q = adj[w].get(i);
			if(!visited[q]) {
				prev[q] = w;
				recurDFS(prev,visited,q,t);
			}
		}
	}
}

测试搜索

public class TestGraph {
	public static void main(String[] args) {
		Graph graph = new Graph(8);
		graph.addEdge(0, 1);
		graph.addEdge(0, 3);
		graph.addEdge(1, 2);
		graph.addEdge(1, 4);
		graph.addEdge(3, 4);
		graph.addEdge(4, 5);
		graph.addEdge(4, 6);
		graph.addEdge(5, 7);
		graph.addEdge(6, 7);
		
		//graph.bfs(0, 6);
		//graph.dfs(0, 6);
		graph.bfs_3(0, 3);
		System.out.println("---------------");
		graph.dfs(0, 3);
	}
}

执行结果

0->1->4->5->
0->1->4->6->
---------------
0->1->4->3->