CODEWITHSUNDEEP
algorithmgraphtree
user107661
user107661

Reputation: 21

Algorithm to find ancestors

This was asked in an exam. Can you please help me find a solution?

Design an algorithm to find the number of ancestors of a given node (of a tree or a graph) using:

  1. O(m) memory
  2. Unlimited memory size

Upvotes: 0

Views: 2064

Answers (2)

Vikram Bhat
Vikram Bhat

Reputation: 6246

Assuming no cycles in graph (in which case the ancestors make no sense) DFS-loop can be used to calculate ancestors of any node k,just mark counted nodes in each iteration and donot count visited nodes twice.

for i in graph visited[i] = false // for DFS

for i in graph counted[i] = false // for ancestors

int globalcount = 0; // count the no of ancestors

for i in graph DFS(i,k) //DFS-loop

def bool DFS(u,k) {   //K is the node whos ancestors want to find


if(!visited[u]) {

visited[u] = true // prevent re-entering

totalret = false // whether there is path from u to k

for each edge(u,v) {

retval = DFS(v)

if(retval&&!counted[u]&&u!=k) {  //there is path from u to k & u is not counted 

  globalcount++

  counted[u] = true

  totalret = true

}

}

if(u == k) return true

else return totalret

}

return counted[u] // if visited already and whether ancestor(k)?
}

print globalcount // total ancestor(k)

space complexity : O(V) V : no of vertices

time complexity : O(E) E : no of edges in graph

Upvotes: 1

Captain Giraffe
Captain Giraffe

Reputation: 14705

The algorithm will be dependent on the design of the tree. The simplest example is for nodes containing their parent in which case it reduces to 

int ancestors = 0;
while( node = node->parent) ancestors++;

Constraints does not pose an issue in any reasonable implementation.

If the node does not contain a parent it depends on the structure of the tree.

  • In the most complex case for an unordered tree it entails a full tree search, counting ancestors.
  • For a search tree all you need is to do a search.

Upvotes: 0

Related Questions