Traversing A Graph

Traversing a graph simply means to follow it from one point to another in a structured format. There are a number of algorithms that allow us to perfom this in the most efficient way possible, but the most basic way to visit all the vertices in a graph is breadth and depth first traversal.

undirected graph

Important key terms to remember:

Vertex = a node in the graph

Arc = A line connecting the verticies

When we traverse a graph, we attempt to visit all verticies within the graph.

In this video we look at a worked example of how to run a breadth first graph traversal:

In the next video, we move on to look at how to traverse a graph using the depth first method:

 

Looking for More?

Lesson Plan

Presentation

Homework

Revision

Not a member yet? Sign Up or Log In below