成人无码视频,亚洲精品久久久久av无码,午夜精品久久久久久毛片,亚洲 中文字幕 日韩 无码

資訊專欄INFORMATION COLUMN

算法（第4版） Chapter 4 練習(xí)題 答案

13651657101 / 2974人閱讀

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

離心率計算

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的所有最短路徑中最大值。
圖的直徑：圖中所有點的離心率的最大值。
圖的半徑：圖中所有點的離心率的最小值。
圖的中心：圖中離心率長度等于半徑的點。
圖的圍長：如果圖中有環(huán)，圍長則為所有環(huán)的長度的最小值。

算法思路
廣度優(yōu)先路徑

因為要計算距離，需要一個數(shù)組int[] distTo記錄距離?？梢院蛿?shù)組 boolean[] marked 進行合并 。
distTo[] 初始值設(shè)為-1，表示未被尋訪。一旦被尋訪到，就改為其到頂點的距離。

改動

離心率計算，在bfp遍歷中增加distTo的賦值即可。

環(huán)計算，尋訪到一個已經(jīng)被尋訪過的頂點，即說明出現(xiàn)了環(huán)。

異常拋出問題還不是很熟練，故未對圖非連通的情況進行判別拋出異常

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]; //這是深度優(yōu)先算法，因此最后一個被尋訪的深度就是最深的
                } else if ( w!= edgeTo[v] ) { //遇到一個尋訪過的w，就說明牽著現(xiàn)在老婆的手遇到了前女朋友，人生兜兜轉(zhuǎn)轉(zhuǎn)形成了一個環(huán)（前提是你遇到的不是你老婆）
                    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 圖的圍長：如果圖中有環(huán)，圍長則為所有環(huán)的長度的最小值。
    public int girth() {
        return girth;
    }

}

文章版權(quán)歸作者所有，未經(jīng)允許請勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。

轉(zhuǎn)載請注明本文地址：http://m.hztianpu.com/yun/66499.html

相關(guān)文章

  • 算法（第4版） Chapter 1

    摘要：由的位置決定乘以幾，依次為，，，，，。遞歸算法遞歸算法就是本次結(jié)果用另外的參數(shù)調(diào)用自己。然而這個函數(shù)方法本身并沒有用，因為方法中若傳遞參數(shù)為基本型如，在方法中對其值的改變并不會在主函數(shù)中產(chǎn)生影響。 Algorithms Fourth EditionWritten By Robert Sedgewick & Kevin WayneTranslated By 謝路云 筆記 二分查找 Bin...

    Jacendfeng 評論0 收藏0

  • Algorithms(第四版)1.1課后練習(xí)答案（個人整理）

    摘要：最近著手學(xué)習(xí)的這本書，開始做習(xí)題時發(fā)現(xiàn)配套網(wǎng)站上對應(yīng)的習(xí)題答案并不完全，后發(fā)現(xiàn)以及有些人的博客上有部分答案，不過一般只做了第一章節(jié)的題目，大概是題目太多了的原因，在此自己整理自己所做的一份答案，希望有同行的人一起交流，分享。 最近著手學(xué)習(xí)Robert Sedgewick的Algorithms這本書，開始做習(xí)題時發(fā)現(xiàn)配套網(wǎng)站上對應(yīng)的習(xí)題答案并不完全，google后發(fā)現(xiàn)github以及有些...

    android_c 評論0 收藏0

  • 算法（第4版） Chapter 5.1 字符串排序

    摘要：區(qū)別把數(shù)字對應(yīng)成字符。這個是字符串的第位。稍作修改可適應(yīng)不等長的字符串。因此增加一個組別，記錄字符為空的頻次。 Algorithms Fourth EditionWritten By Robert Sedgewick & Kevin WayneTranslated By 謝路云Chapter 5 Section 1 字符串排序 參考資料http://blog.csdn.net/gua...

    Amio 評論0 收藏0

  • 算法（第4版） Chapter 2.4 優(yōu)先隊列

    摘要：堆中位置的結(jié)點的父節(jié)點的位置為，子節(jié)點的位置分別是和一個結(jié)論一棵大小為的完全二叉樹的高度為用數(shù)組堆實現(xiàn)的完全二叉樹是很嚴(yán)格的，但它的靈活性足以使我們高效地實現(xiàn)優(yōu)先隊列。 Algorithms Fourth EditionWritten By Robert Sedgewick & Kevin WayneTranslated By 謝路云Chapter 2 Section 4 優(yōu)先隊列 ...

    Turbo 評論0 收藏0

  • 算法（第4版） Chapter 4.2 強聯(lián)通性 Tarjan算法補充

    摘要：在實際的測試中，算法的運行效率也比算法高左右。此外，該算法與求無向圖的雙連通分量割點橋的算法也有著很深的聯(lián)系。學(xué)習(xí)該算法，也有助于深入理解求雙連通分量的算法，兩者可以類比組合理解。固屬于同一連通分支。 參考資料http://blog.csdn.net/acmmmm/a...https://www.byvoid.com/blog/s...http://blog.csdn.net/noth...

    maybe_009 評論0 收藏0

發(fā)表評論

0條評論

閱讀需要支付1元查看
<