Directed vs Undirected Graphs Explained

Mohammed Islam Hadjoudj

Expert Operations Research Engineer

1. The two definitions, side by side

The difference between a directed and an undirected graph is one word in the definition: whether the pair joining two vertices is ordered. Everything else in this article, including which algorithms still work, is a consequence of that word.

An undirected graph is the standard object covered in the guide to vertices and edges. Following Diestel's Graph Theory:

G = (V, E)      with   E ⊆ [V]²      an edge is an unordered pair {u, v}

A directed graph, or digraph, replaces the unordered pair with an ordered one:

D = (V, A)      with   A ⊆ V × V      an arc is an ordered pair (u, v)

Because (u, v) and (v, u) are different ordered pairs, both can be present at once, and a digraph containing both is said to have a digon between u and v. In the undirected world there is nothing to distinguish: {u, v} and {v, u} are the same set, so the edge exists once or not at all.

Diestel gives a more general formulation worth knowing, because it is the one that survives contact with real data. A directed graph is a pair (V, E) of disjoint sets together with two maps

init: E → V        assigning each edge its initial vertex
ter:  E → V        assigning each edge its terminal vertex

Here an arc is an object in its own right rather than a pair, so the definition admits parallel arcs and loops without any special pleading. It is the directed counterpart of the incidence-function definition that multigraphs need, and it is why a flight schedule with three separate daily flights from A to B is still a perfectly good digraph.

The formal relationship to logic is exact and worth stating once: an undirected graph without loops is precisely an irreflexive symmetric relation on V, while a digraph is an arbitrary binary relation on V. Direction is what you get when you stop insisting the relation be symmetric.

These two graphs are the running example for the whole article. The digraph is

V = {A, B, C, D, E}
A = { (A,B), (B,C), (C,A), (C,D), (D,E), (E,D) }        6 arcs

and the undirected graph on the left is its underlying graph, with 5 edges, since the opposite arcs between D and E become the single edge {D, E}.

2. Edges, arcs, tails and heads

The vocabulary changes along with the definition, and the changes are not decorative. Bang-Jensen and Gutin's Digraphs, the standard reference on the directed side, is careful to reserve separate words so that a statement can never be ambiguous about which object it means.

Two terms deserve their own line because they are routinely mixed up. An oriented graph is a digraph with no digons: you took an undirected graph and chose one direction for each edge. Every oriented graph is a digraph, but a digraph containing both (u,v) and (v,u) is not an oriented graph. This distinction is the whole subject of section 5.

3. Degree splits in two

In an undirected graph the degree of a vertex counts the edge ends meeting it, and the handshaking lemma says those counts sum to twice the number of edges. In a digraph each arc has one tail and one head rather than two symmetric ends, so the single count splits into two:

• Out-degree d+(v): the number of arcs whose tail is v.
• In-degree d-(v): the number of arcs whose head is v.

and the one identity splits into two as well:

undirected     ∑v∈V deg(v)   =  2m           every edge has two ends

directed       ∑v∈V d+(v)  =  ∑v∈V d-(v)  =  |A|
                                             every arc has one tail and one head

The missing factor of 2 catches people out. It is not a different theorem, it is the same double-counting argument applied to a set whose elements now contribute to two separate sums instead of twice to one.

Check it on the running example. Out-degrees are A 1, B 1, C 2, D 1, E 1, summing to 6. In-degrees are A 1, B 1, C 1, D 2, E 1, also summing to 6, which is the number of arcs. On the underlying undirected graph the degrees are 2, 2, 3, 2, 1, summing to 10, which is twice its 5 edges.

Two named vertex types come out of this immediately and have no undirected counterpart at all:

• A source has in-degree 0: nothing points at it.
• A sink has out-degree 0: it points at nothing.

Sources and sinks are the entry and exit points of flow networks and the starting and finishing positions of a topological order. In an undirected graph the concepts are simply not expressible.

4. What changes in the matrix and the list

Direction shows up in storage as clearly as it does in the definition, and the differences are the ones set out in Cormen, Leiserson, Rivest and Stein's Introduction to Algorithms.

The adjacency matrix. For an undirected graph the matrix is always symmetric, A = AT, because {u, v} and {v, u} are the same edge. For a digraph it generally is not, and that asymmetry carries real information:

