2012-11-16 73 views
3

程序的輸入是圖中邊的集合。對於例如考慮下面的簡單有向圖:如何確定給定的有向圖是否爲樹

a -> b -> c 

此圖的邊集是

{ (b, c), (a, b) } 

因此,考慮有向圖的邊集,你怎麼判斷是否有向圖是樹?如果它是一棵樹,樹的根節點是什麼?

我首先看着你將如何表示這個圖,鄰接表/鄰接矩陣/其他任何東西?如何利用您選擇的表示方式有效回答上述問題?

編輯1:

有些人mentoning有關使用DFS進行循環檢測,但問題是,從啓動該節點DFS。由於它是有向圖,我們不能從隨機節點開始DFS,例如如果我從頂點'c'開始一個DFS,它將不會繼續前進,因爲沒有後邊緣可以到達任何其他節點。後續的問題應該是你如何確定這棵樹的根源。

+0

上班?面試問題? –

+0

可能重複的[如何檢測有向圖是否循環?](http://stackoverflow.com/questions/2525282/how-to-detect-if-a-directed-graph-is-cyclic) –

+0

只是一個注意:由於原始圖形是定向的,要使用以下人員描述的算法,您需要將邊緣視爲無向/雙向。 – nhahtdh

回答

3

從根開始,「標記」它,然後去所有的孩子,並遞歸地重複。如果你到達一個已經標記的孩子,這意味着它不是一棵樹...

+3

你如何「從根開始」?你沒有得到根。 –

+0

好吧......你需要找到一個沒有父母的節點,並稱之爲「根」......你還需要確保你標記了所有的節點,因爲它可能不是一棵樹,而是一片森林...... –

+2

實際上,如果你考慮它,只要你確定你標記了所有的節點,你就可以從任何節點開始...... –

1

注意:絕不是最有效的方式,但在概念上有用。有時候你想要效率,有時候你想出於教學原因的另一種觀點。這當然是後者。

算法:與尺寸n的鄰接矩陣A開始。以矩陣電源A**n。如果矩陣對於每個條目都爲零,則知道它至少是樹木的集合(森林)。如果你能證明它已連接,那麼它必須是一棵樹。查看Nilpotent matrix。瞭解更多信息。

要找到根節點,我們假設您已經顯示該圖形是連接的樹。假設k是在矩陣全部爲零之前必須提高功率A**k的次數。轉置到(k-1)電源A.T ** (k-1)。唯一的非零條目必須是根。

分析:粗略的最壞情況的分析表明,它是由以上O(n^4),三爲矩陣乘法最多n時間爲界。你可以通過對矩陣進行對角化來實現更好的效果,該矩陣可以將其降至O(n^3)。考慮到這個問題can be doneO(n), O(1)時間/空間這只是一個有用的練習邏輯和理解問題。

+0

_Nilpotent_並不意味着「全零」。如果「A ** k = 0」,那麼「A」本身就是[無效](http://en.wikipedia.org/wiki/Nilpotent_matrix)。 –

+0

@TedHopp我同意,但矩陣是冪零的想法與圖中的循環的存在有關。爲了清晰起見,我會對其進行編輯 – Hooked

8

這是一個相當直接的方法。它可以通過鄰接矩陣或邊界列表完成。

  1. 查找不作爲任何邊緣的目的地出現的節點集合R.如果R不具有一個成員,則該圖不是樹。

  2. 如果R確實有一個成員r,則它是唯一可能的根。

  3. Mark r。

  4. 從r開始,遞歸地標記可以通過從源到目的地的後續邊緣到達的所有節點。如果任何節點已被標記,則有一個循環,並且該圖不是樹。 (這一步與之前發佈的答案相同)。

  5. 如果在步驟3結束時未標記任何節點,則該圖不是樹。

如果沒有這些步驟,發現該圖是不是樹,圖形與R爲根的樹。

如果沒有關於節點和邊的數量的信息,很難知道什麼是高效的。

+0

我正在考慮類似的路線。我用鄰接表來存儲圖形,因爲我一次可以處理1個邊,並建立列表。 – user824212

4

有3個屬性,以檢查是否一個圖是樹:比頂點的數目

  • (1)的邊緣的曲線圖中的數正好是一個小於| E | = | V | - 1
  • (2)沒有周期
  • (3)圖是連通

我認爲本實施例中的算法可以在有向圖的情況下工作:

​​

來源: 算法由S. Dasgupta,CH Papadimitriou和U.V. Vazirani http://www.cs.berkeley.edu/~vazirani/algorithms.html

+0

我想知道...是否足以驗證屬性1和3?我沒有拿出一個具有屬性1和3並且仍然是循環的圖的示例... – Juan

1

對於有向圖,如果無向圖是非循環且完全連通的,則底層無向圖將成爲樹。如果對於有向圖,相同的屬性保持良好,每個頂點具有in-degree = 1,除了具有in-degree = 0的一個頂點。

如果鄰接表表示還支持每個頂點的入度屬性,那麼我們可以很容易地應用上述規則。否則,我們應該使用調整後的DFS爲底層無向圖找到無迴路以及| E | = | V | -1。

1

以下是我爲此編寫的代碼。隨意建議優化。

import java.util.*; 
import java.lang.*; 
import java.io.*; 

class Graph 
{ 
private static int V; 
private static int adj[][]; 

static void initializeGraph(int n) 
{ 
    V=n+1; 
    adj = new int[V][V]; 
    for(int i=0;i<V;i++) 
    { 
     for(int j=0;j<V ;j++) 
     adj[i][j]= 0; 
    } 

} 

static int isTree(int edges[][],int n) 
{ 
    initializeGraph(n); 

    for(int i=0;i< edges.length;i++) 
    { 
     addDirectedEdge(edges[i][0],edges[i][1]); 
    } 

    int root = findRoot(); 
    if(root == -1) 
    return -1; 
    boolean visited[] = new boolean[V]; 
    boolean isTree = isTree(root, visited, -1); 
    boolean isConnected = isConnected(visited); 
    System.out.println("isTree= "+ isTree + " isConnected= "+ isConnected); 
    if(isTree && isConnected) 
    return root; 
    else 
    return -1; 

} 

static boolean isTree(int node, boolean visited[], int parent) 
{ 
// System.out.println("node =" +node +" parent" +parent); 
    visited[node] = true;int j; 

    for(j =1;j<V;j++) 
    { 
    // System.out.println("node =" +node + " j=" +j+ "parent" + parent); 
     if(adj[node][j]==1) 
     { 
      if(visited[j]) 
      { 
      // System.out.println("returning false for j="+ j); 
       return false; 
      } 
      else 
      { //visit all adjacent vertices 
       boolean child = isTree(j, visited, node); 
       if(!child) 
       { 
       // System.out.println("returning false for j="+ j + " node=" +node); 
        return false; 
       } 
      } 

     } 
    } 
    if(j==V) 
    return true; 
    else 
    return false; 
} 

static int findRoot() 
{ 
    int root =-1, j=0,i; 
    int count =0; 
    for(j=1;j<V ;j++) 
    { 
     count=0; 
     for(i=1 ;i<V;i++) 
     { 
      if(adj[i][j]==1) 
      count++; 
     } 
    // System.out.println("j"+j +" count="+count); 
     if(count==0) 
     { 
     // System.out.println(j); 
      return j; 
     } 
    } 
    return -1; 
} 

static void addDirectedEdge(int s, int d) 
{ 
// System.out.println("s="+ s+"d="+d); 
    adj[s][d]=1; 
} 

static boolean isConnected(boolean visited[]) 
{ 
    for(int i=1; i<V;i++) 
    { 
     if(!visited[i]) 
     return false; 
    } 
    return true; 
} 

public static void main (String[] args) throws java.lang.Exception 
{ 
    int edges[][]= {{2,3},{2,4},{3,1},{3,5},{3,7},{4,6}, {2,8}, {8,9}}; 
    int n=9; 
    int root = isTree(edges,n); 
    System.out.println("root is:" + root); 

    int edges2[][]= {{2,3},{2,4},{3,1},{3,5},{3,7},{4,6}, {2,8}, {6,3}}; 
    int n2=8; 
    root = isTree(edges2,n2); 
    System.out.println("root is:" + root); 
    } 
}