Algorithm-and-Leetcode/DataStructrue/Graph/UndirectedGraph.md at master

Undirected Graph无向图

无向图由边(edge)和顶点(vertex)组成。当两个顶点通过一条边相连时我们称这两个顶点相邻。同时这条边依附于这两个顶点某个顶点的度数为依附它的边的条数。

连通图

如果从任意一个顶点都存在一条路径到达一个任意顶点，我们称这幅图是连通图

图的接口

public interface Graph {
	/**
	 * @Description: Get the vertex number.
	 * @return
	 */
	public int V();
	/**
	 * @Description: Get the edge number.
	 * @return
	 */
	public int E();
	/**
	 * @Description: Create an edge between w and v.
	 * @param v
	 * @param w
	 */
	public void addEdge(int v, int w);
	/**
	 * @Description: Get all vertex adjacent to v.
	 * @param v
	 * @return
	 */
	public Iterable<Integer> adj(int v);
	/**
	 * @Description: Return degree of given vertex.
	 * @param G
	 * @param V
	 * @return
	 */
	static Integer degree(Graph G, int V){
		Integer degree = new Integer(0);
		for(int w : G.adj(V)) degree++;
		return degree;
	}
	/**
	 * @Description: Find the largest degree in the graph
	 * @param G
	 * @param V
	 * @return
	 */
	static int maxDegree(Graph G, int V){
		int max = 0;
		for(int w : G.adj(V) )
			if(w > max)
				max = w;
		return max;
	}
	/**
	 * @Description: Calculate the average degree for all vertex.
	 * @param G
	 * @return
	 */
	static double avgDegree(Graph G){
		return 2 * G.E() / G.V();
	}
		/**
	 * @Description: Get the number of selt loop.
	 * @param G
	 * @param V
	 * @return
	 */
	static int numOfSelfLoop(Graph G, int V){
		int num = 0;
		int vNum = G.V();
		for(int v = 0; v < vNum; v++ )
			for(int w : G.adj(v))
				if(w == v)
					num ++;
		return num/2;	//w,v and v,w will both be counted.
	}
		/**
	 * @Description: Print a graph.
	 */
	default void display(){
		int vertexNum = this.V();
		for(int v = 0; v < vertexNum; v++){
			StringBuilder sb = new StringBuilder(v + " -> ");
			for(int w : adj(v))
				sb.append(w + "");
			System.out.println(sb.toString());
	}
}

无向图的实现

public class UndirectedGraph implements Graph {
	private final int V; //vertex
	private int E;	//edge
	private Bag<Integer>[] adj;	//adjacency table.
	@SuppressWarnings("unchecked")
	public UndirectedGraph(int V) {
		this.V = V;
		adj =  new ListBag[V];
		for(int v = 0; v < V; v++)
			adj[v] = new ListBag<>();
	}
	@SuppressWarnings("unchecked")
	public UndirectedGraph(FileInputStream in){	//Read graph from file.
		Scanner scanner = new Scanner(in);
		this.V = scanner.nextInt();
		adj =  new ListBag[V];
		for(int v = 0; v < V; v++)
			adj[v] = new ListBag<>();
		int E = scanner.nextInt();
		for(int e = 0; e < E; e++){
			int v = scanner.nextInt();
			int w = scanner.nextInt();
			addEdge(v, w);
		}
		scanner.close();
	}
	@Override
	public int V() { return V; }
	@Override
	public int E() { return 0; }
	@Override
	public void addEdge(int v, int w) {	//Add a connection between v and w.
		adj[v].add(w);
		adj[w].add(v);
		this.E++;
	}

