Graph Traversal

Depth-First Traversal

algorithm  dft(x) 
   visit(x) 
   FOR each y such that (x,y) is an edge DO 
     IF y was not visited yet THEN 
        dft(y) 

A recursive algorithm implicitly recording a “backtracking” path from the root to the node currently under consideration

     

 

            

Breadth-First Traversal

Visit the nodes at level i before the nodes of level i+1.

 

visit(start node) 
queue <- start node 
WHILE queue is nor empty DO 
  x <- queue 
  FOR each y such that (x,y) is an edge 
                  and y has not been visited yet DO 
    visit(y) 
    queue <- y 
  END 
END 

          

Representations of Graphs

Adjacency Matrices

Graphs G = (V, E) can be represented by adjacency matrices G[v₁..v_|V |, v₁..v_|V |], where the rows and columns are indexed by the nodes, and the entries G[v_i, v_j] represent the edges. In the case of unlabeled graphs, the entries are just boolean values.

A B C D A 0 1 1 1 B 1 0 0 1 C 1 0 0 1 D 1 1 1 0

In case of labeled graphs, the labels themselves may be introduced into the entries.

A B C D A 10 4 1 B 15 C 9 D

Adjacency matrices require O(|V |²) space, and so they are space-efficient only when they are dense (that is, when the graphs have many edges). Time-wise, the adjacency matrices allow easy addition and deletion of edges.

Adjacency Lists

A representation of the graph consisting of a list of nodes, with each node containing a list of its neighboring nodes.

This representation takes O(|V | + |E|) space.