What data structure is used for breadth first traversal of a graph?
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: "queue". Duyệt theo chiều rộng phải thăm hết các đỉnh cách nguồn một cạnh trước khi sang lớp cách hai cạnh, nên cấu trúc giữ các đỉnh đang chờ phải nhả ra đúng theo thứ tự đã nạp vào: đỉnh nào được phát hiện trước thì được mở rộng trước. Hàng đợi vào trước ra trước cho đúng tính chất đó, và cũng chính nó làm BFS tìm được đường đi ít cạnh nhất trên đồ thị không trọng số. Phương án "stack" cho vào sau ra trước, nên đỉnh vừa phát hiện bị mở rộng ngay và thuật toán bị kéo chạy sâu xuống một nhánh trước khi quay lại; đó là duyệt theo chiều sâu. Phương án "list" chỉ là vật chứa chung, bản thân nó không quy định lấy ra ở đầu hay ở cuối, nên không bảo đảm được thứ tự theo lớp; muốn dùng danh sách thì vẫn phải thao tác nó đúng như một hàng đợi. Phương án "none of the above" sai vì hàng đợi đã nằm sẵn trong các lựa chọn.
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 a graph below. What is the output of depth-first traversal from vertex B? (visit nodes in ABC order if there are some nodes having the same selection ability).Có lời giảiCâu hỏiSuppose 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ỏiCả 48 câu của chủ đề48 câu
Xuất hiện trong 1 bộ đề
Đi tiếp từ đây