A directed graph, or digraph, is a finite set of elements called nodes or vertices, and a finite set of directed arcs or edges that connect pairs of nodes.
A directed graph differs from a tree in that they need not have a root node and there may be several (or no) paths from one vertex to another. For example, a directed graph having six vertices numbered 1, 2, 3, 4, 5, 6 and ten directed arcs joining vertices 1 to 2, 1 to 4, 1 to 5, 2 to 3, 2 to 4, 3 to itself, 4 to 2, 4 to 3, 6 to 2, and 6 to 3, can be pictured as:
A tree is a special case of a directed graph. They are characterized by the fact that one of their nodes, the root, has no incoming arcs and every other node can be reached from the root by a unique path, that is, by following one and only one sequence of consecutive arcs.
A directed graph differs from a tree in that they need not have a root node and there may be several (or no) paths from one vertex to another.
The applications for directed graphs are many and varied. They can be used to analyze electrical circuits, develop project schedules, find shortest routes, analyze social relationships, and construct models for the analysis and solution of many other problems. For example, the following directed graph illustrates the activities that must be carried out and the order in which they must be done for a construction project:
A directed graph also differs from a tree in the way that it is processed. Take insertion for example. To add a node to a tree, you must add a link field in a parent node. For a directed graph, a node may be inserted, but there need not be an arc to or from it; or an edge can be inserted between two existing nodes.
There are several common ways of implementing a directed graph. One of the common methods is to use an adjacency matrix. To construct the matrix, number the vertices of the directed graph 1, 2, ..., n. Construct a matrix that is n X n. For each entry in row i and column j, insert a 1 if vertex j is adjacent to vertex i (that is, if there is an arc from vertex i to vertex j); otherwise insert a 0.
The following directed graph:
is represented as the following adjacency matrix:
One drawback to the adjacency matrix is that it is often sparse, that is, it has a lot of zero entries, and thus considerable space is wasted. To alleviate this problem, a directed graph can also be represented as an adjacency list. For this type of representation, an array is used to hold the data for each vertex in the directed graph. For each vertex, there is also a pointer to a linked list of all vertices that are adjacent to the vertex. The adjacency list for the above list is as follows:
One of the basic operations that can be performed on a directed graph is a search. There are two types of searches that can be performed:
A depth-first search of a directed graph starts from a selected vertex and then directed arcs are followed as "deeply" as possible to visit the vertices that are reachable from it that have not already been visited. Once the end of a chain is reached, backtrack the previous node and continue the search. For example:
starting the search from vertex A results in: A, B, F, I, H, G, C, D, E.
If the search is started from a different vertex, it is possible that all of the node might not be visited. Starting from vertex B results in: B, F, I, H, G, C, D. So A and E cannot be reached.
A breadth-first search of a directed graph starts from a selected vertex and then all adjacent vertices are visited. Once done, the first adjacent vertex becomes the new starting point, and all of its adjacent vertices are visited as long as they have not been previously visited. For example:
starting the search from vertex A results in: A, B, D, E, F, C, H, G, I.
As with the depth-first search, it is possible that all of the vertices might not be visited.
An undirected graph, or graph, is like a directed graph except that there is no direction associated with the connecting arcs or edges and a node cannot be connected to itself.
An adjacency matrix and list can both be used to represent a graph. For the matrix, number the vertices of the directed graph 1, 2, ..., n. Construct a matrix that is n X n. For each entry in row i and column j, insert a 1 if there is a connecting arc between vertex j and vertex i; otherwise insert a 0.
| 0 | 1 | 0 | 1 | 1 |
| 1 | 0 | 0 | 1 | 0 |
| 0 | 0 | 0 | 1 | 0 |
| 1 | 1 | 1 | 0 | 1 |
| 1 | 0 | 0 | 1 | 0 |
For the adjacency list, you still use an array with pointers to linked lists. But with a graph, there is a node in the linked list for every connecting arc.
One of the two searches can be used to determine if there is a path from each vertex to every other vertex. If this property exists, the graph is said to be connected.