图的常用工具方式

基于图数据结构的实现，我们可以提供一些工具方法

计算顶点v的度数 顶点的度数就等于与之相连接顶点的个数

1. public static int degree(Graph graph, int v) { 
2.     int degree = 0; 
3.     for (int w : graph.adj(v)) { 
4.         degree++; 
5.     } 
6.     return degree; 
7. } 

计算所有顶点的最大度数

1. public static int maxDegree(Graph graph) { 
2.     int maxDegree = 0; 
3.     for (int v = 0; v < graph.V(); v++) { 
4.         int degree = degree(graph, v); 
5.         if (maxDegree < degree) { 
6.             maxDegree = degree; 
7.         } 
8.     } 
9.     return maxDegree; 
10. } 

计算所有顶点的平均度数 每条边都有两个顶点，所以图所有顶点的总度数是边的2倍

1. public static double avgDegree(Graph graph) { 
2.     return 2.0 * graph.E() / graph.V(); 
3. } 

计算图中的自环个数 对于顶点v，如果v同时也出现了在v的邻接表中，那么表示v存在一个自环;由于是无向图，每条边都被记录了两次(如果不好理解可以把图的toString打印出来就可以理解了)

1. public static int numberOfSelfLoops(Graph graph) { 
2.     int count = 0; 
3.     for (int v = 0; v < graph.V(); v++) { 
4.         for (int w : graph.adj(v)) { 
5.             if (v == w) { 
6.                 count++; 
7.             } 
8.         } 
9.     } 
10.     return count / 2; 
11. } 

（编辑：我爱制作网_潮州站长网）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!