3

プログラムへの入力は、グラフのエッジのセットです。たとえば、次の単純な有向グラフを考えてみましょう。

a -> b -> c

このグラフのエッジのセットは次のとおりです。

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

では、有向グラフをエッジのセットとして考えると、有向グラフがツリーであるかどうかをどのように判断しますか？ツリーの場合、ツリーのルートノードは何ですか？

まず、このグラフ、隣接リスト/隣接行列/その他をどのように表現するかを検討しています。上記の質問に効率的に答えるために、選択した表現をどのように活用しますか？

編集1：

サイクル検出にDFSを使用することについて言及している人もいますが、問題はどのノードからDFSを開始するかです。これは有向グラフであるため、ランダムノードからDFSを開始することはできません。たとえば、頂点'c'からDFSを開始した場合、他のノードに移動するバックエッジがないため、それ以上先に進みません。ここでのフォローアップの質問は、このツリーのルートが何であるかをどのように判断するかです。

4

6 に答える 6

9

これはかなり直接的な方法です。これは、隣接行列またはエッジ リストのいずれかを使用して実行できます。

  1. どのエッジの宛先としても表示されないノードの集合 R を見つけます。R のメンバーが 1 つだけでない場合、グラフはツリーではありません。

  2. R がメンバー r を 1 つだけ持つ場合、それが可能な唯一のルートです。

  3. マーク R.

  4. r から開始して、ソースから宛先までエッジをたどって到達できるすべてのノードを再帰的にマークします。いずれかのノードが既にマークされている場合、循環があり、グラフはツリーではありません。(この手順は、以前に投稿された回答と同じです)。

  5. 手順 3 の最後でノードがマークされていない場合、グラフはツリーではありません。

これらのステップでグラフがツリーではないことが判明した場合、グラフは r をルートとするツリーです。

ノードとエッジの数に関する情報がなければ、何が効率的かを知ることは困難です。

于 2012-11-16T03:04:34.797 に答える
4

グラフがツリーであるかどうかを確認するための 3 つのプロパティがあります。

  • (1) グラフの辺の数は、頂点の数 |E| よりちょうど 1 つ少ない。= |V| - 1
  • (2) サイクルがない
  • (3) グラフがつながる

この例のアルゴリズムは、有向グラフの場合に機能すると思います。

 # given a graph and a starting vertex, check if the graph is a tree
 def checkTree(G, v):

    # |E| = |V| - 1
    if edges.size != vertices.size - 1:
        return false;

    for v in vertices:
        visited[v] = false;

    hasCycle = explore_and_check_cycles(G, v);

    # a tree is acyclic
    if hasCycle:
        return false;

    for v in vertices:
        if not visited[v]: # the graph isn't connected
            return false;

    # otherwise passes all properties for a tree
    return true;

# given a Graph and a vertex, explore all reachable vertices from the vertex
# and returns true if there are any cycles
def explore_and_check_cycles(G, v):
    visited[v] = true;

    for (v, u) in edges:
        if not visited[u]:
            return explore_and_check_cyles(G, u)
        else: # a backedge between two vertices indicates a cycle
            return true

    return false

出典: S. Dasgupta、CH Papadimitriou、および UV Vazirani によるアルゴリズム http://www.cs.berkeley.edu/~vazirani/algorithms.html

于 2013-02-25T17:10:16.260 に答える
3

ルートから開始し、それを「マーク」してから、すべての子に移動し、再帰的に繰り返します。すでにマークされている子供に到達した場合、それは木ではないことを意味します...

于 2012-11-16T02:09:08.437 に答える
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);
   }
}
于 2016-11-22T16:03:13.933 に答える
1

有向グラフの場合、無向グラフが非循環で完全に接続されている場合、基になる無向グラフはツリーになります。有向グラフの場合、各頂点がイン次数 = 0 を除いてイン次数 = 1 である場合、同じプロパティが適切に保持されます。

隣接リスト表現も各頂点の次数プロパティをサポートする場合、上記のルールを簡単に適用できます。それ以外の場合は、調整された DFS を適用して、基になる無向グラフと |E|=|V|-1 のループがないことを見つける必要があります。

于 2016-09-04T12:38:54.907 に答える
1

注: 決して最も効率的な方法ではありませんが、概念的には役立ちます。効率が必要な場合もあれば、教育上の理由から別の視点が必要な場合もあります。これは間違いなく後者です。

アルゴリズム:Aサイズの隣接行列から開始しますn。行列べき乗を取りA**nます。すべてのエントリの行列がゼロの場合、それは少なくとも木の集まり (森) であることがわかります。接続されていることを示すことができれば、それはツリーに違いありません。冪零行列を参照してください。詳細については。

ルート ノードを見つけるために、グラフが接続されたツリーであることを示したと仮定します。行列がすべてゼロになる前にべき乗kを上げる必要がある回数をとします。A**k転置を(k-1)べき乗しA.T ** (k-1)ます。唯一のゼロ以外のエントリはルートでなければなりません。

分析:大まかな最悪のケースの分析ではO(n^4)、ほとんどの場合、行列の乗算が , 3 で制限されていることが示されていnます。に下げる必要がある行列を対角化することで、より良い結果が得られO(n^3)ます。この問題は時間/空間で実行できることを考えると、これO(n), O(1)は論理と問題の理解における有用な演習にすぎません。

于 2012-11-16T02:16:15.747 に答える