Difference between revisions of "Graph Algorithms OldKiwi" - Rhea

Revision as of 17:19, 13 April 2008

Graphs are a useful technique for solving a variety of problems. We can represent the data as nodes and whenever the data are related we can connect them with edges. A graph is represented as G(V,E) where G is the graph , V is the set of vertices and E are the edges.

When we want to implement graph algorithms on computer we can use one the 2 techniques:

1) Maintain a linked list for each node. Whenever there is a edge from that node to another node add a node to the list(the adjacency list of the vertex) .

2) A matrix where every row represents a vertex and every column represents the adjacency list corresponding to that node.

Whenever we talk of graphs the first problem that is usually taken up is that of searchin the graph. There are to common techniques used:

I) Breadth first search (BFS) II)Depth First Search (DFS)

I) BFS

This is used when we need to search the graph in a breadth wise fashion. At the end of depth first search we can find the distance from a given "source" vertex to every other vertex. It can work on graphs where there are NO negative weight cycles.

The following is the algorithm for BFS starting from a source vertex s

BFS(G,s)

1. for each v in the graph

  set d[v]=infinity
      color[v]=white
      pi[v]=NIL

2. d[s]=0 3. Enqueue(Q,s) 4. while Q! EMPTY

  do
  u=DEQUEUE(Q)
  for each v in the adjacency of u
     if(color[v]==WHITE)
         d[v]=d[u]+1
         pi[v]=u
         color[v]=GRAY
         ENQUEUE(Q,v)
   color[u]=BLACK

pi[v] maintains the predecessor of a node in the Breadth first tree. d[v] maintains the shortest distance from source node to vertex v Whenever a node is discovered it is paintd gray and put into a queue. When all its neighbours are explored then it is colored BLACK to indicate its been completely searched.

II) DFS

In DFS the method is to search the depth of the tree. It starts from a node goes to some node connected to it and then to some node connected to that one and so on. SO it dives in depth and does not stop till it hits the bottom and then comes back to the parent and looks for other unexplored nodes. DFS is very useful for finding Strongly Connected Components and for TOPOLOGICAL sorting of a graph.

The pseudocode for DFS is as follows:

DFS(G,s)

1. for each vertex in G

   color[v]=white
   pi[v]=NIL

2. set time=0 3. for each node v in V

   if(color[v]==white)
      DFSVISIT(v)

DFSVISIT(u)

1.set color[u]=gray 2.time =time +1 3.d[u]=time 4.for each v in adj[u]

if(color[v]==white)
   pi[v]=u
   DFSVISIT(v)

5.color[u]=BLACk 6.f[u]=time+1 7.time=time+1

d[u] is the discovery time for a node u and f[u] is the finish time- the time when all the nodes connected to the node u have been finished exploring. These quantities are very useful in various graph algorithms.

Algorithms adapted from EE608 class notes and Introduction to Algorithms by Cormen,Leisersen,Rivest and Stein.