Mastering Algorithms With C - Kyle Loudon [128]
A: Discovery and finishing times recorded during depth-first search are important to some algorithms. To record these times, we use a counter that increments itself each time we color a vertex either gray or black. As a vertex is colored gray, we record the current value of the counter as its discovery time. As a vertex is colored black, we record the current value of the counter as its finishing time. In the implementation presented in this chapter, we could add two members to the DfsVertex structure to keep track of these times for each vertex.
Q: The transpose of a directed graph is a graph with the direction of its edges reversed. Formally, for a directed graph G = (V, E ), its transpose is indicated as GT . How could we form the transpose of a graph assuming an adjacency-list representation? What is the runtime complexity of this?
A: To form the transpose G T of a graph G = (V, E ), we traverse the adjacency list of each vertex u in V. As we traverse each list, we make sure that vertex v and u have both been inserted into G T by calling graph_ins_vertex for each vertex. Next, we call graph_ins_edge to insert an edge from v to u into G T. Each call to graph_ins_vertex runs in O (V ) time. This operation is called 2E times, where E is the number of edges in G. Of course, some of these calls will not actually insert the vertex if it was inserted previously. Each call to graph_ins_edge runs in O (V ) time. This operation is called once for each edge in G as well. Thus, using this approach, the overall time to transpose a graph is O (V E ).
Q: At the start of this chapter, it was mentioned that many data structures can be represented as graphs. How might we think of a binary tree as a graph?
A: A binary tree is a directed acyclic graph with the following characteristics. Each node has up to two edges incident from it and one edge incident to it, except for the root node, which has only the two edges incident from it. Edges incident from a vertex connect it with its children. The edge incident to a vertex connects its parent to it. Thus, the adjacency list of each vertex contains its children.
Related Topics
Hypergraphs
Graphs similar to undirected graphs but which contain hyperedges. Hyperedges are edges that connect an arbitrary number of vertices. In general, most operations and algorithms for graphs, such as the ones described in this chapter, can be adapted to work with hypergraphs as well.
Multigraphs
Graphs similar to undirected graphs but which allow multiple edges between the same two vertices. As with hypergraphs, in general, most operations and algorithms for graphs can be adapted to work with multigraphs as well.
Adjacency-matrix representation
A graph representation that consists of a V × V matrix, where V is the number of vertices in the graph. If an edge exists between two vertices u and v, we set a flag in position [u, v ] in the matrix. An adjacency-matrix representation is typically used for dense graphs, in which the number of edges is close to the number of vertices squared. Although the interface presented in this chapter may appear to reflect the specifics of an adjacency-list representation, there are things we could do to support this interface for an adjacency-matrix representation as well, thus keeping the details of the actual implementation hidden.
Part III. Algorithms
This part of the book contains six chapters on algorithms. Chapter 12, covers various algorithms for sorting, including insertion sort, quicksort, merge sort, counting sort, and radix sort. Chapter 12 also presents binary search. Chapter