	@Override
	public Iterable<Integer> adj(int v) {	//Return a list that the certex connected to.
		return adj[v];
	}
}

图的API

接口

public interface Search {
	/**
	 * @Description: If s and v are connected.
	 * @param v
	 * @return
	 */
	public boolean mark(int v);
	/**
	 * @Description: Number of vertex connected to source.
	 * @return
	 */
	public int count();
}

抽象类

之所以使用抽象类是为了减少重复定义图的构造器方法，而构造器是无法在接口中通过default实现的。

public abstract class AbstractSearch implements Search {
	protected final Graph g;
	protected final int s;	//source点
	public AbstractSearch(Graph g, int s) {
		this.g = g;
		this.s = s;
	}
}

通过加权并查集实现的Seach类： UFSearch

public class UFSearch extends AbstractSearch {
	private final UF uf;
	public UFSearch(Graph g, int s) {
		super(g, s);
		this.uf = new UF(g.V());
		//Insert connections into the UF.
		for(int v = 0; v < g.V(); v++){
			for(int w : g.adj(v)){
				if(uf.connected(v, w))	continue;
				else	uf.union(v, w);
			}
		}
	}
	@Override
	public boolean mark(int v) {
		return uf.connected(super.s, v);
	}
	@Override
	public int count() {
		return uf.size[super.s];
	}
	private final class UF{	//定义了一个内部final私有类UF，其为加权并查集的实现。
		private final int N;
		private final int[] a;	//并查集数组
		private final int[] size;	//当前结点的子结点的数量。
		public UF(int N){
			this.N = N;
			a = new int[N];
			for(int i = 0; i < N; i++)	a[i] = i;
			size = new int[N];
			for(int i = 0; i < N; i++)	size[i] = 1;
		}
		public int find(int v){
			if(a[v] == v)	return v;
			else	return find(a[v]);
		}
		public void union(int p, int q){
			int qRoot = find(q);	//分别找到p和q的根路径
			int pRoot = find(p);
			if(pRoot == qRoot) return;
			if(size[qRoot] < size[pRoot]){	//比较子树数量，连接到更大的树上以减小树得深度
				a[qRoot] = pRoot;
				size[pRoot] += size[qRoot];
			}else{	//size[qRoot] >= size[pRoot]
				a[pRoot] = qRoot;
				size[qRoot] += size[pRoot];
			}
		}
		public boolean connected(int p, int q){
			return find(q) == find(p);
		}
	}

}

UFSearch测试

		Graph g = new UndirectedGraph(new FileInputStream(new File("src/ca/mcmaster/chapter/four/graph/tinyG.txt")));
		Search search = new UFSearch(g, 3);
		System.out.println(search.mark(7));
		g.display();

结果

false 0 -> 6 2 1 5 1 -> 0 2 -> 0 3 -> 5 4 4 -> 5 6 3 5 -> 3 4 0 6 -> 0 4 7 -> 8 8 -> 7 9 -> 11 10 12 10 -> 9 11 -> 9 12 12 -> 11 9

深度优先查找DFSearch, DFPath

public class DeepFirstSearch extends AbstractSearch {
	private boolean[] marked;	//A array used to mark if current node is connected to s
	private int count;	//number of vertex connected to s
	public DeepFirstSearch(Graph g, int s) {
		super(g, s);
		marked = new boolean[g.V()];
		dfs(g, s);
	}
	private void dfs(Graph g, int v){
		marked[v] = true;	//It means current vertex has been accessed.
		count++;	//update the number of vertex connected to s.
		for(int w : g.adj(v))
			if(!marked[w]) dfs(g, w);	//Check all point connected to v, if not accessed, access recursively.
	}
	@Override
	public boolean mark(int v) {
		return marked[v];
	}
	@Override
	public int count() {
		return this.count;
	}
}

测试

	public static void main(String[] args) throws FileNotFoundException {
		Graph g = new UndirectedGraph(new FileInputStream(new File("src/ca/mcmaster/chapter/four/graph/tinyG.txt")));
		Search search = new DeepFirstSearch(g, 12);
		System.out.println(search.mark(9));
		System.out.println(search.count());
		//g.display();
	}

结果

true 4

寻找路径

定义路径的接口函数

public interface Path {
	/**
	 * @Description: If there is a path from s to v
	 * @param v
	 * @return
	 */
	public boolean hasPathTo(int v);
	/**
	 * @Description: Return the path from s to v if it exists and return null if not existing.
	 * @param v
	 * @return
	 */
	Iterable<Integer> pathTo(int v);
}

抽象类

用于定义构造函数。

public abstract class AbstractPath implements Path {
	protected final Graph g;
	protected final int s;
	public AbstractPath(Graph g, int s) {
		super();
		this.g = g;
		this.s = s;
	};
}

深度优先查找路径

public class DepthFirstPath extends AbstractPath {
	private boolean[] marked;	//If current vertex has been accessed.
	private int[] edgeTo;	//Record the path from that point to s.
	public DepthFirstPath(Graph g, int s) {
		super(g, s);
		marked = new boolean[g.V()];
		edgeTo = new int[g.V()];
		dfs(g, s);
	}
	@Override
	public boolean hasPathTo(int v) {
		return marked[v];
	}
	@Override
	public Iterable<Integer> pathTo(int v) {
		if(true == hasPathTo(v)){
			//存入的时候是逆序，读取的时候需要顺序，所以LIFO的队列最为合适，使用栈
			MyStack<Integer> path = new ListStack<>();
			do {
				path.push(v);
				v = edgeTo[v];
			} while (v != s);
			return path;
		}
		return null;
	}
	private void dfs(Graph g, int v){
		marked[v] = true;
		for(int w : g.adj(v)){	//All vertex connected to v
			if(!marked[w]){	//If current vertex has not been accessed, we mark it and save the previous vertex to current vertex.
				edgeTo[w] = v;
				dfs(g, w);
			}
		}
	}
}

测试

