成人国产在线小视频_日韩寡妇人妻调教在线播放_色成人www永久在线观看_2018国产精品久久_亚洲欧美高清在线30p_亚洲少妇综合一区_黄色在线播放国产_亚洲另类技巧小说校园_国产主播xx日韩_a级毛片在线免费

資訊專欄INFORMATION COLUMN

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

13651657101 / 2925人閱讀

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

離心率計(jì)算

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 計(jì)算點(diǎn)的離心率，圖的直徑，半徑，中心
4.1.18 計(jì)算圖的圍長(zhǎng)

定義
點(diǎn)的離心率：圖中任意一點(diǎn)v，v的離心率是圖中其他點(diǎn)到v的所有最短路徑中最大值。
圖的直徑：圖中所有點(diǎn)的離心率的最大值。
圖的半徑：圖中所有點(diǎn)的離心率的最小值。
圖的中心：圖中離心率長(zhǎng)度等于半徑的點(diǎn)。
圖的圍長(zhǎng)：如果圖中有環(huán)，圍長(zhǎng)則為所有環(huán)的長(zhǎng)度的最小值。

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

因?yàn)橐?jì)算距離，需要一個(gè)數(shù)組int[] distTo記錄距離。可以和數(shù)組 boolean[] marked 進(jìn)行合并 。
distTo[] 初始值設(shè)為-1，表示未被尋訪。一旦被尋訪到，就改為其到頂點(diǎn)的距離。

改動(dòng)

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

環(huán)計(jì)算，尋訪到一個(gè)已經(jīng)被尋訪過(guò)的頂點(diǎn)，即說(shuō)明出現(xiàn)了環(huán)。

異常拋出問(wèn)題還不是很熟練，故未對(duì)圖非連通的情況進(jìn)行判別拋出異常

import java.util.*;

public class GraphProperties {
    //private懶得寫(xiě)了
    int[] distTo; //到頂點(diǎn)的距離
    int[] e; //離心率
    int[] c; //cycle
    int[] edgeTo; //前任（是誰(shuí)牽著你的手走到這條路？）
    
    int diameter = 0;
    int radius = Integer.MAX_VALUE;
    int center;
    int girth = Integer.MAX_VALUE;
    
    //異常拋出問(wèn)題還不是很熟練，先不考慮
    GraphProperties(Graph G) {
        int V = G.V();
        distTo = new int[V];
        e = new int[V];
        c = new int[V];
        edgeTo = new int[V];
        
        //遍歷所有的頂點(diǎn)，造v棵樹(shù)
        for (int v = 0; v < V; v++) { 
            bfp(G, v);
        }
        
        //找各個(gè)最大最小值，各找各媽，各賦各值
        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，表示未被尋訪過(guò)
        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) { //如果未被尋訪過(guò)
                    distTo[w] = distTo[v] + 1; //記錄距離
                    eccen = distTo[w]; //這是深度優(yōu)先算法，因此最后一個(gè)被尋訪的深度就是最深的
                } else if ( w!= edgeTo[v] ) { //遇到一個(gè)尋訪過(guò)的w，就說(shuō)明牽著現(xiàn)在老婆的手遇到了前女朋友，人生兜兜轉(zhuǎn)轉(zhuǎn)形成了一個(gè)環(huán)（前提是你遇到的不是你老婆）
                    int d = distTo[w] + distTo[v] + 1; //算一下繞了多大的一個(gè)圈
                    cycle = d < cycle ? d : cycle; //記錄最小的那個(gè)圈，走最小的套路
                }
            }
        }
        e[s] = eccen;
        c[s] = cycle;
    }

    // diameter of G 圖的直徑：圖中所有點(diǎn)的離心率的最大值。
    public int diameter() {
        return diameter;
    }

    // radius of G 圖的半徑：圖中所有點(diǎn)的離心率的最小值。
    public int radius() {
        return radius;
    }

    // center of G 圖的中心：圖中離心率的最小值所對(duì)的頂點(diǎn)。
    public int center() {
        return center;
    }

    // grith of G 圖的圍長(zhǎng)：如果圖中有環(huán)，圍長(zhǎng)則為所有環(huán)的長(zhǎng)度的最小值。
    public int girth() {
        return girth;
    }

}

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

轉(zhuǎn)載請(qǐng)注明本文地址：http://systransis.cn/yun/66499.html

相關(guān)文章

  • 算法（第4版） Chapter 1

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

    Jacendfeng 評(píng)論0 收藏0

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

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

    android_c 評(píng)論0 收藏0

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

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

    Amio 評(píng)論0 收藏0

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

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

    Turbo 評(píng)論0 收藏0

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

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

    maybe_009 評(píng)論0 收藏0

發(fā)表評(píng)論

0條評(píng)論

最新活動(dòng)
閱讀需要支付1元查看
<