Data structure | 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

寻找路径

定义路径的接口函数 ```Java 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 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)。任何连通图的连通分量只有一个，即是其自身，非连通的无向图有多个连通分量。

接口 ```Java 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型，所以我们制作一张哈希表存储符号（字符串）和值之间的关系。
符号图接口

```Java 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));
		}
	}

图的接口

无向图的实现

图的API

接口

抽象类

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

UFSearch测试

深度优先查找DFSearch, DFPath

测试

寻找路径

广度优先搜索

连通分量 Connection Component

符号图

符号图接口

符号图的实现

间隔的度数