算法（第4版） Chapter 4.1 無向圖

kamushin233 發(fā)布于2019-08-14 17:14 / 1888人閱讀

摘要：邊僅由兩個頂點(diǎn)連接，并且沒有方向的圖稱為無向圖。用分隔符當(dāng)前為空格，也可以是分號等分隔。深度優(yōu)先算法最簡搜索起點(diǎn)構(gòu)造函數(shù)找到與起點(diǎn)連通的其他頂點(diǎn)。路徑構(gòu)造函數(shù)接收一個頂點(diǎn)，計(jì)算到與連通的每個頂點(diǎn)之間的路徑。

Algorithms Fourth Edition
Written By Robert Sedgewick & Kevin Wayne
Translated By 謝路云
Chapter 4 Section 1 無向圖

以下內(nèi)容修改自
http://www.cnblogs.com/skyivb...
http://www.cnblogs.com/yangec...
http://blog.csdn.net/yafeicha...

無向圖的建立 無向圖的定義

圖是若干個頂點(diǎn)(Vertices)和邊(Edges)相互連接組成的。邊僅由兩個頂點(diǎn)連接，并且沒有方向的圖稱為無向圖。在研究圖之

前，有一些定義需要明確，下圖中表示了圖的一些基本屬性的含義，這里就不多說明。

無向圖API

數(shù)據(jù)結(jié)構(gòu)

鄰接列表

鄰接矩陣空間V^2

邊的數(shù)組要實(shí)現(xiàn)adj()，即要知道一個頂點(diǎn)和哪些頂點(diǎn)相鄰，需要遍歷每一個邊

對于非稠密的無向圖，標(biāo)準(zhǔn)表示是使用鄰接表，將無向圖的每個頂點(diǎn)的所有相鄰頂點(diǎn)都保存在該頂點(diǎn)對應(yīng)的元素所指向的一張

鏈表中。所有的頂點(diǎn)保存在一個數(shù)組中，使用這個數(shù)組就可以快速訪問給定頂點(diǎn)的鄰接頂點(diǎn)列表。下面就是非稠密無向圖的一

個例子

這種 Graph 的實(shí)現(xiàn)的性能有如下特點(diǎn)：

使用的空間和 V + E 成正比

添加一條邊所需的時間為常數(shù)

遍歷頂點(diǎn) v 的所有相鄰頂點(diǎn)所需的時間和 v 的度數(shù)成正比（處理每個相鄰頂點(diǎn)所需的時間為常數(shù)）
對于這些操作，這樣的特性已經(jīng)是最優(yōu)的了，已經(jīng)可以滿足圖處理應(yīng)用的需要。

Graph 代碼

public class Graph
{
  private final int V;        // number of vertices 頂點(diǎn)數(shù) 這個final值在構(gòu)造函數(shù)中初始化后就不能修改了。
  private int E;              // number of edges 邊數(shù)
  private Bag[] adj; // adjacency lists 鄰接表數(shù)組 將Bag替換成Stack也可以, adj.add()改為adj.push()。
  
  public Graph(int V)
  {
    this.V = V; this.E = 0;
    adj = (Bag[]) new Bag[V]; // Create array of lists.
    for (int v = 0; v < V; v++)        // Initialize all lists
      adj[v] = new Bag();     //   to empty.
  //由于 Java 語言固有的缺點(diǎn)，無法創(chuàng)建泛型數(shù)組，所以第 10 行中只能創(chuàng)建普通數(shù)組后強(qiáng)制轉(zhuǎn)型為泛型數(shù)組。這導(dǎo)致在編譯時出現(xiàn)警告信息。
  //由于 Java 語言固有的缺點(diǎn)，泛型的參數(shù)類型不能是原始數(shù)據(jù)類型，所以泛型的參數(shù)類型是 Integer，而不是 int 。這導(dǎo)致了一些性能損失。

  }

  public Graph(In in)
  {
    this(in.readInt());         // Read V and construct this graph.
    int E = in.readInt();       // Read E.
    for (int i = 0; i < E; i++)
    { // A an edge.
      int v = in.readInt();     // Read a vertex,
      int w = in.readInt();     //   read another vertex,
      addEdge(v, w);            //   and add edge connecting them.
    }
  }

  public int V() { return V; }
  public int E() { return E; }

  public void addEdge(int v, int w)
  {
    adj[v].add(w);  // Add w to v"s list.
    adj[w].add(v);  // Add v to w"s list.
    E++;
  }

