Graph traversal algorithms (such as DFS and BFS) usually require a visited array, whereas tree traversal algorithms typically do not. What is the primary reason?
4 phương ánCó giải thích
Các phương án trả lời
Chọn một phương ánLời giảiChọn phương án để mở
Đáp án đúng: "General graphs may contains cycles". Trong cây, từ gốc tới mỗi nút chỉ có một đường duy nhất nên phép duyệt không bao giờ gặp lại nút đã thăm và không cần ghi nhớ gì. Đồ thị tổng quát thì có chu trình và nhiều đường đi tới cùng một đỉnh, nếu không đánh dấu đỉnh đã thăm thì phép duyệt sẽ quay vòng mãi hoặc xử lý lặp cùng một đỉnh, nên mảng đánh dấu chính là thứ cắt chu trình. "Trees are disconnected" nói ngược: cây theo định nghĩa là liên thông và không có chu trình. "Trees always have a designated root" đúng với cây có gốc và giải thích vì sao ta biết bắt đầu từ đâu, nhưng có gốc vẫn không ngăn được việc thăm lại một đỉnh khi đồ thị có chu trình, nên đó không phải lý do tồn tại của mảng đánh dấu. "Tree cannot be traversed using DFS or BFS" sai hẳn, vì duyệt trước, duyệt giữa và duyệt sau đều là tìm theo chiều sâu, còn duyệt theo mức chính là tìm theo chiều rộng trên cây.
Cùng phần 5
Suppose the graph G = (V,E) satisfies the conditions for the existence of an Eulerian cycle. The following is an algorithm for finding Euler cycle from the vertex X using stack:
declare a stack S of characters (a vertex is labeled by a character)
declare an empty array E (which will contain Euler cycle)
push the vertex X to S
while(S is not empty)
{ch = top element of the stack S
if ch is isolated then remove it from the stack and put it to E
else
select the first vertex Y (by alphabet order), which is adjacent
to ch,push Y to S and remove the edge (ch,Y) from the graph
}
the last array E obtained is an Euler cycle of the graph
Suppose a multigraph G is given below (view picture). Which of the followings is the Euler cycle from the vertex B, created by above algorithm?Có lời giảiCâu hỏiGiven the graph G = (V,E) and X is a vertex of G. Suppose there exists at least one Hamilton Cycle for the graph. The following is a backtracking algorithm for finding the first Hamilton cycle from the vertex X:
declare an empty array H (which will contain Hamilton cycle)
(1) Put the vertex X to H
(2) Check if H is a Hamilton cycle then stop, else go to (3)
(3) Consider the last vertex Y in H, if there is/are vertex(es) adjacent to Y, select the first adjacent vertex Z (by alphabet order) and put it to H. If there no adjacent vertex, remove Y from H and denote it as a bad selection (so you do not select it in the same way again).
Go to (2).
Suppose a G is given below (view picture). Which of the followings is the Hamilton cycle from the vertex A, created by above algorithm?Có lời giảiCâu hỏiWhat data structure is used for breadth first traversal of a graph?Có lời giảiCâu hỏiCả 48 câu của chủ đề48 câu
Xuất hiện trong 1 bộ đề
Đi tiếp từ đây