3

程序的输入是图中的一组边。例如，考虑以下简单的有向图：

a -> b -> c

该图的边集是

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

所以给定一个有向图作为一组边，你如何确定有向图是否是一棵树？如果是树，树的根节点是什么？

首先我要看看你将如何表示这个图，邻接列表/邻接矩阵/其他任何东西？将如何利用您选择的表示来有效地回答上述问题？

编辑1：

有些人正在谈论使用 DFS 进行循环检测，但问题是从哪个节点启动 DFS。由于它是一个有向图，我们不能从随机节点启动 DFS，例如，如果我从顶点“c”启动 DFS，它将不会继续进行，因为没有后边可以到达任何其他节点。这里的后续问题应该是如何确定这棵树的根。

4

6 回答 6

9

这是一个相当直接的方法。它可以使用邻接矩阵或边列表来完成。

  1. 找到不作为任何边的目的地出现的节点集合 R。如果 R 没有恰好一个成员，则图不是树。

  2. 如果 R 确实只有一个成员 r，它是唯一可能的根。

  3. 马克河。

  4. 从 r 开始，递归地标记所有可以通过从源到目标的边到达的节点。如果任何节点已被标记，则存在一个循环，并且该图不是树。（此步骤与之前发布的答案相同）。

  5. 如果在第 3 步结束时没有标记任何节点，则该图不是树。

如果这些步骤都没有发现图不是树，那么图就是以 r 为根的树。

如果没有关于节点和边数的一些信息，很难知道什么是有效的。

于 2012-11-16T03:04:34.797 回答
4

有 3 个属性可以检查图是否为树：

  • (1) 图中的边数正好比顶点数|E|少一 = |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

注意：绝不是最有效的方法，但在概念上很有用。有时您需要效率，有时您出于教学原因需要另一种观点。这肯定是后者。

算法：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 回答
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

对于有向图，如果无向图是无环且全连接的，则底层无向图将是一棵树。对于有向图，如果每个顶点的入度 = 1，除了一个入度 = 0 的顶点外，相同的属性也适用。

如果邻接表表示也支持每个顶点的入度属性，那么我们可以很容易地应用上述规则。否则，我们应该应用调整后的 DFS 来找到底层无向图以及 |E|=|V|-1 的无环。

于 2016-09-04T12:38:54.907 回答