  //這里為什么要返回Iterable？返回Stack或者Bag可以嗎？
  public Iterable adj(int v)
  { return adj[v]; }

  public String toString()
  {
    StringBuilder s = new StringBuilder(); //待研究 StringBuiler類
    String NEWLINE = System.getProperty("line.separator");
    s.append(V + " vertices, " + E + " edges" + NEWLINE);
    for (int v = 0; v < V; v++)
    {
      s.append(v + ": ");
      for (int w : adj[v]) s.append(w + " ");
      s.append(NEWLINE);
    }
    return s.toString();
  }
}

其他常用代碼

    // 深度 = 相鄰頂點(diǎn)的個數(shù)/連接邊的數(shù)量
    public static int degree(int v) {
        int degree = 0;
        for (int w : G.adj(v)) degree++;
            return degree;
    }
    
    // 最大深度
       public static int maxDegree(Graph G) {
        int max = 0;
        for (int v = 0; v < G.V(); v++)
            if (degree(G, v) > max) max = degree(G, v);
        return max;
    }
    
    // 平均深度 
    // 一個頂點(diǎn)的深度為和它相鄰的頂點(diǎn)數(shù)=連接它的邊數(shù)
    // 平均深度=求和（每個頂點(diǎn)的邊數(shù)）/頂點(diǎn)數(shù) = 2E/V
    public static int avgDegree(Graph G) {
        return 2 * G.E() / G.V();
    }

    //自環(huán)數(shù)
    public static int numberOfSelfLoops(Graph G) {
        int count = 0;
        for (int v = 0; v < G.V(); v++)
            for (int w : G.adj(v))
                if (v == w) count++;
        return count / 2; // each edge counted twice
    }

復(fù)雜度

符號圖

引入符號圖是因?yàn)椋旤c(diǎn)更多的不是數(shù)字表示，而是由字符串表示，因此要做一個映射

符號圖API

實(shí)現(xiàn)

三種數(shù)據(jù)結(jié)構(gòu)

符號表 st 鍵為String（頂點(diǎn)字符串名字），值為int(索引數(shù)字）

數(shù)組keys[] 反向索引（通過數(shù)字反過來找到字符串）

圖對象G

SymbolGraph 代碼

輸入數(shù)據(jù)格式
A B
A D
D E
D B
...
每一行表示一條邊，每一行的兩個字符串表示連接邊的兩個頂點(diǎn)。用分隔符（當(dāng)前為空格，也可以是分號等）分隔。
（Graph的創(chuàng)建可以直接使用符號表，而不使用Bag，使得不需要遍歷文件兩次。待補(bǔ)充。詳情可見An Introduction to Programming in Java: An Interdisciplinary Approach.）

public class SymbolGraph {
    private ST st; // String -> index 就是個Map
    private String[] keys; // index -> String 就是個反向Map
    private Graph G; // the graph

    public SymbolGraph(String stream, String sp) { //stream是文件名，sp是分隔符
        //下面這一段就是遍歷一遍文件，得到所有頂點(diǎn)的字符串名，放進(jìn)Map里。然后再建立一個數(shù)組（反向Map）。這樣就建立了字符串和數(shù)字的雙向映射關(guān)系。
        st = new ST();
        In in = new In(stream); // First pass 
        while (in.hasNextLine()) // builds the index
        {
            String[] a = in.readLine().split(sp); // by reading strings
            for (int i = 0; i < a.length; i++) // to associate each
                if (!st.contains(a[i])) // distinct string
                    st.put(a[i], st.size()); // with an index.
        }
        keys = new String[st.size()]; // Inverted index
        for (String name : st.keys()) // to get string keys
            keys[st.get(name)] = name; // is an array.
        
        
        G = new Graph(st.size());
        in = new In(stream); // Second pass
        while (in.hasNextLine()) // builds the graph
        {
            String[] a = in.readLine().split(sp); // by connecting the
            int v = st.get(a[0]); // first vertex
            for (int i = 1; i < a.length; i++) // on each line
                G.addEdge(v, st.get(a[i])); // to all the others.
        }
    }

    public boolean contains(String s) {
        return st.contains(s);
    }

    public int index(String s) {
        return st.get(s);
    }

    public String name(int v) {
        return keys[v];
    }

    public Graph G() {
        return G;
    }
}

深度優(yōu)先算法 最簡搜索API

int s：起點(diǎn)
構(gòu)造函數(shù)：找到與起點(diǎn)連通的其他頂點(diǎn)。在圖中從起點(diǎn)開始沿著路徑到達(dá)其他頂點(diǎn)，并標(biāo)記每個路過的頂點(diǎn)。
方法marked(int v)：判斷s是否和v相連通
方法count(): 有多少個頂點(diǎn)和起點(diǎn)相連？（類似于G.adj(s)的個數(shù)）

引入：迷宮探索

在談?wù)撋疃葍?yōu)先算法之前，我們可以先看看迷宮探索問題。下面是一個迷宮和圖之間的對應(yīng)關(guān)系：
迷宮中的每一個交會點(diǎn)代表圖中的一個頂點(diǎn)，每一條通道對應(yīng)一個邊。

