Trees and graph traversal

Graph traversal

Depth first

Go down as far as you can go then backtrack back to o down a separate path.

Visit the root node, add to visited
Put the node on the stack and visit the next child node, add to visited
Put the first child in stack and visit the next child, add to visited
Repeat until no more children that are not visited
Backtrack by popping nodes of the stack until unvisited node is found
Perform steps 1-3 on the unvisited node and branches
Continue till all nodes visited. or the stack is empty.

def dfs(graph, currentVertex, visited):
  visitedNodes.append(currentVertex)
  for vertex in graph[currentVertex]
    if vertex not in visited::
      dfs(graph, vertex, visited)
  return visited

Applications

Job-scheduling, where some jobs have to completed before others can begin
Finding a path between two vertices
Solving puzzles such as navigating a maze

Breadth-First Traversal

all nodes adjacent to the current node are visited before moving on.

Visit the root node
Add child nodes to a queue
visit the nodes in the queue in order
add the children of each visited node to the end of the queue
Repeat until queue empty

applications

Finding the shortest path
A web crawler
Facebook uses a breadth-first search to find all the friends of a given individual

Complexity

In a graph of n nodes and e edges the time complexity is O(n+e) therefore O(n)

in a graph with a max number of edges there are n edges and n^2 edges vn^2 + n therefore the time complexity is O(n^2)

Trees

Trees are graphs with no cycles, therefore both types of traversal will visit the nodes in the same order

Post order traversal

starting on the left go down as far as possible then record the nodes going upwards, at a branch go down as far as possible before continuing to record.