Tham khảo tài liệu 'thuật toán algorithms (phần 44)', khoa học tự nhiên, toán học phục vụ nhu cầu học tập, nghiên cứu và làm việc hiệu quả | DIRECTED GRAPHS 423 ing to those edges that were actually used to visit vertices via recursive calls and dotted edges corresponding to those edges pointing to vertices that had already been visited at the time the edge was considered. The nodes are visited in the order A F E D B G J K L M C H I. Note that the directions on the edges make this depth-first search forest quite different from the depth-first search forests that we saw for undirected graphs. For example even though the original graph was connected the depth-first search structure defined by the solid edges is not connected it is a forest not a tree. For undirected graphs we had only one kind of dotted edge one that connected a vertex with some ancestor in the tree. For directed graphs there are three kinds of dotted edges up edges which point from a vertex to some ancestor in the tree down edges which point from a vertex to some descendant in the tree and cross edges which point from a vertex to some vertex which is neither a descendant nor an ancestor in the tree. As with undirected graphs we re interested in connectivity properties of directed graphs. We would like to be able to answer questions like Is there a directed path from vertex x to vertex y a path which only follows edges in the indicated direction and Which vertices can we get to from vertex x with a directed path and Is there a directed path from vertex x to vertex y and a directed path from y to x. Just as with undirected graphs we ll be able to answer such questions by appropriately modifying the basic depth-first search algorithm though the various different types of dotted edges make the modifications somewhat more complicated. Transitive Closure In undirected graphs simple connectivity gives the vertices that can be reached from a given vertex by traversing edges from the graph they are all those in the same connected component. Similarly for directed graphs we re often interested in the set of vertices which can be reached from a .
