As we mentioned, graphs are very similar to trees. They are both made of entities (vertices) connected by relations (edges), with a couple of differences:
- In trees, vertices are usually called nodes.
- In trees, edges are somewhat implicit. Since they can only go from a node to its children, it’s more common to talk about parent/children relations than explicitly list edges. Also, because of this, trees are implicitly represented with adjacency lists.
Furthermore, trees have other peculiar characteristics that make them a strict subset of the whole set of graphs. In particular, any tree is a simple, undirected, connected, and acyclic graph.
We have illustrated in the previous section what simple graph means. In fact, a tree cannot have multiple edges between two nodes, nor can it have loops; instead, only a single edge between a node and each of its children is allowed.
Let’s now see what the other three properties mean.
1. Undirected
As we mentioned in section 1, a graph is directed when all its edges can be traversed in a single direction, from source (the first vertex in the edge’s pair) to destination.
In undirected graphs, conversely, the edges can be traversed in both directions. The difference is shown in figure 14.4.
Figure 14.4 An undirected graph (A) versus a directed graph with the same vertices (B). The two graphs are not equivalent; in particular, the latter can’t be transformed into an equivalent undirected graph.
An undirected graph can easily be represented as a directed graph, by expanding each undirected edge (u,v) into a couple of directed edges (u,v) and (v,u).
Vice versa is usually not true, and many directed graphs can’t be transformed into their undirected isomorphic counterpart.
So, unless the application context suggests otherwise, representing directed graphs is the least restricting choice.
It’s also worth noting that if the adjacency matrix representation is used, undirected graphs can be represented using only half the matrix, because they always have a symmetrical adjacency matrix: A[u,v] = A[v,u] for every pair of vertices u,v.
2. Connected
A graph is connected if, given any pair of its vertices (u,v), there is a sequence of vertices u, (w1, …, wK), v, with k≥0, such that there is an edge between any two adjacent vertices in the sequence.
For undirected graphs, this means that in a connected graph, any vertex can be reached by all other vertices, while for directed graphs, it means that each vertex has at least an in-going or an out-going edge.
For either kind, it means that the number of edges is at least |v|-1.
Figure 14.5 shows a few examples of connected and disconnected undirected graphs. The notion of connected graph makes the most sense for undirected graphs, while for directed graphs we instead introduce the notion of strongly connected components, illustrated in figure 14.6.
In a strongly connect component (SCC), every vertex is reachable from every other vertex; strongly connected components must therefore have cycles (see section 14.2.3).
The notion of strongly connected components is particularly important. It allows us to define a graph of the SCCs, which is going to be sensibly smaller than the original graph, and run many algorithms on this graph instead. We can gain a great increase in speed by first examining a graph at a high level, and then (possibly) studying the interaction within each SCC.
A tree is usually regarded as an undirected graph, at least in graph theory; but in implementations, each node usually stores the links to its children and only sometimes to its parent. If references to parents are not stored in children, then each edge is not traversable from child to parent, making it a de facto directed edge.
3. Acyclic
A cycle, in a graph, is a non-empty sequence of edges (u,v1)/ (v1 v2), …, (vK,u) that starts and ends at the same vertex.
An acyclic graph (shown in figure 14.7) is a graph that has no cycle.
Both directed and undirected graphs can have cycles, and as such there is a subset of acyclic graphs that is of special interest: directed acyclic graphs (DAGs).
A DAG has a few interesting properties: there must be at least one vertex that has no incoming edge (otherwise, there would be a cycle); moreover, since it’s acyclic, the set of edges defines a partial ordering on its vertices.
Given a directed acyclic graph G=(V,E), in fact, a partial ordering is a relation < such that for any couple of vertices (u,v), exactly one of these three conditions will hold:
- u ≤ v, if there is a path of any number of edges starting from u and reaching v.
- v ≤ u, if there is a path of any number of edges starting from v and reaching u.
- u <> v; they are not comparable because there isn’t any path from u to v or vice versa.
Figure 14.8 shows a couple of generic DAGs and a chain: the latter is the only kind of DAG defining a total ordering on its nodes.
The partial ordering on DAGs provides a topological sorting, an ordering of the vertices such that, for any edge in the graph, the edge’s starting point occurs before its ending point; usually each graph has several equivalent topological orderings. All chains, like the one in figure 14.8 (E), certainly have a single unique topological sorting, but it’s also possible that a non-chain graph also has a single topological sorting (see figure 14.8 (A-B)).
DAGs and topological ordering have many fundamental applications in computer science, spanning from scheduling (at all levels) to resolving symbol dependencies in linkers.
Source: Rocca Marcello La (2021), Advanced Algorithms and Data Structures, Manning Publications (2021)