算法（第4版） Chapter 4 练习题答案

13651657101 发布于2019-08-14 17:13 / 2850人阅读

摘要：离心率计算题目释义计算点的离心率，图的直径，半径，中心计算图的围长定义点的离心率图中任意一点，的离心率是图中其他点到的所有最短路径中最大值。图的中心图中离心率长度等于半径的点。改动离心率计算，在遍历中增加的赋值即可。

离心率计算

4.1.16 The eccentricity of a vertex v is the the length of the shortest path from that vertex to the furthest vertex from v. The diameter of a graph is the maximum eccentricity of any vertex. The radius of a graph is the smallest eccentricity of any vertex. A center is a vertex whose eccentricity is the radius. Implement the following API:

4.1.18 The girth of a graph is the length of its shortest cycle. If a graph is acyclic, then its girth is infinite. Add a method girth() to GraphProperties that returns the girth of the graph. Hint : Run BFS from each vertex. The shortest cycle containing s is a shortest path from s to some vertex v, plus the edge from v back to s.

题目释义
4.1.16 计算点的离心率，图的直径，半径，中心
4.1.18 计算图的围长

定义
点的离心率：图中任意一点v，v的离心率是图中其他点到v的所有最短路径中最大值。
图的直径：图中所有点的离心率的最大值。
图的半径：图中所有点的离心率的最小值。
图的中心：图中离心率长度等于半径的点。
图的围长：如果图中有环，围长则为所有环的长度的最小值。

算法思路
广度优先路径

因为要计算距离，需要一个数组int[] distTo记录距离。可以和数组 boolean[] marked 进行合并。
distTo[] 初始值设为-1，表示未被寻访。一旦被寻访到，就改为其到顶点的距离。

改动

离心率计算，在bfp遍历中增加distTo的赋值即可。

环计算，寻访到一个已经被寻访过的顶点，即说明出现了环。

异常抛出问题还不是很熟练，故未对图非连通的情况进行判别抛出异常

import java.util.*;

public class GraphProperties {
    //private懒得写了
    int[] distTo; //到顶点的距离
    int[] e; //离心率
    int[] c; //cycle
    int[] edgeTo; //前任（是谁牵着你的手走到这条路？）
    
    int diameter = 0;
    int radius = Integer.MAX_VALUE;
    int center;
    int girth = Integer.MAX_VALUE;
    
    //异常抛出问题还不是很熟练，先不考虑
    GraphProperties(Graph G) {
        int V = G.V();
        distTo = new int[V];
        e = new int[V];
        c = new int[V];
        edgeTo = new int[V];
        
        //遍历所有的顶点，造v棵树
        for (int v = 0; v < V; v++) { 
            bfp(G, v);
        }
        
        //找各个最大最小值，各找各妈，各赋各值
        for (int v = 0; v < V; v++) {
            diameter = e[v] > diameter ? e[v] : diameter;
            if (e[v] < radius) {
                radius = e[v];
                center = v;
            }
            girth = c[v] < girth ? c[v] : girth;
        }
    }
    
    //主算法
    void bfp(Graph G, int s) {
        int eccen = 0;
        int cycle = Integer.MAX_VALUE;
        
        for (int v = 0; v < G.V(); v++)
            distTo[v] = -1; //初始化为0，表示未被寻访过
        distTo[s] = 0;
        Queue q = new LinkedList();
        q.offer(s);
        while (!q.isEmpty()) {
            int v = q.poll();
            for (int w : G.adj(v)) {//v是我，w是我的前女友们
                if (distTo[w] == -1) { //如果未被寻访过
                    distTo[w] = distTo[v] + 1; //记录距离
                    eccen = distTo[w]; //这是深度优先算法，因此最后一个被寻访的深度就是最深的
                } else if ( w!= edgeTo[v] ) { //遇到一个寻访过的w，就说明牵着现在老婆的手遇到了前女朋友，人生兜兜转转形成了一个环（前提是你遇到的不是你老婆）
                    int d = distTo[w] + distTo[v] + 1; //算一下绕了多大的一个圈
                    cycle = d < cycle ? d : cycle; //记录最小的那个圈，走最小的套路
                }
            }
        }
        e[s] = eccen;
        c[s] = cycle;
    }

    // diameter of G 图的直径：图中所有点的离心率的最大值。
    public int diameter() {
        return diameter;
    }

    // radius of G 图的半径：图中所有点的离心率的最小值。
    public int radius() {
        return radius;
    }

    // center of G 图的中心：图中离心率的最小值所对的顶点。
    public int center() {
        return center;
    }

    // grith of G 图的围长：如果图中有环，围长则为所有环的长度的最小值。
    public int girth() {
        return girth;
    }

}

GPU云服务器云服务器汇编语言程序设计第二版课后习题答案 python 第4版 hadoop权威指南第4版 linux防火墙第4版

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/66499.html

算法（第4版） Chapter 1

摘要：由的位置决定乘以几，依次为，，，，，。递归算法递归算法就是本次结果用另外的参数调用自己。然而这个函数方法本身并没有用，因为方法中若传递参数为基本型如，在方法中对其值的改变并不会在主函数中产生影响。 Algorithms Fourth EditionWritten By Robert Sedgewick & Kevin WayneTranslated By 谢路云笔记二分查找 Bin...

Jacendfeng 2019-08-14 17:07 评论0 收藏0
Algorithms(第四版)1.1课后练习答案（个人整理）

摘要：最近着手学习的这本书，开始做习题时发现配套网站上对应的习题答案并不完全，后发现以及有些人的博客上有部分答案，不过一般只做了第一章节的题目，大概是题目太多了的原因，在此自己整理自己所做的一份答案，希望有同行的人一起交流，分享。最近着手学习Robert Sedgewick的Algorithms这本书，开始做习题时发现配套网站上对应的习题答案并不完全，google后发现github以及有些...

android_c 2019-08-14 14:39 评论0 收藏0
算法（第4版） Chapter 5.1 字符串排序

摘要：区别把数字对应成字符。这个是字符串的第位。稍作修改可适应不等长的字符串。因此增加一个组别，记录字符为空的频次。 Algorithms Fourth EditionWritten By Robert Sedgewick & Kevin WayneTranslated By 谢路云Chapter 5 Section 1 字符串排序参考资料http://blog.csdn.net/gua...

Amio 2019-08-14 17:15 评论0 收藏0
算法（第4版） Chapter 2.4 优先队列

摘要：堆中位置的结点的父节点的位置为，子节点的位置分别是和一个结论一棵大小为的完全二叉树的高度为用数组堆实现的完全二叉树是很严格的，但它的灵活性足以使我们高效地实现优先队列。 Algorithms Fourth EditionWritten By Robert Sedgewick & Kevin WayneTranslated By 谢路云Chapter 2 Section 4 优先队列 ...

Turbo 2019-08-14 17:17 评论0 收藏0
算法（第4版） Chapter 4.2 强联通性 Tarjan算法补充

摘要：在实际的测试中，算法的运行效率也比算法高左右。此外，该算法与求无向图的双连通分量割点桥的算法也有着很深的联系。学习该算法，也有助于深入理解求双连通分量的算法，两者可以类比组合理解。固属于同一连通分支。参考资料http://blog.csdn.net/acmmmm/a...https://www.byvoid.com/blog/s...http://blog.csdn.net/noth...

maybe_009 2019-08-14 17:13 评论0 收藏0