Số lượng thành phần được kết nối trong đồ thị vô hướng

Question

Tôi sẽ xem xét một số thuật toán đồ thị (đây không phải là bài tập về nhà; tôi chỉ đánh vào các thuật toán và cấu trúc dữ liệu) và tôi có một câu hỏi. Giả sử tôi có đồ thị vô hướng sau:

var graph = { 
    9: [19, 26], 
    13: [19, 5], 
    17: [], 
    26: [11, 18], 
    18: [9], 
    19: [], 
    23: [24], 
    24: [], 
    11: [], 
    18: [] 
}; 

Đồ thị về cơ bản trông như thế này:

Có bao nhiêu kết nối hợp phần trong biểu đồ này? Từ chỉ nhìn vào biểu đồ, có vẻ như có 3 thành phần. Nhưng nếu tôi thực sự thực hiện thuật toán (lặp qua mỗi đỉnh, và làm một bfs sử dụng đỉnh đó làm điểm bắt đầu nếu rằng đỉnh chưa được khám phá. Ngoài ra, các bfs sẽ đánh dấu bất kỳ đỉnh nào nó gặp, như được phát hiện).

Nếu tôi bắt đầu với 9, tôi sẽ tìm ra các nút sau: [19, 26, 11, 18]. Tuy nhiên, 13 không được phát hiện vì nó không có trong danh sách kề kề của 19. Tuy nhiên, 19 là trong danh sách kề của 13. Đây là lý do tại sao tôi kết thúc với một thành phần phụ.

Điều này có đúng không? Có thực sự 4 thành phần riêng biệt và nếu như vậy, là sự hiểu biết của tôi về các thành phần kết nối sai?

Answer 1

Vấn đề là cho cơ quan đại diện danh sách kề của vô hướng đồ thị, bạn phải hoặc là

(1) sử dụng danh sách kề đối xứng, tức là khi đặt trong một cạnh mới ab, thêm b-adjlist[a]và ngược lại

hoặc

(2) đi qua danh sách tất cả các đỉnh kề everytim e bạn đang tìm kiếm sự tồn tại của một cạnh.

Vì (2) là không hiệu quả khủng khiếp, bạn thường đi với (1). Đây cũng là quy ước cho danh sách adj được sử dụng nói chung. Nếu tôi đã được trình bày với danh sách điều chỉnh của bạn, tôi cho rằng đồ thị đã được đạo diễn.

Answer 2

Bạn có thể thay đổi đại diện danh sách kề, đại diện của bạn là 'được hướng dẫn' nhưng hình ảnh của bạn không bị hướng dẫn. Đối với biểu đồ cạnh (a, b) {a: [b], b: [a]}