我有一个带有n节点的图作为邻接矩阵。
是否有可能在更短的O(n)时间内检测到水槽？
如果是，如何？如果不是，我们如何证明？
Sink 顶点是具有来自其他节点的入边且没有出边的顶点。
问问题
17164 次
7 回答
10
Reading the link provided by SPWorley I was reminded of tournament tree algo for finding the minimum element in an array of numbers. The node at the top of the tree is a minimum element. Since the algorithm in the link also speaks about competition between two nodes (v,w) which is succeeded by w if v->w otherwise by v. We can use an algorithm similar to finding minimum element to find out a sink. However, a node is returned irrespective of the existence of a sink. Though, if a sink exists it is always returned. Hence, we finally have to check that the returned node is a sink.
//pseudo code
//M -> adjacency matrix
int a=0
for(int i=1;i<vertices;++i)
{
if(M[a,i]) a=i;
}
//check that a is sink by reading out 2V entries from the matrix
return a; //if a is a sink, otherwise -1
于 2012-04-16T07:40:23.427 回答
7
此页面回答您的确切问题。线性时间算法是
def find-possible-sink(vertices):
if there's only one vertex, return it
good-vertices := empty-set
pair vertices into at most n/2 pairs
add any left-over vertex to good-vertices
for each pair (v,w):
if v -> w:
add w to good-vertices
else:
add v to good-vertices
return find-possible-sink(good-vertices)
def find-sink(vertices):
v := find-possible-sink(vertices)
if v is actually a sink, return it
return "there is no spoon^H^H^H^Hink"
于 2009-05-11T11:24:16.337 回答
3
Suppose to the contrary that there exists an algorithm that queries fewer than (n-2)/2 edges, and let the adversary answer these queries arbitrarily. By the Pigeonhole Principle, there exist (at least) two nodes v, w that are not an endpoint of any edge queried. If the algorithm outputs v, then the adversary makes it wrong by putting in every edge with sink w, and similarly if the algorithm outputs w.
于 2009-05-15T23:48:46.617 回答
1
I've been working on this problem and I believe this does it:
int graph::containsUniversalSink() {
/****************************************************************
Returns: Universal Sink, or -1 if it doesn't exist
Paramters: Expects an adjacency-matrix to exist called matrix
****************************************************************/
//a universal sink is a Vertex with in-degree |V|-1 and out-degree 0
//a vertex in a graph represented as an adjacency-matrix is a universal sink
//if and only if its row is all 0s and its column is all 1s except the [i,i] entry - path to itself (hence out-degree |V|-1)
//for i=0..|V|-1, j=0..|V|-1
//if m[i][j]==0 then j is not universal sink (unless i==j) - column is not all 1s
//if m[i][j]==1 then i is not universal sink - row is not all 0s
int i=0,j=1;
while (i<numVertices && j<numVertices) {
if (j>i && matrix[i][j]==true) {
//we found a 1, disqualifying vertex i, and we're not in the last row (j>i) so we move to that row to see if it's all 0s
i=j;
if (j<numVertices-1) {
//if the row we're moving to is not the last row
//we want to start checking from one element after the identity element
//to avoid the possibility of an infinite loop
j++;
}
continue;
}
if (j==numVertices-1 && matrix[i][j]==false) {
//the last element in a row is a 0
//thus this is the only possible universal sink
//we have checked the row for 0s from i+1 (or i if we're in the last row) to numVertices-1 (inclusive)
//we need to check from 0 to i (inclusive)
for (j=0; j<i+1; j++) {
if (matrix[i][j]==true || (matrix[j][i]==false && i!=j)) {
//this row is not all 0s, or this column is not all 1s so return -1 (false)
return -1;
}
}
//row is all 0s, but we don't know that column is all 1s
//because we have only checked the column from 0 to i (inclusive), so if i<numVertices-1
//there could be a 0 in the column
//so we need to check from i+1 to numVertices-1 (inclusive)
for (j=i+1; j<numVertices; j++) {
if (matrix[j][i]==false) {
return -1;
}
}
//if we get here we have a universal sink, return it
return i;
}
j++;
}
//if we exit the loop there is no universal sink
return -1;
/********************
Runtime Analysis
The while loop will execute at most |V| times: j is incremented by 1 on every iteration
If we reach the end of a row - this can only happen once - then the first for loop will
execute i times and the second will execute numVertices-i times, for a combined numVertices iterations
So we have 2|V| loop executions for a run-time bound of O(|V|)
********************/
}
于 2011-01-21T01:26:57.040 回答
1
I have figured out a solution to this.
I'm assuming arrays are initialized with all 0's (otherwise N needs to be filled with 0) and that M is a adjacency matrix for the graph. I let n be the number of nodes (n = |V|).
j,i = 1;
N = new int[n]
while (j <= n && i <= n) {
if (N[i] == 1) {
i++
} else if (N[j] == 1) {
j++;
} else if (M[i,j] == 1) {
N[i] = 1
i++
} else if (i == j) {
j++
} else {
N[j] = 1
j++
}
}
for (z = 1 to n) {
if (N[z] == 0) {
return z
}
}
return NULL
Why this works (not formal proof): Any node with any edges going from it is not a universal sink. Thus, if M[i,j] is 1 for any j, i can not be a sink.
If M[i,j] is 0 for any i, then i does not have an edge to j, and j can not be a universal sink.
A 1 at N[i] designates that I know it isn't a sink, and any node that I know isn't a sink can be skipped on both i and j. I stop when either exeeds n.
This way I keep checking any nodes, that I still don't know isn't a sink, until 1 or 0 possible sinks remain.
Thus any node that is still 0 at the end of the loop must be the sink, and there will only be either 1 or 0 of those.
Why it is O(n): This always increments either i or j. It stops when either exeeds n. Thus the worst case for the loop is 2n. The work in the loop is constant. The last loop is worst case n. Hence the algorithm is O(3n) = O(n).
This solution is based on the idea of the celebrity problem, which is a way of considering the same problem.
于 2016-05-10T13:13:46.887 回答
1
There are so many algorithms that shows how to find the universal sink in O(n) but they are so complex and couldn't be understood easily. I have found it on internet in paper that shows how to find a universal sink in O(n) very smoothly.
1) first create a "SINK" set consisting of all vertices of the graph also
create an adjacency list of the graph.
2) now choose first 2 elements of the set.
3) if(A(x,y)==1){
remove x; // remove x from "SINK" set.
}else{
remove y; } //remove y from "SINK" set.B
By this algo you will end up with the sink node in your SINK set in "n-1" time. that is O(n) time.
于 2017-10-25T07:04:19.547 回答