迷宮探索可以采用Trémaux繩索探索法。即：

在身后放一個繩子

訪問到的每一個地方放一個繩索標(biāo)記訪問到的交會點(diǎn)和通道

當(dāng)遇到已經(jīng)訪問過的地方，沿著繩索回退到之前沒有訪問過的地方：

圖示如下：

下面是迷宮探索的一個小動畫：

深度優(yōu)先搜索算法模擬迷宮探索。在實(shí)際的圖處理算法中，我們通常將圖的表示和圖的處理邏輯分開來。所以算法的整體設(shè)計(jì)

模式如下：

創(chuàng)建一個Graph對象

將Graph對象傳給圖算法處理對象，如一個Paths對象

然后查詢處理后的結(jié)果來獲取信息

算法思路

一條路子走到底，不到南門不回頭。

從一個頂點(diǎn)v出發(fā)，遍歷與自身相連通的頂點(diǎn)

在遍歷過程中，設(shè)當(dāng)前被遍歷的頂點(diǎn)為w

標(biāo)記w為已訪問

判斷w是否已經(jīng)被訪問

是，則繼續(xù)遍歷；

否，則搜索與頂點(diǎn)w相連通的頂點(diǎn)（即調(diào)用自身，開始關(guān)于頂點(diǎn)w的遍歷）

結(jié)束遍歷

DepthFirstSearch 代碼

下面是深度優(yōu)先的基本代碼，我們可以看到，遞歸調(diào)用dfs方法，在調(diào)用之前判斷該節(jié)點(diǎn)是否已經(jīng)被訪問過。

public class DepthFirstSearch{
    private boolean[] marked;
    private int count;

    public DepthFirstSearch(Graph G, int s) {
        marked = new boolean[G.V()];
        dfs(G, s);
    }

    private void dfs(Graph G, int v) {
        marked[v] = true;
        count++;
        for (int w : G.adj(v)) {
            if (!marked[w]) dfs(G, w);
        }
    }

    public boolean marked(int w) {
        return marked[w];
    }

    public int count() {
        return count;
    }
}

DFS簡單例子的追蹤

上圖中是黑色線條表示深度優(yōu)先搜索中，所有定點(diǎn)到原點(diǎn)0的路徑，他是通過edgeTo[]這個變量記錄的，可以從右邊可以看

出，他本質(zhì)是一顆樹，樹根即是原點(diǎn)，每個子節(jié)點(diǎn)到樹根的路徑即是從原點(diǎn)到該子節(jié)點(diǎn)的路徑。

深度優(yōu)先搜索標(biāo)記與起點(diǎn)連通的所有頂點(diǎn)所需要的時間和所有頂點(diǎn)的深度之和成正比。

無向圖的算法應(yīng)用 連通性

圖是否連通？
從概念上來說，如果一個圖是連通的，那么對于圖上面的任意兩個節(jié)點(diǎn)i, j來說，它們相互之間可以通過某個路徑連接到對方

兩個給定頂點(diǎn)是否連通？

連通分量API

實(shí)現(xiàn)1.
ConnectedComponents

算法思路
深度優(yōu)先搜索，依次建立一棵樹
其預(yù)處理時間和V+E成正比

ConnectedComponents 代碼

public class CC {
    public CC(Graph G) {
        marked = new boolean[G.V()];
        id = new int[G.V()];
        for (int s = 0; s < G.V(); s++) //從0開始遍歷
            if (!marked[s]) {
                dfs(G, s);
                count++; //如果dfs返回了，說明所有和0連通的都找完了。就開始找下一個連通的team了，因此count++
            }
    }
    
