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.

• Visit all the nodes to the left of the root node

• visit right

• Visit root node

• Repeat three points for each node visited

50, 45, 76, 20, 48, 60, 98, 5, 31, 88, 92