• Row sums are out-degrees, column sums are in-degrees. In the undirected case both give the degree, which is why the distinction never comes up.
• The transpose AT is exactly the reverse digraph, with every arc flipped. Reversing an undirected graph does nothing, which is another way of saying that A = AT.
• The entry (Ak)uv counts walks of length k from u to v in both worlds, but in the directed case those walks must respect the arrows, so the count is generally different from (Ak)vu.

The adjacency list. An undirected graph stores every edge twice, once in each endpoint's list, so the lists hold 2m entries. A digraph stores each arc once, in the tail's list, giving m entries. This has a practical consequence that surprises people the first time: to walk a digraph backwards you need a second structure, the reverse adjacency list, because a vertex's list tells you where you can go, not where you came from. Kosaraju's algorithm for strongly connected components is built directly on that observation and traverses the reverse graph on its second pass.

Two counting bounds follow. A simple undirected graph on n vertices has at most n(n-1)/2 edges. A digraph with no loops has at most n(n-1) arcs, exactly twice as many, because each ordered pair is now its own slot.

5. Orientations and the underlying graph

The two worlds are connected by a pair of constructions that go in opposite directions, and naming them properly removes a lot of confusion.

• Given a digraph D, its underlying graph is what you get by forgetting the arrows: replace each arc (u, v) by the edge {u, v} and discard duplicates. The running example's underlying graph has 5 edges, one fewer than the digraph's 6 arcs, because the digon between D and E collapses.
• Given an undirected graph G, an orientation of it is a digraph obtained by choosing exactly one direction for every edge. The result is an oriented graph: no digons, since each edge yields one arc.

These are not inverse operations. Taking the underlying graph loses information that no orientation can restore, and a graph with m edges has 2m distinct orientations, since each edge is an independent binary choice. The running example's underlying graph has 5 edges and therefore 32 orientations, of which the original digraph is not even one, because the original has a digon.

That raises the question the next section answers. Of those 2m orientations, is any of them good, in the sense that you can still get everywhere?

6. Robbins' theorem: which streets can go one-way

In 1939 Herbert Robbins published a short paper in the American Mathematical Monthly with the memorable title "A theorem on graphs, with an application to a problem of traffic control". The problem is exactly the one a city planner faces: if every street becomes one-way, can drivers still reach every part of town?

Robbins' theorem. A connected undirected graph has a strongly connected orientation if and only if it has no bridge.

A bridge, also called a cut edge, is an edge whose removal disconnects the graph. A connected graph with no bridges is exactly a 2-edge-connected graph, one where every edge lies on a cycle. (Connectedness matters here: a disconnected graph can be bridgeless without being 2-edge-connected.)

One direction of the proof is the easy one and is worth seeing, because it explains the whole result. Suppose e = {u, v} is a bridge, so removing it splits the graph into a component holding u and a component holding v. Any orientation must send e one way or the other. If it becomes (u, v) then nothing on v's side can ever return to u's side, because e was the only connection and it now points the wrong way. If it becomes (v, u) the same argument runs in reverse. Either way the orientation fails to be strongly connected. The converse, that every bridgeless connected graph does admit a strongly connected orientation, is the substantial half, and the standard proof runs a depth-first search and orients tree edges away from the root and back edges towards it.

The running example makes the theorem concrete. Its underlying graph contains the triangle A, B, C, which is bridgeless, but the edges {C, D} and {D, E} are both bridges. So by Robbins' theorem no orientation of that graph is strongly connected, which is precisely why the digraph in the figure is not strongly connected no matter how you redraw the arrows.

Nash-Williams generalised the result in 1960: every 2k-edge-connected undirected graph has a k-arc-connected orientation, of which Robbins' theorem is the case k = 1. The practical reading is unchanged. One-way systems are safe exactly where the road network has redundancy, and a single road connecting a suburb to the rest of town can never be made one-way without cutting it off.

7. Connectivity becomes three different questions

In an undirected graph, connectivity is a single yes or no: is there a path between every pair of vertices? Direction breaks that into a hierarchy. The classification is due to Harary, Norman and Cartwright's Structural Models, and it is the piece of directed-graph theory most often skipped and most often needed.

Each condition implies the one below it, so strong implies unilateral implies weak. The running example sits exactly in the middle of the hierarchy, which is the common case in practice: you can get from the A, B, C triangle out to D and E, but never back.

