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

kamushin233 發布于2019-08-14 17:14 / 1881人閱讀

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

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

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

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

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

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

無向圖API

數據結構

鄰接列表

鄰接矩陣空間V^2

邊的數組要實現adj()，即要知道一個頂點和哪些頂點相鄰，需要遍歷每一個邊

對于非稠密的無向圖，標準表示是使用鄰接表，將無向圖的每個頂點的所有相鄰頂點都保存在該頂點對應的元素所指向的一張

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

個例子

這種 Graph 的實現的性能有如下特點：

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

添加一條邊所需的時間為常數

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

Graph 代碼

public class Graph
{
  private final int V;        // number of vertices 頂點數 這個final值在構造函數中初始化后就不能修改了。
  private int E;              // number of edges 邊數
  private Bag[] adj; // adjacency lists 鄰接表數組 將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 語言固有的缺點，無法創建泛型數組，所以第 10 行中只能創建普通數組后強制轉型為泛型數組。這導致在編譯時出現警告信息。
  //由于 Java 語言固有的缺點，泛型的參數類型不能是原始數據類型，所以泛型的參數類型是 Integer，而不是 int 。這導致了一些性能損失。

  }

  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();
  }
}

其他常用代碼

    // 深度 = 相鄰頂點的個數/連接邊的數量
    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;
    }
    
    // 平均深度 
    // 一個頂點的深度為和它相鄰的頂點數=連接它的邊數
    // 平均深度=求和（每個頂點的邊數）/頂點數 = 2E/V
    public static int avgDegree(Graph G) {
        return 2 * G.E() / G.V();
    }

    //自環數
    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
    }

復雜度

符號圖

引入符號圖是因為，頂點更多的不是數字表示，而是由字符串表示，因此要做一個映射

符號圖API

實現

三種數據結構

符號表 st 鍵為String（頂點字符串名字），值為int(索引數字）

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

圖對象G

SymbolGraph 代碼

輸入數據格式
A B
A D
D E
D B
...
每一行表示一條邊，每一行的兩個字符串表示連接邊的兩個頂點。用分隔符（當前為空格，也可以是分號等）分隔。
（Graph的創建可以直接使用符號表，而不使用Bag，使得不需要遍歷文件兩次。待補充。詳情可見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是分隔符
        //下面這一段就是遍歷一遍文件，得到所有頂點的字符串名，放進Map里。然后再建立一個數組（反向Map）。這樣就建立了字符串和數字的雙向映射關系。
        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;
    }
}

深度優先算法 最簡搜索API

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

引入：迷宮探索

在談論深度優先算法之前，我們可以先看看迷宮探索問題。下面是一個迷宮和圖之間的對應關系：
迷宮中的每一個交會點代表圖中的一個頂點，每一條通道對應一個邊。

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

在身后放一個繩子

訪問到的每一個地方放一個繩索標記訪問到的交會點和通道

當遇到已經訪問過的地方，沿著繩索回退到之前沒有訪問過的地方：

圖示如下：

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

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

模式如下：

創建一個Graph對象

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

然后查詢處理后的結果來獲取信息

算法思路

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

從一個頂點v出發，遍歷與自身相連通的頂點

在遍歷過程中，設當前被遍歷的頂點為w

標記w為已訪問

判斷w是否已經被訪問

是，則繼續遍歷；

否，則搜索與頂點w相連通的頂點（即調用自身，開始關于頂點w的遍歷）

結束遍歷

DepthFirstSearch 代碼

下面是深度優先的基本代碼，我們可以看到，遞歸調用dfs方法，在調用之前判斷該節點是否已經被訪問過。

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簡單例子的追蹤

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

出，他本質是一顆樹，樹根即是原點，每個子節點到樹根的路徑即是從原點到該子節點的路徑。

深度優先搜索標記與起點連通的所有頂點所需要的時間和所有頂點的深度之和成正比。

無向圖的算法應用 連通性

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

兩個給定頂點是否連通？

連通分量API

實現1.
ConnectedComponents

