5 docs tagged with "graphs"

Directed Graph

The goal of graph traversal is to visit each vertex in a graph. This can be done a multitude of ways.

Before we see how to find the shortest path from vertex $a$ to vertex $b$ we need to define a few things.

There are multiple ways of storing graphs. Depending on the type of graph and the requirements a certain storage method might be preferred.

The goal of a topological sort is given a list of items with dependencies, (ie. item 5 must be completed before item 3, etc.) to produce an ordering of the items that satisfies the given constraints. In order for the problem to be solvable, there can not be a cyclic set of constraints. (We can't have that item 5 must be completed before item 3, item 3 must be completed before item 7, and item 7 must be completed before item 5, since that would be an impossible set of constraints to satisfy.) Meaning we can model this problem with a directed unweighted acyclic graph. When all the vertices are topologically ordered in a row all the edges go from left to right.