java - 如何在有向图中找到坑？

Question

问题：我们有一个有向图，如何在 Ɵ(n) 时间复杂度的图中找到一个洞（坑）。

图上的一个坑：如果一个顶点的（输入）度数为 n-1，（输出）度数为 0，我们在图上就有一个坑。

Answer 1

我错过了什么吗？不要沿着图形边缘搜索图形。只需遍历图中的所有 n 个顶点并测试每个顶点的传入和传出边数。我假设对于每个顶点，您可以存储传入和传出边的计数。如果你有边缘计数，这将缩放 O(n)。

@REPLY：我们必须知道您的图表是如何实现的才能更具体。但我的意思是：

foreach( node in graph )
     if (( node.numberInputEdges == numNodes -1 ) && 
         ( node.numberOutputEdges == 0 ))
         print ( "this node is a pit" )

Answer 2

我认为您根本不需要搜索图表。您可以只计算每个节点的入度和出度。你只需要寻找一个节点的哪个节点入度是（n-1）并且出度是'0'。

考虑到您知道“有多少边”。

int outdegree[n]={0}; // Storing outdegree of each node
int indegree[n]={0}; /// Storing indegree of each node


 while(m--)  // m is number of edges
 {
    scanf("%d %d",&a,&b);  // this means there is an edge from 'a' to 'b'. a-->b
    outdegree[a]++;
    indegree[b]++;
 }
 int sink;  
 for(i=1;i<=n;i++)
 {
    if((outdegree[i]==0 )&& (indegree[i]==(n-1)))
        sink=i;
 }
 cout<<"Sink/Pit is: "<<sink<<endl;

Answer 3

如果你有一个邻接列表实现，只需扫描它，你会在 O(n) 时间内找到，如果有一个出度为 0 的顶点。如果你有一个邻接矩阵，你可以使用 DFS。

在 DFS 中，只要我们找到一个传出节点，只需增加计数器的度数。

伪代码：

for each adjacent node :
   indegree->neighbour ++;
   if (neighbour not visited ) dfs(neighbour)   

最后扫描入度数组以获取哪个节点具有入度 (n-1) ，因为每个节点都会有一条到 Pit 的边缘。

Answer 4

图中只能有一个“坑”（因为 deg_in = N-1）。所以搜索所有 deg_out = 0 的节点。如果两个，停止。如果有，请检查 deg_in。这是 O(N)。