ashish.singla87
BAN USERWhat i see it as .. If you are my friend then you are one distance apart. if you are not my friend and my friends friend then you are 2 distance apart. so first i find you in all my friends. thats first thing. then i keep all my friends in queue if i dont find you then i dequeue every one.. one by one and search in there friends and put them in queue if i find you any where in my friends friends then your distance is 2 else it will increase. to keep track of the the distance, each node we are adding to the queue can be given a depth val of node as parent + 1 and setting my depth val as 0.
- ashish.singla87 July 23, 2012I meant that shortest path helps us identify the shortest distance in case our nodes are variable distance apart. In this case all our nodes are one distance apart. then running a bfs would give all neighbors of a node and during recursion we can give a break statement on the time we find the node. that way we dont need to traverse through the whole bfs or shortest path algorithm. If we apply shortest path algorithm we are resting every node weather we have found the node or not. if we have found the node then there is no point going on with the search as it would not reduce the distance. it can only give equal or a greater distance.
- ashish.singla87 July 23, 2012when the distances are same. which you are taking to be one. then bfs does the same thing.
- ashish.singla87 July 23, 2012
make a trie tree of i words. then scan through the paper once. for every hit in trie we increase the value for that i key. (we have to specify a condition in trie. that we can only update those nodes which are instantiated to 0 and we cannot increase or touch the none nodes.. )
- ashish.singla87 July 25, 2012