Đang chuẩn bị liên kết để tải về tài liệu:
Thuật toán Algorithms (Phần 41)

Tham khảo tài liệu 'thuật toán algorithms (phần 41)', 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ả | CONNECTMTY 393 Graph Traversal Algorithms Depth-first search is a member of a family of graph traversal algorithms that are quite natural when viewed nonrecursively. Any one of these methods can be used to solve the simple connectivity problems posed in the last chapter. In this section we ll see how one program can be used to implement graph traversal methods with quite different characteristics merely by changing the value of one variable. This method will be used to solve several graph problems in the chapters which follow. Consider the analogy of traveling through a maze. Any time we face a choice of several vertices to visit we can only go along a path one of them so we must save the others to visit later. One way to implement a program based on this idea is to remove the recursion from the recursive depth-first algorithm given in the previous chapter. This would result in a program that saves on a stack the point in the adjacency list of the vertex being visited at which the search should resume after all vertices connected to previous vertices on the adjacency list have been visited. Instead of examining this implementation in more detail we ll look at a more general framework which encompasses several algorithms. We begin by thinking of the vertices as being divided into three classes tree or visited vertices those connected together by paths that we ve traversed fringe vertices those adjacent to tree vertices but not yet visited and unseen vertices those that haven t been encountered at all yet. To search a connected component of a graph systematically implement the visit procedure of the previous chapter we begin with one vertex on the fringe all others unseen and perform the following step until all vertices have been visited move one vertex call it from the fringe to the tree and put any unseen vertices adjacent to x on the fringe. Graph traversal methods differ in how it is decided which vertex should be moved from the fringe to the tree. For .