The useful refinement is to stop asking about the whole digraph and ask about its parts. A strongly connected component, or SCC, is a maximal set of vertices in which every vertex reaches every other. Every digraph partitions uniquely into SCCs, and contracting each one to a single vertex produces the condensation, which is always acyclic. That last fact is not an accident: if the condensation had a cycle, every component on it would reach every other, so they would all have been one SCC to begin with.

Finding the SCCs takes linear time. Tarjan's 1972 paper "Depth-first search and linear graph algorithms" does it in a single depth-first traversal using low-link numbers, and the Kosaraju-Sharir method does it with two passes, the second over the reverse digraph. Both run in O(n + m), and both have no undirected counterpart, because in an undirected graph the connected components fall out of any single traversal.

8. Cycles, DAGs and topological order

The word "cycle" quietly means something stricter once arrows are involved, and the gap causes real bugs.

In a simple undirected graph, a cycle is a closed walk with no repeated vertex, and it needs at least three vertices, since going along an edge and straight back is not considered a cycle. An undirected graph with no cycles is a forest, and a connected one is a tree.

In a digraph, a directed cycle must follow the arrows the whole way round, and a digon counts: the two arcs (D, E) and (E, D) form a directed cycle of length 2. A digraph with no directed cycles is a DAG, a directed acyclic graph, and DAGs carry a property nothing in the undirected world has:

A digraph has a topological order, a linear arrangement of its vertices in which every arc points forwards, if and only if it is acyclic.

Kahn's 1962 paper in Communications of the ACM gave the standard algorithm: repeatedly take a vertex of in-degree 0, output it, and delete it along with its outgoing arcs. If the digraph empties, the output is a topological order; if it stalls with vertices remaining, every survivor lies on a cycle. The details are in the guide to topological sorting.

Two traps follow from all this:

• The underlying graph having a cycle says nothing. The running example's underlying graph contains the triangle A, B, C, and its digraph does contain a directed cycle there. But orient that same triangle as A → B, A → C, B → C and you have a DAG whose underlying graph still has a cycle. Undirected cycle detection cannot answer a directed question.
• Cycle detection is a different algorithm. In an undirected graph a DFS finds a cycle when it meets any already-visited vertex that is not the parent it came from. In a digraph that test is wrong: you must find a back edge to a vertex still on the current recursion stack, since an arc into an already-finished vertex is harmless.

9. Which algorithms transfer, and which break

The practical question is which parts of an undirected toolkit survive the move. The pattern is clearer than it first appears: anything that only follows edges forwards transfers, and anything that relies on symmetry does not.

The minimum spanning tree row is the one that catches experienced people. Kruskal's and Prim's algorithms are greedy on a symmetric cost structure, and neither survives orientation. The right directed question is the minimum spanning arborescence: choose a set of arcs of least total weight so that every vertex is reachable from a fixed root. Chu and Liu in 1965 and Edmonds in 1967 solved it independently, and the algorithm looks nothing like a sorted edge scan: it selects each vertex's cheapest incoming arc, then contracts any cycle that forms and repeats.

10. Choosing: is your relation symmetric?

The modelling question has one form: if the relation holds from u to v, must it hold from v to u? If yes, use an undirected graph. If no, or if you are unsure, use a digraph, because a digraph can always express a symmetric relation but not the reverse.

One case deserves special attention because it looks symmetric and is not. An undirected edge can carry only one weight. If the cost of going from u to v differs from the cost of coming back, the relation is mutual but the model must still be directed. Cycling uphill and downhill, uploading and downloading on an asymmetric link, and exchanging currency in one direction versus the other are all mutual connections with two different costs, and each of them forces a digraph with two arcs carrying different weights.

11. Converting between the two

Three conversions come up constantly, and each loses or invents something you should be aware of.

• Digraph to undirected (symmetrisation). Replace each arc by an edge. This invents reachability: after symmetrising the running example, D reaches A, which was false in the original. Use it only when you genuinely want to ask a question about the underlying structure, such as whether the digraph is weakly connected. A stricter variant keeps only the mutual pairs, giving the "reciprocal" graph, which invents nothing but discards a great deal.
• Undirected to digraph (orientation). Choose one direction per edge. This discards mutual reachability unless the graph is bridgeless, which is exactly Robbins' theorem in section 6.
• Undirected as a digraph (arc doubling). Replace each edge {u, v} by both arcs (u, v) and (v, u). This is what almost every graph library does internally, and it is faithful for traversal and shortest paths. But it makes every edge a directed cycle of length 2, so any DAG test now answers false, every connected component becomes one strongly connected component, and a cycle detector reports a cycle for every single edge. The representation is fine; running directed structural algorithms on it is not.