	public static void main(String[] args) throws FileNotFoundException {
		Graph g = new UndirectedGraph(new FileInputStream(new File("src/ca/mcmaster/chapter/four/graph/tinyCG.txt")));
		Path p = new DepthFirstPath(g, 0);
		Iterable<Integer> path = p.pathTo(1);
		StringBuilder sb = new StringBuilder("0");
		for(Integer pnode : path){
			sb.append("->" + pnode);
		}
		System.out.println(sb.toString());
	}

0->2->1

广度优先搜索

广度优先用于寻找最短路径。
深度优先（DFP）所寻找到的路径是通过递归调用寻找到路径，递归调用的路径返回是根据adjacency table中的链表的显示顺序。所以返回的值不一定是最短的。
广度优先查找定义了相邻的所有顶点，再找到相邻两个，以此类推。

public class BreadthFirstPath extends AbstractPath{
	private final boolean[] marked;
	private final int[] edgeTo;
	public BreadthFirstPath(Graph g, int s) {
		super(g, s);
		marked = new boolean[g.V()];
		edgeTo = new int[g.V()];
		bfs(g, s);
	}

	@Override
	public boolean hasPathTo(int v) {
		return marked[v];
	}

	@Override
	public Iterable<Integer> pathTo(int v) {
		MyStack<Integer> stack = new ListStack<>();
		do {
			stack.push(v);
			v = edgeTo[v];
		} while (v != s);
		return stack;
	}
	private void bfs(Graph g, int s){
		LinkedBlockingQueue<Integer> q = new LinkedBlockingQueue<Integer>();
		marked[s] = true;
		q.add(s);
		while(!q.isEmpty()){
			Integer v = q.poll();	//从队列中读取下一个顶点并对其遍历相邻顶点。
			for(int w : g.adj(v)){
				if(!marked[w]){	//Current vertex is not accessed.
					q.add(w);	//如果相邻的顶点没有被访问过，就将它加入队列中。
					edgeTo[w] = v;
					marked[w] = true;
				}
			}
		}
	}
}

测试

	public static void main(String[] args) throws FileNotFoundException {
		Graph g = new UndirectedGraph(new FileInputStream(new File("src/ca/mcmaster/chapter/four/graph/tinyCG.txt")));
		Path p = new BreadthFirstPath(g, 0);
		Iterable<Integer> path = p.pathTo(4);
		StringBuilder sb = new StringBuilder("0");
		for(Integer pnode : path){
			sb.append("->" + pnode);
		}
		System.out.println(sb.toString());
	}

连通分量 Connection Component

无向图G的极大连通子图称为G的连通分量( Connected Component)。任何连通图的连通分量只有一个，即是其自身，非连通的无向图有多个连通分量。

接口

public interface ConnectionComponent {
	/**
	 * @Description: If v and w are connected.
	 * @param v
	 * @param w
	 * @return
	 */
	public boolean connected(int v, int w);
	/**
	 * @Description: Number of cc in current graph.
	 * @return
	 */
	public int count();
	/**
	 * @Description: Identification of connection component.
	 * @param v
	 * @return
	 */
	public int id(int v);
}

抽象类

public abstract class AbstractCC implements ConnectionComponent {
	protected final Graph g;
	public AbstractCC(Graph g){
		this.g = g;
	}
}

基于DFS的实现

public class DFSCC extends AbstractCC {
	private boolean[] marked;
	private int[] id;
	private int count;
	public DFSCC(Graph g) {
		super(g);
		marked = new boolean[g.V()];
		id = new int[g.V()];
		for(int v = 0; v < g.V(); v++)	//Traversal all of vertex if not accessed
			if(!marked[v]){	//Current vertex is not accessed.
				dfs(g, v);
				count++;
			}
	}
	@Override
	public boolean connected(int v, int w) {
		return id[w] == id[v];
	}
	@Override
	public int count() {
		return this.count;
	}
	@Override
	public int id(int v) {
		return id[v];
	}
	private void dfs(Graph g, int v){
		marked[v] = true;
		id[v] = count;	//assign current count to this vertex as id.
		for(int w : g.adj(v))
			if(!marked[w])
				dfs(g, w);
	}
}

测试

