Algorithms 第四版 习题 4.1.16- 4.1.18
原书部分内容见：http://algs4.cs.princeton.edu/home/
4.1.16 计算点的离心率，图的直径，半径，中心
4.1.18 计算图的围长
定义：
点的离心率：图中任意一点v，v的离心率是图中其他点到v的所有最短路径中最大值。
图的直径：图中所有点的离心率的最大值。
图的半径：图中所有点的离心率的最小值。
图的中心：图中离心率长度等于半径的点。
图的围长：如果图中有环，围长则为所有环的长度的最小值。
一般解法：
1. 分别以图中每个点为根进行 广度优先搜索BFS，每次BFS计算并用数组 e[] 保存好每个点的离心率。之后迭代数组即可得知直径，半径，中心。
2. 对于围长，分别以图中每个点为根进行BFS，每次BFS计算并用数组 g [] 保存包含该点的最小环的长度。之后迭代数组即可得知图的围长。
以上两种操作可以在同一迭代中进行。
另外，为方便计算，标记 点 是否访问过时 改用具体的数字- 点到根的距离，即点到根的最短路径 - 代替使用布尔值标记。即定义 int [] marked = new marked [G.V]
为了计算包含某个点的最小环，对于每个层次的BFS，需要知道该层次中各点，例如u，的前驱是哪个点：如果有边连接v 到 u，如果u不是v的前驱，则说明出现了环，
该环的长度为 marked[v] + marked[u] +1。
因为要对每个点进行BFS，所以时间复杂度为 O(V *(V+E))，V为点数，E为边数。
代码如下：
package com.cupid.algorithm.graph.algorithms4th;import java.io.File;import java.io.FileNotFoundException;import java.util.LinkedList;import java.util.Queue;import java.util.Scanner;public class GraphProperties {// Rather than using boolean values to indicate whether a vertex was visited,// use a Integer array to mark each visited vertex.// If marked[v] = -1 , vertex v has not been visited.// If v is root of a BFS, marked[v] = 0;// Other positive values represent for the shortest path length from source(root) to a particular vertex.private int[] marked;// Integer array e is used to store eccentricity of every vertex.private int[] e;// Integer array g is used to store minimum length of circle(s) involving the root vertex.private int[] g;// For calculating minimum length of circle(s), Integer array p is used to store predecessor of every vertex. private int[] p;private Graph myGraph;private int center; public GraphProperties(Graph G){e = new int[G.V()];g = new int[G.V()];p = new int[G.V()];marked = new int[G.V()];this.myGraph = G;// Calculate the eccentricity and girth for the tree rooted at each vertex// to decide diameter, radius, center, and girth of a given graph.// It takes O(V*(V+E))for(int i=0;i<myGraph.V();i++){breathFirstSearch(i,e,g);}}public int eccentricity(int v){return e[v];}public int girth(){int min = Integer.MAX_VALUE;for(int i=0;i<g.length;i++){if(g[i] < min){min = g[i];}}return min;}// The diameter of a graph is the maximum eccentricity// of any vertex.public int diameter(){int max = Integer.MIN_VALUE;for(int i=0;i<e.length;i++){if(e[i] > max){max = e[i];}}return max;}// The radius of a graph is the smallest eccentricity of any vertex. A center is// a vertex whose eccentricity is the radius.public int radius(){int min = Integer.MAX_VALUE;for(int i=0;i<e.length;i++){if(e[i] < min){min = e[i];center = i;}}return min;}// Calculate the eccentricity and girth for a given vertex.// Definition from Algorithms 4th edition:// The eccentricity of a vertex v is the the length of the shortest path from that vertex// to the farthest vertex from v // The girth of a graph is the length of its shortest cycle. If a graph is acyclic, then its// girth is infinite.private void breathFirstSearch(int v,int[] e,int[] g){// Initialize int[] marked before a BFS is going to commence.for(int i=0;i<myGraph.V();i++){marked[i] = -1;}// A standard BFS begins.Queue<Integer> q = new LinkedList<Integer>();int eccen = 0;int girth = Integer.MAX_VALUE;marked[v] = 0;q.add(v);while(!q.isEmpty()){int u = q.poll();for(Integer w: myGraph.adj(u)){if(marked[w] <0){// Each level of BFS should increase shortest path length by 1marked[w] = marked[u] +1;// Assign a shortest path length to an eccentricity.eccen = marked[w];// w's parent u was found.p[w] = u;q.add(w);}else{// If the marked vertex w is not u's parent,// there is a circle here.if(w != p[u]){// Decide that whether this circle's length is greater than// the smallest one that has been discovered.// If no, this circle is the smallest one.if(girth > marked[w] + marked[u] + 1){girth = marked[w] + marked[u] + 1;}}}}}// Store eccentricity and girth for root vertex in every BFS.e[v] = eccen;g[v] = girth;}public int getCenter() {return center;}public static void main(String[] args) {File file = new File("d:\\mediumG.txt");try {Scanner in = new Scanner(file);Graph G = new Graph(in);System.out.println(G);GraphProperties gps = new GraphProperties(G);System.out.println("The diameter is: " + gps.diameter());System.out.println("The radius is: " +gps.radius());System.out.println("The center is vertex No." + gps.getCenter());if(gps.girth() == Integer.MAX_VALUE){System.out.println("The girth is infinite since the graph is acyclic.");}else{System.out.println("The girth is: " + gps.girth());}}catch(FileNotFoundException e){e.printStackTrace();}}}PS：关于具体的图的实现（如每个点的邻接链表）及 测试数据 可以参考上面的原书网址。