CareerCup

Depending on how the getNextNotVisited() method. The Complexity should be worse case O(n)

What about the avg? O(n) ??

The complexity should be O(E) as we will pass through all the edges.

should be O(n+m) where n is the number of nodes and m is the number of edges, worst case you visit all nodes and edges

you are not marking the node as visited when you push it on stack..does't that mean the node would be used again and again, and will end up in stack multiple times ?

You make a node visited only when you have visited all Its childrens. when you are pushing to the stack It is on a state like "exploring" or "visiting" but not visited at all.
try it yourself here is the complete code:

//Given a directed graph, design an algorithm to find out whether there is a route between two nodes.
import java.util.*;
public class Graph{
	public static void main(String [] args){
		GNode startPoint = new GNode(100);
		Random random = new Random();
		
		for(int w = 0; w < 5; w ++){
			startPoint.addGNode(random.nextInt(100));
		}
		List<GNode> secondLevel = startPoint.getNodes();
		for(int i = 0; i < secondLevel.size(); i++){
			GNode node = secondLevel.get(i);
			for(int z = 0; z < 5; z ++){
				GNode n = new GNode(random.nextInt(100),node.value);
				node.getNodes().add(n);
				for(int c = 0; c< 5; c++)
				n.getNodes().add(new GNode(random.nextInt(100),n.value));
			}
			
		}
		
		
		
		printBFSGraph(startPoint);
		int target = random.nextInt(100);
		System.out.println("target: " + target	);
		searchDFS(startPoint,target);
	}
	
	public static void printBFSGraph(GNode node){
		Queue<GNode> q = new LinkedList<GNode>();
		q.add(node);
		while(q.peek() != null){
			GNode current = q.poll();
			System.out.println("[ {"+current.parent+"},"+ current.value +" ] ");
			List<GNode> childrens = current.getNodes();
			for(GNode ne : childrens){
				q.add(ne);
			}
		}
	}
	public static void searchDFS(GNode node, int value)
	{
		Stack<GNode> stack = new Stack<GNode>();
		stack.push(node);
		boolean found = false;
		while(!stack.empty()){
				GNode current = stack.peek();
				if(current.value == value){
					found  =true;
					break;
				}else{
					GNode next = current.getNextNotVisited();
					if(next == null){
						current.visited =true;
						stack.pop();
					}else{
						stack.push(next);
					}
				}
		}
		if(found){
			while(!stack.empty())
				System.out.print(stack.pop().value + " <- ");
		}else{
			System.out.println("No found");
		}
	}
	public static void searchBFS(GNode node, int value){
		Queue<GNode> queue = new LinkedList<GNode>();
		queue.add(node);
		while(queue.peek() != null)
		{
			
		}
	}

	static class GNode{
		public int value;
		public int parent;
		public boolean visited;
		public List<GNode> nodes;
		public GNode(int val){
			this.value = val;
			this.parent = -666;
		}
		public GNode(int val,int parent){
			this.value =val;
			this.parent = parent;
		}
		public void addGNode(int value){
			if(nodes == null){
				nodes = new ArrayList<GNode>();
				
			}
			
			nodes.add(new GNode(value,this.value));
		}
		public List<GNode> getNodes(){
			if(nodes == null){
				nodes = new ArrayList<GNode>();
			}
			return nodes;
		}
		public GNode getNextNotVisited(){
			for(GNode node:nodes){
				if(!node.visited)return node;
			}
			return null;
		}
	}
}

please ignore the searchBFS, I'm still working on it. the one that does the actual work is called:

searchDFS(startPoint,target);

Note: Sorry about the mess I did on the main method, I was just trying to create a random Graph. Not the best way to do it, but It works for testing proposes.

import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

public class Graph {
	
	public void bfs(Node start){
		
		Queue<Node> queue = new LinkedList<Node>();
		queue.add(start);
		
		while (queue.isEmpty()){
           Node current = queue.poll();
           
           for (Edge e : current.adj){
        	   if (e.node.dest==Node.INFINITY){
        		   e.node.dest = current.dest + 1;
        		   e.node.pre = current;
        		   queue.add(e.node);
        	   }
           }
		}
	}
	
	public boolean isConnected(Node from , Node to){
		if (to==null){
			return false;
		}else{
			if (from ==to){
				return true;
			}else{			 	
			  if (isConnected(from,to.pre)){
				  return true;
			  }
			}			
			return false;
		}
	}
	
	
	
	
	class Node{
		
		public static final int INFINITY = Integer.MAX_VALUE;
		
		Node pre;
		
		List<Edge> adj;
		
		int dest = INFINITY;
		
	}
	
	
	class Edge{
		Node node;
		int cost;
	}

}