	public static void main(String[] args) throws FileNotFoundException {
		Graph g = new UndirectedGraph(new FileInputStream(new File("src/ca/mcmaster/chapter/four/graph/tinyG.txt")));
		DFSCC cc = new DFSCC(g);
		int ccNum = cc.count();
		System.out.println("Number of cc: " + ccNum);
		Bag<Integer>[] bag = new ListBag[ccNum];	//Create bag array to save all connection components.
		for(int i = 0; i < ccNum; i++)
			bag[i] = new ListBag<>();
		for(int i = 0; i < g.V(); i++)
			bag[cc.id(i)].add(i);	//Add vertex into bag.
		for(int i = 0; i < ccNum; i++){
			StringBuilder sb = new StringBuilder(i + ": ");
			for(int v : bag[i])
				sb.append(v + " ");
			System.out.println(sb.toString());
		}
	}

Number of cc: 3 0: 6 5 4 3 2 1 0 1: 8 7 2: 12 11 10 9

符号图

图中的顶点都是int型，所以我们制作一张哈希表存储符号（字符串）和值之间的关系。

符号图接口

public interface SymbolGraph {
	/**
	 * @Description: Is key a vertex.
	 * @param key
	 * @return
	 */
	public boolean contains(String key);
	/**
	 * @Description: Index of key.
	 * @param key
	 * @return
	 */
	public int index(String key);
	/**
	 * @Description: name of v in symbol table
	 * @param v
	 * @return
	 */
	public String name(int v);
	/**
	 * @Description: Get the anonymous graph object.
	 * @return
	 */
	public Graph G();
}

符号图的实现

public class SymbolGraphImpl implements SymbolGraph {
	private final Map<String, Integer> st;
	private String[] keys;
	private final Graph G;
	public SymbolGraphImpl(String file, String sp) throws FileNotFoundException {
		st = new HashMap<>();
		//fulfill the symbol table
		Scanner scanner = null;
		try {
			scanner = new Scanner(new File(file));	//将每个顶点都加入符号表
			int count = 0;
			while(scanner.hasNextLine()){
				String[] tokens = scanner.nextLine().split(sp);
				for(String t : tokens){
					if(!st.containsKey(t)){	//If not contains token then put it into the st.
						st.put(t, count++);
					}
				}
			}
		}finally{
			scanner.close();
		}
		keys = new String[st.size()];	//没有办法之间用(String[])st.keySet.toArray(),只能通过遍历将每一个顶点的符号复制。
		for(String name : st.keySet()){
			keys[st.get(name)] = name;
		}
		// Create graph
		G = new UndirectedGraph(st.size());
		//Add edges
		Scanner scanner2 = null;
		try{
			scanner2 = new Scanner(new File(file));
			while(scanner2.hasNextLine()){
				String[] tokens = scanner2.nextLine().split(sp);
				for(int i = 1; i < tokens.length; i++){
					int v = st.get(tokens[0]);
					G.addEdge(v, st.get(tokens[i]));
				}
			}
		}finally{
			scanner2.close();
		}
	}
	@Override
	public boolean contains(String key) { return st.containsKey(key); }

	@Override
	public int index(String key) { return st.get(key); }

	@Override
	public String name(int v) { return keys[v]; }

	@Override
	public Graph G() { return G; }

	public static void main(String[] args) throws FileNotFoundException {
		SymbolGraphImpl symbolGraphImpl = new SymbolGraphImpl("src/ca/mcmaster/chapter/four/graph/movies.txt", "/");
		Graph graph = symbolGraphImpl.G();
		int vertexNum = graph.V();
		for(int v = 0; v < vertexNum; v++){
			StringBuilder sb = new StringBuilder(symbolGraphImpl.name(v) + " -> ");
			for(int w : graph.adj(v))
				sb.append(symbolGraphImpl.name(w) + " ");
			System.out.println(sb.toString());
		}
	}
}

间隔的度数

间隔的度数实际上就是最短路径，即两个顶点之间的最短距离。

	public static void main(String[] args) throws FileNotFoundException {
		SymbolGraphImpl symbolGraphImpl = new SymbolGraphImpl("src/ca/mcmaster/chapter/four/graph/movies.txt", "/");
		Graph graph = symbolGraphImpl.G();
		int vertexNum = graph.V();
		for(int v = 0; v < vertexNum; v++){
			StringBuilder sb = new StringBuilder(symbolGraphImpl.name(v) + " -> ");
			for(int w : graph.adj(v))
				sb.append(symbolGraphImpl.name(w) + "|");
		}
		//Use BFS to find the shorted path.
		BreadthFirstPath bfs = new BreadthFirstPath(graph, symbolGraphImpl.index("Bacon, Kevin"));
		Iterable<Integer> pathTo = bfs.pathTo(symbolGraphImpl.index("Kidman, Nicole"));
		System.out.println("Bacon, Kevin");
		for(int w : pathTo){
			System.out.println(symbolGraphImpl.name(w));
		}
	}