killervastu Posted November 12, 2011 Share Posted November 12, 2011 I am trying to find a tutorial on how to perform a depth first search. I've seen pseudocodes and sources in other languages, but I just can't implement it in PHP no matter what I try. Can anyone show me how or where I can read up on it or how to do it? Quote Link to comment https://forums.phpfreaks.com/topic/250991-learn-dfs-algorithm/ Share on other sites More sharing options...
cwarn23 Posted November 12, 2011 Share Posted November 12, 2011 I just happen to be writing an algorithm which follows similar concepts and the main thing you need to do is record what you have seen as you have gone along. It is actually quite easy when you get your mind around the loop and is only a matter of a decent database structure. For example, this is the database structure I chose: backlinks table column (int) ->linkid column (int) ->backlink linkdata table column (int) ->linkid column (int) ->backlinks (total) column (varchar)->linkurl pages table column (int) ->linkid column (varchar)->page Using that database design you can simply insert newly discovered links into linkdata with backlinks being 1 upon insertion unless the link occurs multiple times in that page. So basically to track the backlinks or the number of depths you simply add the the backlinks variable if another instance of that link has been found along the track in the linkdata table. Quote Link to comment https://forums.phpfreaks.com/topic/250991-learn-dfs-algorithm/#findComment-1287575 Share on other sites More sharing options...
silkfire Posted November 12, 2011 Share Posted November 12, 2011 You need a recursive function. Lots of PHP implementations out there. Quote Link to comment https://forums.phpfreaks.com/topic/250991-learn-dfs-algorithm/#findComment-1287655 Share on other sites More sharing options...
killervastu Posted November 12, 2011 Author Share Posted November 12, 2011 Hey guys thanks for reply, but i just want to implement total nodes on left and total nodes on right in a binary tree. so can anyone please guide me through that in php Quote Link to comment https://forums.phpfreaks.com/topic/250991-learn-dfs-algorithm/#findComment-1287702 Share on other sites More sharing options...
cwarn23 Posted November 13, 2011 Share Posted November 13, 2011 The easiest way to do it is to have a loop which loops through an array of nodes and keep on appending to the array as more nodes are found. Simple concept but probably not the most efficient one. Quote Link to comment https://forums.phpfreaks.com/topic/250991-learn-dfs-algorithm/#findComment-1287747 Share on other sites More sharing options...
Recommended Posts
Join the conversation
You can post now and register later. If you have an account, sign in now to post with your account.