    private void dfs(Graph G, int v) {
        marked[v] = true;
        id[v] = count; //新加 保存id
        for (int w : G.adj(v))
            if (!marked[w]) dfs(G, w);
    }
    
    public boolean connected(int v, int w) {
        return id[v] == id[w];
    }
    
    public int id(int v) {
        return id[v];
    }
    
    public int count() {
        return count;
    }

實(shí)現(xiàn)2.
UnionFind 詳情請見Chapter 1.5

尋找路徑

給定一副圖G和一個頂點(diǎn)s，從s到給定頂點(diǎn)v是否存在一條路徑？如果有，找出這條路徑。

路徑API

構(gòu)造函數(shù)接收一個頂點(diǎn)s，計(jì)算s到與s連通的每個頂點(diǎn)之間的路徑。
現(xiàn)在暫時查找所有路徑。

DepthFirstPaths 代碼

和DepthFirstSearch幾乎一致。
只是添加了路徑的記錄數(shù)組int[] edgeTo

public class DepthFirstPaths {
    private boolean[] marked;
    private int[] edgeTo; //新加。第一次訪問頂點(diǎn)v的頂點(diǎn)為w。 edgeTo[v]=w 
    private final int s;  //新加。把圖變成樹，構(gòu)造時的頂點(diǎn)s為樹的根結(jié)點(diǎn)為s
    // private int count; 被刪去了
    
    public DepthFirstPaths (Graph G, int s) {
        this.s = s;
        marked = new boolean[G.V()];
        edgeTo = new int[G.V()];
        dfs(G, s);
    }

    private void dfs(Graph G, int v) {
        // count++;
        marked[v] = true;
        for (int w : G.adj(v)) {
            if (!marked[w]) {
                edgeTo[w] = v; //新加，記錄路徑
                dfs(G, w);
            }
        }
    }

    // 圖變成了樹，樹的根為s
    // 圖被扔掉了，以樹的形式保留在數(shù)組里了
    public boolean hasPathTo(int v) {
        return marked[v];
    }

    public Iterable pathTo(int v) {
        if (!hasPathTo[v]) return null;
        Stack path = new Stack();
        for (int w = v; w != s; w = edgeTo[w])
            path.push(w);
        path.push(s);
        return path;
    }
}

檢測環(huán)

給定的環(huán)是無環(huán)圖嗎？

假設(shè)沒有自環(huán)，并且兩個頂點(diǎn)間至多只有一條邊（即沒有平行邊）

Cycle 代碼

public class Cycle {
        private boolean[] marked;
        private boolean hasCycle;

    public Cycle(Graph G) {
        marked = new boolean[G.V()];
        for (int s = 0; s < G.V(); s++)
            if (!marked[s]) dfs(G, s, s);
    }

    private void dfs(Graph G, int v, int u) { // 新增參數(shù)u。這個team手把手帶你的師傅被遞歸進(jìn)去了。。。看上去很簡單，想起來很復(fù)雜。。。
        marked[v] = true;
        for (int w : G.adj(v))
            if (!marked[w]) dfs(G, w, v); // w是在前線小學(xué)徒，v是帶你入行的師傅
            else if (w != u) hasCycle = true; //在這里判斷，這個不等于的判斷是因?yàn)閣是從u過來的，因此要排除掉這個單向通道。
    }

    public boolean hasCycle() {
        return hasCycle;
    }
}

雙色問題

能夠用兩種顏色將所有頂點(diǎn)著色，使得任意一條邊的兩個頂點(diǎn)顏色不同嗎？
這個問題等價于，這是一個二分圖嗎？（什么叫二分圖？）

TwoColor 代碼

public class TwoColor {
    private boolean[] marked;
    private boolean[] color; //因?yàn)橹挥袃缮?，用boolean就可以了
    private boolean isTwoColorable = true;

    public TwoColor(Graph G) {
        marked = new boolean[G.V()];
        color = new boolean[G.V()];
        for (int s = 0; s < G.V(); s++)
            if (!marked[s]) dfs(G, s);
    }

    private void dfs(Graph G, int v) {
        marked[v] = true;
        for (int w : G.adj(v))
            if (!marked[w]) {
                color[w] = !color[v]; // 沒訪問過的賦個顏色
                dfs(G, w);
            } else if (color[w] == color[v]) isTwoColorable = false; //同色的話 就抱歉了 和環(huán)的問題有點(diǎn)像
    }

