Độ phức tạp thời gian của thuật toán Tốt nhất để xác định xem một đồ thị vô hướng có phải là một cây không ??Thuật toán tốt nhất để xác định nếu một đồ thị vô hướng là một cây
chúng ta có thể nói Big-oh (n), với n đỉnh ??
Có, đó là O (n).
Chọn nút bắt đầu và thực hiện thao tác lướt ngang đầu tiên. Nếu bạn truy cập một nút nhiều lần, nó không phải là một cây.
Có, đó là O (n). Với một tìm kiếm chiều sâu đầu tiên trong một đồ thị có hướng dẫn có 3 loại không cạnh cây - chéo, lùi lại và tiến lên.
Đối với trường hợp không có hướng dẫn, loại cạnh không phải cây duy nhất là cạnh sau. Vì vậy, bạn chỉ cần tìm kiếm các cạnh sau.
Tóm lại, chọn một đỉnh bắt đầu. Traverse và tiếp tục kiểm tra nếu cạnh gặp phải là một cạnh sau. Nếu bạn tìm thấy các cạnh cây n-1 mà không tìm thấy các cạnh sau và sau đó, hết các cạnh, bạn là vàng.
(Chỉ cần làm rõ - back edge là một trong những đỉnh của đầu kia đã gặp phải - và vì các thuộc tính của đồ thị vô hướng, đỉnh ở đầu kia sẽ là tổ tiên của nút hiện tại trong cây đang được xây dựng.)
thnx .. chúng ta có thể làm điều đó bằng cách sử dụng BFS trong O (n) thời gian – rakesh
Bạn có thể, nhưng BFS có thể chậm hơn vì nó sẽ không tìm thấy chu kỳ nhanh. –
Thnx anthony ... chúng ta cũng có thể làm điều đó bằng BFS với thời gian O (n) – rakesh
Có, nhưng chiều sâu đầu tiên tốt hơn vì nó sẽ tìm chu kỳ nhanh hơn. –
Cũng xác minh rằng tất cả các nút được truy cập, nếu không biểu đồ có thể là một khu rừng. – dieram3