graph

** Graph Traversal

l  DFS(Depth-First Search)

Void dfs(vertex u){

      u.visit();

      u.visited=true;

      for(each vertex v such that (u,v) ∈ E){

                 if(!v.visited)

                           dfs(v);

      }

}

l  BFS(Breadth-First Search)

void BFS(vertex u){

      u.visit();

      u.visited=true;

      q=new Queue();

      q.enqueue(u);

      while(q is not empty){

                 v=q.dequeue();

                 for (each vertex w s.t (v,w)∈E){

                           if(!w.visited){

                                      w.visit();

                                      w.visited=true;

                                      q.enqueue(w);

                           } //end of if

                 }

      }

** Quick-Union with an array for disjoint sets

{0} {1} {2} {3} {4} {5} {6} {7} {8} {9}

0  1  2  3  4  5  6  7  8  9

0 -1

1 -1

…

….

8 -1

9 -1

l  Union-by-size

l  Find

Ex)

Int find(int x){

      If(array[x] < 0){ return x;}

      Else{

                 Array[x]=find(array[x]);

                 Return array[x];

      }

}

find(7)

array[7]=find(4)

array[4]=find(1)

array[1]=find(0)

 

void union ( int root1, int root2){

      if(array[root2]<array[root1]){

                 array[root2]+=array[root];

                 array[root1]=root2;

      }else{

                 Array[root1]+=array[root2];

                 Array[root2]=root1;

      }

}

** If we use union-by-size, a single find operation can take O(log u) worst-case time, where u is the number of union operations that took place prior to the find.