    public boolean isBipartite() {
        return isTwoColorable;
    }
}

廣度優(yōu)先搜索

單點(diǎn)最短路徑

給定一副圖G和一個頂點(diǎn)s，從s到給定頂點(diǎn)v是否存在一條路徑？如果有，找出其中最短（所含邊數(shù)最少）的路徑。

算法思路

五湖四海先識得，泛泛之交后深掘。

先進(jìn)先出Queue q。
給定頂點(diǎn)s

將v壓入q

大循環(huán)：彈出q直到q為空，當(dāng)前頂點(diǎn)為v

小循環(huán)：遍歷與v相鄰的所有頂點(diǎn)，當(dāng)前頂點(diǎn)為w

判斷w是否已訪問，如果未被訪問

標(biāo)記w為已訪問

壓入q

直到大循環(huán)q為空，循環(huán)結(jié)束。

BreadthFirstPaths 代碼

public class BreadthFirstPaths {

    private final int s;
    private boolean[] marked;
    private int[] edgeTo;

    BreadthFirstPaths (Graph G, int s) {
        marked = new boolean[G.V()];
        edgeTo = new int[G.V()];
        this.s = s;
        bfs(G, s);
    }

    public void bfs(Graph G, int s) {
        Queue q = new LinkedList();
        marked[s] = true;
        q.offer(s);
        while (!q.isEmpty()) {
            int v = q.poll();
            for (int w : G.adj(v)) 
                if (!marked[w]) {
                    marked[w] = true;
                    edgeTo[w] = v;
                    q.offer(w);
                }
        }
    }
}

待研究，隊(duì)列Queue q
q.add(); q.remove()會throw異常
q.offer();q.poll()好一些

待研究

StringBuiler類
Queue q q.offer() q.poll()

GPU云服務(wù)器云服務(wù)器 python 第4版 hadoop權(quán)威指南第4版 linux防火墻第4版無向圖鄰接表數(shù)

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

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

發(fā)表評論

登陸后可評論

0條評論

kamushin233

男|高級講師

我要關(guān)注我要私信

TA的文章

C/C++游戲項(xiàng)目：中國程序員一定要會的中國象棋教程

閱讀 2248·2021-11-18 10:02
虛擬主機(jī)一年需要多少錢

閱讀 3499·2021-11-15 11:36
veeValidate實(shí)戰(zhàn)

閱讀 1124·2019-08-30 14:03
Node.js運(yùn)行原理、高并發(fā)性能測試對比及生態(tài)圈匯總

閱讀 741·2019-08-30 11:08
CSS揭秘之《小技巧》

閱讀 2772·2019-08-29 13:20
2017年3月份前端資源分享

閱讀 3295·2019-08-29 12:34
偽類與偽元素

閱讀 1382·2019-08-28 18:30
Vue組件開發(fā)

閱讀 1648·2019-08-26 13:34

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

資訊專欄INFORMATION COLUMN

上云采購季！| 2核2G4M爆款云服務(wù)器低至59元/年，更有多臺、長期優(yōu)惠，快來選購！

算法（第4版） Chapter 4.1 無向圖

相關(guān)文章

**算法（第4版） Chapter 4.3 最小生成樹**

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

算法第四版4.1-無向圖詳解

「中高級前端」窺探數(shù)據(jù)結(jié)構(gòu)的世界- ES6版

發(fā)表評論

0條評論

kamushin233

男|高級講師

TA的文章

C/C++游戲項(xiàng)目：中國程序員一定要會的中國象棋教程

虛擬主機(jī)一年需要多少錢

veeValidate實(shí)戰(zhàn)

Node.js運(yùn)行原理、高并發(fā)性能測試對比及生態(tài)圈匯總

CSS揭秘之《小技巧》

2017年3月份前端資源分享

偽類與偽元素

Vue組件開發(fā)

最新活動

資訊專欄INFORMATION COLUMN

上云采購季！| 2核2G4M爆款云服務(wù)器低至59元/年，更有多臺、長期優(yōu)惠，快來選購！

算法（第4版） Chapter 4.1 無向圖

相關(guān)文章

發(fā)表評論

0條評論

男|高級講師

TA的文章

最新活動

上云采購季！| 2核2G4M爆款云服務(wù)器低至59元/年，更有多臺、長期優(yōu)惠，快來選購！