cs126 digraphs

What is a digraph?

A directed graph // A graph whose edges are all direct

What are some applications of digraphs?

• One-way streets

• Flights

• Task scheduling

What are the properties of a diagraph?

• Each edge goes in one direction

• If it is simple, m ≤ n(n-1)

How can a digraph be used to implement task scheduling?

Edge (a,b) means task a must be completed before b can be started.

Name the (4) types of edge when a DFS traverses a direct graph.

• Discovery edges

• Back edges

• Cross Edges

• Forward edges

What does a directed DFS achieve?

It determines the vertices reachable from the start vertex.

What are some applications of directed acyclic graphs (DAGs)?

• Prerequisites between modules 

• Inheritance between classes in OOP

• Scheduling tasks of a project

Define topological ordering.

• A numbering of vertices of a diagraph: v₀, v_1, …

• For every edge (v_i, v_j), we have i < j

• A diagraph admits a topology order, iff it is a DAG

Define topological sorting.

An algorithm that computes a topological ordering of a DAG.

Describe how to perform a topological sorting using a DFS.

1. Set n^* to (number of vertices - 1)

2. Mark v as visited

3. For all outgoing edges (v,w)

   • If w is unvisited:

     • Repeat from (2) with w

4. Label v with topological number n

5. Decrement n