Tôi đang tìm một phương pháp/thuật toán nhanh để tìm các nút nào trong biểu đồ là rất quan trọng.Thuật toán nhanh để tìm các nút quan trọng là gì?
Ví dụ, trong biểu đồ này: 
số Node 2 và 5 là rất quan trọng.
Phương pháp hiện tại của tôi là thử xóa một nút không phải điểm cuối khỏi đồ thị tại một thời điểm và sau đó kiểm tra xem toàn bộ mạng có thể được truy cập từ tất cả các nút khác hay không. Phương pháp này rõ ràng không hiệu quả lắm.
Cách nào tốt hơn?
Xem biconnected components. Việc gọi chúng là các điểm khớp nối thay vì các nút quan trọng dường như mang lại kết quả tìm kiếm tốt hơn.
Trong mọi trường hợp, thuật toán bao gồm một đơn giản depth first search nơi bạn duy trì một số thông tin nhất định cho mỗi nút.
Cảm ơn bạn rất nhiều, điểm khớp nối đã thực sự cho kết quả tốt hơn và tôi tìm thấy một số rất các liên kết hữu ích để tìm kiếm độ sâu đầu tiên. – monoceres
có một số cách tốt hơn. research is always helpful
nhưng vì đây là bài tập về nhà, điểm của bài tập có khả năng là để con nó ra cho mình
gợi ý: làm thế nào bạn có thể trang trí các đồ thị để cho bạn biết những gì các nút phụ thuộc vào những gì các nút khác, và sẽ thông tin này có lẽ hữu ích để phát hiện các nút quan trọng?
Xem: http://portal.acm.org/citation.cfm?id=1480409. Họ chứng minh rằng phát hiện các nút quan trọng là NP-complete, vì vậy tôi sẽ không mong đợi những cải tiến mạnh mẽ. –
Bạn quan tâm đến các nút, không phải là các liên kết? Ví dụ, nếu tôi có một liên kết giữa 3 và 6 sau đó để tìm các nút quan trọng tôi cần phải tìm các liên kết có thể được gỡ bỏ, đầu tiên. –
@Jerry Coffin - Tôi nhớ điều gì đó trong lớp phân tích mạng điện nhưng tôi cần phải xem lại, nhưng tùy thuộc vào việc đơn giản hóa điều này có thể dễ dàng hoặc rất khó giải quyết, vì trường hợp chung quá khó, như bạn đã chỉ ra. –