12. Common mistakes

• Building the adjacency list one-way for an undirected graph. The single most common graph bug in existence. Reading an edge list and appending only adj[u].push(v) silently produces a digraph, and your BFS then finds no path along an edge it can see.
• Building it both ways for a directed graph. The same mistake inverted, and harder to spot: the code runs, the paths look plausible, and every answer that depended on direction is wrong.
• Using undirected cycle detection on a digraph. Reporting a cycle whenever DFS meets a visited non-parent vertex flags plenty of DAGs as cyclic. Digraphs need the back-edge-to-the-recursion-stack test.
• Assuming reachability is symmetric. "Is there a path from u to v" and "is there a path from v to u" are two different queries in a digraph, and answering one does not answer the other.
• Forgetting you need the reverse graph. "Which vertices can reach v" cannot be answered from the forward adjacency list in less than a full scan. Build the reverse list once if you ask that question often.
• Reaching for an MST on a digraph. Kruskal and Prim have no directed version. What you want is a minimum arborescence.
• Symmetrising to reuse a library. Convenient, and it changes the answer. Every conversion in section 11 has a cost, so make it deliberately.

13. Glossary

15. References

The definitions, theorems and attributions above come from these sources, listed in chronological order.

1. Robbins, H. E. (1939). "A theorem on graphs, with an application to a problem of traffic control." American Mathematical Monthly 46(5), 281 to 283. The bridgeless orientation theorem in section 6.
2. Ford, L. R. and Fulkerson, D. R. (1956). "Maximal flow through a network." Canadian Journal of Mathematics 8, 399 to 404. Flow posed on a digraph from the beginning.
3. Nash-Williams, C. St. J. A. (1960). "On orientations, connectivity and odd-vertex-pairings in finite graphs." Canadian Journal of Mathematics 12, 555 to 567. The k-arc-connected generalisation of Robbins.
4. Kahn, A. B. (1962). "Topological sorting of large networks." Communications of the ACM 5(11), 558 to 562.
5. Chu, Y. J. and Liu, T. H. (1965). "On the shortest arborescence of a directed graph." Scientia Sinica 14, 1396 to 1400.
6. Harary, F., Norman, R. Z. and Cartwright, D. (1965). Structural Models: An Introduction to the Theory of Directed Graphs. New York: Wiley. Source of the strong, unilateral and weak classification.
7. Edmonds, J. (1967). "Optimum branchings." Journal of Research of the National Bureau of Standards 71B(4), 233 to 240.
8. Tarjan, R. E. (1972). "Depth-first search and linear graph algorithms." SIAM Journal on Computing 1(2), 146 to 160. Linear-time strongly connected components.
9. Sharir, M. (1981). "A strong-connectivity algorithm and its applications in data flow analysis." Computers & Mathematics with Applications 7(1), 67 to 72. The two-pass method usually paired with Kosaraju's name.
10. Brin, S. and Page, L. (1998). "The anatomy of a large-scale hypertextual Web search engine." Computer Networks and ISDN Systems 30(1 to 7), 107 to 117. PageRank on the web digraph.
11. West, D. B. (2001). Introduction to Graph Theory, 2nd edition. Upper Saddle River: Prentice Hall.
12. Bondy, J. A. and Murty, U. S. R. (2008). Graph Theory. Graduate Texts in Mathematics 244. London: Springer.
13. Bang-Jensen, J. and Gutin, G. (2009). Digraphs: Theory, Algorithms and Applications, 2nd edition. London: Springer. The standard reference for directed graph terminology.
14. Cormen, T. H., Leiserson, C. E., Rivest, R. L. and Stein, C. (2009). Introduction to Algorithms, 3rd edition. Cambridge, Massachusetts: MIT Press. Source of the representation costs in section 4.
15. Chartrand, G., Lesniak, L. and Zhang, P. (2015). Graphs & Digraphs, 6th edition. Boca Raton: CRC Press. A textbook that develops both objects side by side.
16. Diestel, R. (2017). Graph Theory, 5th edition. Graduate Texts in Mathematics 173. Berlin: Springer. Source of both definitions quoted in section 1.