Graph: Elementary Algorithms - RahulKushwaha/Algorithms GitHub Wiki
##Breadth First Search:
In breadth first search we start with any node as the root node. Process the current node and add all the neighboring nodes in the queue for processing. Continue in this manner until the queue is empty.
int BFS(unordered_map<int, vector<int> >& graph, int * nodes, int n, int startNode)
{
int lastNode = startNode;
queue<int> q1;
vector<bool> visited (n, false);
queue<int>* currentQueue = &q1;
currentQueue->push(startNode);
visited[startNode] = true;
while(currentQueue->empty() == false){
int node = currentQueue->front();
lastNode = node;
unordered_map<int, vector<int> >::iterator itr = graph.find(node);
if(itr != graph.end()){
for(int i = 0; i < itr->second.size(); i++){
if(visited[itr->second[i]] == false){
currentQueue->push(itr->second[i]);
visited[itr->second[i]] = true;
nodes[itr->second[i]] = node;
}
}
}
currentQueue->pop();
}
return lastNode;
}
##Depth First Search:
Start with any node as the start node, go to any of its neighbor which is not visited before. Take the neighbor, selected in the previous step, as the new start node and explore its neighbor. Mark the node as complete when all the nodes reachable from that node have been processed. All the nodes reachable by a node are all its neighbors, neighbors of all neighbors and so on.
bool dfs(unordered_map<int, vector<int>>& graph, Color * visited, int startNode)
{
if(visited[startNode] == black || visited[startNode] == grey){
return false;
}
visited[startNode] = grey;
vector<int>::iterator endMarker = graph[startNode].end();
for(vector<int>::iterator itr = graph[startNode].begin(); itr != endMarker; itr ++){
if(visited[*itr] != black && dfs(graph, visited, *itr) == false){
return false;
}
}
visited[startNode] = black;
return true;
}