Lecture outline for Week 8

I. Graph traversals
	- depth first search
		- start at a node, pick a random edge and follow it to the
		  nest node, repeat
		- this traversal follows a path as "deep" as possible in the
		  graph before backtracking/branching

		- pseudocode:
			void dfs(vertex v, graph G)
        		{
			    mark v as visited

			    for each i such that there is an edge (v,i)
						 and i is unvisited,
				dfs(i, G);
			}

		- what if graph is unconnected?
			- we need to re-start depth first search from an
			  unvisited node
			void traverse(graph)
			{
			    for each v in G
				if v is unvisited
				   dfs(v, G)
			}

	- breadth first search
		- traverse a graph in a "fan-out" approach
		- first find all vertices adjacent to the starting vertex
		- then find all nodes adjacent to these nodes (vertices at
		  distance 2 from the source node)
		- and continue
		- this uses a queue to keep track of visited vertices

		- pseudocode

			void bfs(vertex v, graph G)
			{
		            queue_insert(v);

			    while (queue not empty)
			    {
			        w = queue_remove(&error)
			        mark w as visited
				for each i such that there is an edge (w, i)
						and i is unvisited,
				    queue_insert(i);
			    }
			}

		- if we switch the queue for a stack we get something close
		  to depth first search
			- the difference is that true depth first search does
			  not find all neighbors to a vertex before taking
			  and edge
		- in C, you can use pointers to functions so that we can
		  write one generic search and call it with the desired
		  abstract data type

			gensearch(vertex v, graph G,
				  void (*add)(int, char *), 
				  int (*remove)(char *))
			{
			    add(v);
			    while (!empty) {
				w = remove();
				mark w as visited
				for each i such that there is an edge (w, i)
						and i is unvisited,
				    add(i, &error);
			    }
			} 

			void bfs(vertex v, graph G)
			{
			    gensearch(v, G, queue_insert, queue_remove);
			}
			void pseudo-dfs(vertex v, graph G)
			{
			    gensearch(v, G, stack_push, stack_pop);
			}

	- what is running time of each traversal algorithm?
		- will visit each vertex once (|V| steps)
		- will examine each edge once (|E| steps) - if adjacency list
		- with a adj. list, total running time is O(|V| + |E|)
		- if adjacency matrix, it is O(|V|) to find each neighbor
		  of a vertex
			- thus with a matrix, running time is O(|V|^2)
	- uses:
		- is the graph connected?
		- is there a path from x to y?
		- a breadth first search will find shortest path in terms of 
		  number of edges
		- a depth first search might not take as long, but may miss
		  the shortest path
		- heuristic seach - used in AI
			- when we hae a very large or infinite graph
			  and we are not certain where the "goal" node is
			- combines a depth first with a breadth first search
			- uses a heuristic to guide the dfs, but uses a 
			  limited bfs so to decrease the chance dfs misses the
			  goal