Graphs 0/61

Topological sort: ordering directed graphs · 1 of 3

Directed graphs and degrees

Draw one-way rules as a directed graph, count each vertex's indegree and outdegree in one pass, and answer questions from those two counts.

1,392 words · 7 min read

Part 1 of 5 Directed graphs

Edges that point one way

A graph can be a map, with places as vertices and ways to move between them as edges. An edge can also record a relation that holds in one direction only: a course has to be passed before a later course can be taken, a file has to be compiled before the program that uses it, and one person can trust another who does not trust them back. A graph of such relations is a directed graph: every edge u→vu \to v has a direction, from uu to vv, and it does not lead from vv back to uu.

Our example, here and in the topological sort and cycle detection that follow, is a set of four courses, numbered 0 to 3, with four rules:

  • course 0 must be taken before course 1
  • course 0 must be taken before course 2
  • course 1 must be taken before course 3
  • course 2 must be taken before course 3

The four courses as a graph

We make each course a vertex, and we draw each rule as an edge from the course that comes first to the course that has to wait for it:

0123

We store the graph in adjacency lists: graph[u] is the list of the vertices that uu has an edge to.

graph[0] = [1, 2]graph[1] = [3]graph[2] = [3]graph[3] = []

An undirected edge goes into two lists, one at each of its ends. A directed edge goes into one, the list of the vertex it starts at. So graph[0] shows at once which courses wait for course 0, but nothing stored at course 3 says which courses it is waiting for. To find that out from these lists we would have to read all of them.