# Digraphs

**Understanding Digraphs**

- A
**digraph**or**directed graph**is a type of graph that is made up of vertices and directed edges often called**arcs**. - Unlike an edge in an undirected graph, an arc has an orientation, meaning it goes from one vertex, known as the
**initial vertex**, to another vertex, the**terminal vertex**. - If a vertex has arcs directed away from it, those arcs are called
**outgoing arcs**, and the vertex is the initial vertex for those arcs. - Conversely, if a vertex has arcs directed towards it, those arcs are called
**incoming arcs**, and the vertex is the terminal vertex for those arcs. - The
**outdegree**of a vertex is the number of outgoing arcs from it, while the**indegree**is the number of incoming arcs to it.

**Special Types of Digraphs**

- A
**simple digraph**is a digraph which has no loops (arcs starting and ending at the same vertex) and at most one arc between any ordered pair of vertices. - An
**acyclic digraph**or**DAG**(Directed Acyclic Graph) is a digraph with no directed cycles. That is, it is impossible to start at a vertex v and follow a consistently-directed sequence of arcs that eventually loops back to v again. - A
**weighted digraph**is a digraph where each arc has a**weight**, or numerical value, associated with it. This weight could represent a variety of different things, for example, the cost to move from one vertex to another.

**Traversals in Digraphs**

**Euler paths and cycles**are possible in digraphs just as in undirected graphs. An Eulerian circuit in a digraph is a directed circuit that uses every arc exactly once.- For a strongly-connected digraph to contain an Euler circuit, every vertex must have equal indegree and outdegree.
- Traversing a directed graph is done using algorithms such as depth-first search (
**DFS**) and breadth-first search (**BFS**).

**Properties of Digraphs**

- The sum of the indegrees of all of the vertices in a digraph is equal to the sum of the outdegrees, which is also equal to the number of arcs.
- A
**strongly connected**digraph is a digraph where there is a directed path from any vertex to every other vertex. - In a digraph, the
**shortest path**from a vertex to another (based on the sum of weights, if it is a weighted digraph) can be found using algorithms like the**Dijkstra’s algorithm**.