算法（第4版） Chapter 4 練習題答案

13651657101 發布于2019-08-14 17:13 / 2911人閱讀

摘要：離心率計算題目釋義計算點的離心率，圖的直徑，半徑，中心計算圖的圍長定義點的離心率圖中任意一點，的離心率是圖中其他點到的所有最短路徑中最大值。圖的中心圖中離心率長度等于半徑的點。改動離心率計算，在遍歷中增加的賦值即可。

離心率計算

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版

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://specialneedsforspecialkids.com/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