Thread: how can a breadth-first-search-tree include every node have ancestor list

how can a breadth-first-search-tree include every node have ancestor list. every node have multiple ancestor list(because every node may be multiple parents)
input: undirected graph

I think that you need to explain more clearly what you are trying to do and what problems you are facing doing it. Just writing "input: undirected graph" tells me nothing about how does that relate in your case to a "breadth-first-search-tree", and how "include every node have ancestor list" is a problem.

(Also, I don't think there is such a thing as a breadth-first search tree: you can apply breadth-first search on a tree, but that doesn't make it a "breadth-first-search-tree" since you can apply depth-first search on the same tree.)

^_^

I'm so pleased that I'm not the only one...

Soma

thank you laserlight
i want to make ancestor list at every node in the bfs spanning tree but bfs spanning tree every node does not contain more then one parent. in my case every node have multiple parent and every node maintain own ancestor list(if single parent then single ancestor list else multiple parent then multiple ancestor list). ancestor list are stored at corresponding node.
example:
input graph
node connected_with_node
0 -> 1,2,5
1 ->0,3
2 ->0,3,4
3 ->1,2
4 ->2,5
5 ->0,4
desire output :
node ancestor_list
0 -(no any parent so no list)
1 ->0-1
2 ->0-2
3 ->0-1-3
->0-2-3(node 2 have two parent so make two list)
4 ->0-2-4
->0-5-4(same as node 2,node 4 have two parent)
5 ->0-5


and using BFS only for making ancestor list in graph.

thank you laserlight

O_o

I'm not sure I understand, but if I do, you have only to use normal "DFS" traversal of your graph with an recursive phase to reset "visited" for each parent followed by reducing the set.

That said, having the list isn't the same as having valuable information about the list. If you are trying to find the "nearest" ancestor for each node or similar property you should search for specific algorithms related to what property you require.

Soma

thank you sir

Originally Posted by cmsamota

thank you sir
i'm beginner in c++ so please help me in code. please give me source code

Please read the rules. At least this one.
Announcements - General Programming Boards