算法思路
深度優先搜索，依次建立一棵樹
其預處理時間和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;
    }

實現2.
UnionFind 詳情請見Chapter 1.5

尋找路徑

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

路徑API

構造函數接收一個頂點s，計算s到與s連通的每個頂點之間的路徑。
現在暫時查找所有路徑。

DepthFirstPaths 代碼

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

public class DepthFirstPaths {
    private boolean[] marked;
    private int[] edgeTo; //新加。第一次訪問頂點v的頂點為w。 edgeTo[v]=w 
    private final int s;  //新加。把圖變成樹，構造時的頂點s為樹的根結點為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
    // 圖被扔掉了，以樹的形式保留在數組里了
    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;
    }
}

檢測環

給定的環是無環圖嗎？

假設沒有自環，并且兩個頂點間至多只有一條邊（即沒有平行邊）

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) { // 新增參數u。這個team手把手帶你的師傅被遞歸進去了。。。看上去很簡單，想起來很復雜。。。
        marked[v] = true;
        for (int w : G.adj(v))
            if (!marked[w]) dfs(G, w, v); // w是在前線小學徒，v是帶你入行的師傅
            else if (w != u) hasCycle = true; //在這里判斷，這個不等于的判斷是因為w是從u過來的，因此要排除掉這個單向通道。
    }

    public boolean hasCycle() {
        return hasCycle;
    }
}

雙色問題

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

TwoColor 代碼

public class TwoColor {
    private boolean[] marked;
    private boolean[] color; //因為只有兩色，用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; //同色的話 就抱歉了 和環的問題有點像
    }

    public boolean isBipartite() {
        return isTwoColorable;
    }
}

廣度優先搜索

單點最短路徑

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

算法思路

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

先進先出Queue q。
給定頂點s

將v壓入q

大循環：彈出q直到q為空，當前頂點為v

小循環：遍歷與v相鄰的所有頂點，當前頂點為w

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

標記w為已訪問

壓入q

直到大循環q為空，循環結束。

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);
                }
        }
    }
}

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

待研究

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

GPU云服務器云服務器 python 第4版 hadoop權威指南第4版 linux防火墻第4版無向圖鄰接表數

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

轉載請注明本文地址：http://specialneedsforspecialkids.com/yun/66502.html

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

摘要：算法圖示代碼復雜度時間初始化優先隊列，最壞情況次比較每次操作成本次比較，最多還會多次和次操作，但這些成本相比的增長數量級可忽略不計詳見空間 Algorithms Fourth EditionWritten By Robert Sedgewick & Kevin WayneTranslated By 謝路云Chapter 4 Section 3 最小生成樹定義樹是特殊的圖圖的生...

asoren 2019-08-14 17:16 評論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
算法第四版4.1-無向圖詳解

摘要：樹是一副無環連通圖。互不相連的樹組成的集合稱為森林。表示無向圖的數據類型圖的基本操作的兩個構造，得到頂點數和邊數，增加一條邊。該方法不符合第一個條件，上百萬個頂點的圖是很常見的空間不滿足。四種重要的圖模型：無向圖（簡單連接）有向圖（連接有方向性）加權圖（連接帶有權值）加權有向圖（連接既有方向性又帶有權值）無向圖定義：由一組頂點和一組能夠將兩個頂點相連的邊組成。特殊：...

scola666 2019-08-14 17:53 評論0 收藏0
「中高級前端」窺探數據結構的世界- ES6版

摘要：單鏈表與雙向鏈表單鏈表是表示一系列節點的數據結構，其中每個節點指向列表中的下一個節點。且分別稱為該結點的左子樹與右子樹。由于二叉樹是非線性結構，因此，樹的遍歷實質上是將二叉樹的各個結點轉換成為一個線性序列來表示。1. 什么是數據結構？數據結構是在計算機中組織和存儲數據的一種特殊方式，使得數據可以高效地被訪問和修改。更確切地說，數據結構是數據值的集合，表示數據之間的關系，也包括了作用在數據上...

Lucky_Boy 2019-05-22 10:29 評論0 收藏0