Software Layers 2 Introduction to unix 2

Graph Traversal

• 
  traversal = progressing from one point to another via edges in a graph
  
• 
  There are many different types of graph traversal algorithms that compute info over graphs
  
• 
  eg: The above tree can be traversed in various ways to get infix, postfix and prefix expressions:
  

• 
  note: all these functions are recursive (the call stack is used to "remember" the previous state of the functions)  this is another form of backtracking
  

• 
  A more general form of graph traversal utilizing backtracking is constructed using a stack based algorithm:
  
  • 
    the visited Boolean array is used to determine if the traversal has already reached a particular node
    
  • 
    This particular graph algorithm is called: Depth-First Search (DFS)  it explores as deep as possible into a graph first, then backtracks to all the possible alternatives at each node
    
  • 
    DFS is used in more complex algorithms to apply orderings to nodes (called a topological sort), or to find out how strongly connected a graph is
    
  • 
    variants of DFS are also used in artificial intelligence (AI) for computing over search spaces, (eg. using a DFS-based algorithm, program can compute next chess move)
    

• 
  in the binary tree above, with the root node as the start node, the following order of traversal is achieved by DFS:
  

• 
  in the 5-node 7-edge graph above, the following order of traversal is achieved by DFS:
  

• 
  If we substitute a queue for the stack in the above algorithm, all adjacent nodes are explored first  this variant explores a level at a time with no backtracking!
  
• 
  the algorithm is called: Breadth-first Search (BFS)
  
• 
  BFS is used in more complex graph algorithms for finding the shortest paths in a graph with edge values ("weights") – this is a critical algorithm for the internet (to find the fastest way to connect your computer to a remote computer...)
  
• 
  variants of BFS is also used for search space algorithms in AI
  
• 
  here is the algorithm:
  

• 
  here are the traversal orders under BFS for the binary tree and the 5-node 7-edge graph above:
  

• 
  note: BFS is finding the shortest paths from the starting node to each of the remaining nodes in a graph! (where the edge weights are assumed to be 1)
  

• 
  (very advanced stuff!!!): here is the more general algorithm for finding shortest distances along paths in weights graphs:
  
  • 
    here we need to record summations of edge weights ("distances") in every node
    
  • 
    note that the queue is a priority queue (the ordering of the nodes is by minimal distances, rather than the order of enqueues)
    
  • 
    priority queues are themselves an ADT and are typically implemented using trees (called heaps)
    

• 
  here is the resulting graph after applying the algorithm (the dark lines indicate the shortest paths from which the distance values where computed):