What's the difference between a directed and an undirected graph?

A directed graph has edges with direction, while an undirected graph has edges without any direction.

In a directed graph, also known as a digraph, each edge has an orientation, or a direction. This means that the edge is an ordered pair of vertices, and the order in which the vertices are arranged matters. For example, if there is an edge from vertex A to vertex B, it does not imply that there is an edge from vertex B to vertex A. This characteristic makes directed graphs suitable for representing asymmetric relationships, such as "is the parent of" or "is the boss of".

On the other hand, an undirected graph has edges that do not have a direction. In this case, the edge is an unordered pair of vertices, and the order of the vertices does not matter. If there is an edge between vertex A and vertex B, it implies that there is also an edge from vertex B to vertex A. This makes undirected graphs suitable for representing symmetric relationships, such as "is a friend of" or "is connected to".

The choice between using a directed or undirected graph depends on the nature of the relationships you are trying to represent. If the relationships are symmetric, an undirected graph is appropriate. If the relationships are asymmetric, a directed graph is the better choice.

In terms of their representation, directed graphs are usually drawn with arrows indicating the direction of the edges, while undirected graphs are drawn with simple lines connecting the vertices. In terms of their mathematical representation, directed graphs are represented by adjacency matrices or adjacency lists where the order of the vertices matters, while undirected graphs are represented by symmetric adjacency matrices or adjacency lists where the order of the vertices does not matter.

In summary, the main difference between a directed and an undirected graph lies in whether the edges have a direction (directed) or not (undirected), which in turn affects how the relationships between vertices are represented and interpreted.