Điều tôi đang tìm kiếm là danh sách toàn diện các thuật toán truyền tải đồ thị, với các mô tả ngắn gọn về mục đích của chúng, như là một điểm nhảy tắt để nghiên cứu chúng. Cho đến nay tôi biết:Tên của thuật toán Traversal đồ thị
một số những người nổi tiếng khác là gì? Vui lòng cung cấp mô tả ngắn gọn về từng thuật toán cho từng câu trả lời của bạn.
các knowns cũng là:
dòng chảy mạng thuật toán
Một vài tắt của đỉnh đầu của tôi: traversals
Depth-first và Chiều rộng đầu tiên, thực sự chỉ là hai cách khác nhau để chạm vào tất cả các nút.
Thuật toán Floyd-Warshall tìm đường đi ngắn nhất giữa bất kỳ cặp điểm nào, trong (big-theta) (v^3) time.
Thuật toán của Prim là giải pháp thay thế cho Kruskal cho MST.
Ngoài ra còn có các thuật toán để tìm các thành phần được kết nối đầy đủ, là các nhóm nút mà bạn có thể nhận được từ bất kỳ thành viên nào trong thành phần cho bất kỳ thành viên nào khác. Điều này chỉ quan trọng đối với "đồ thị được hướng dẫn", nơi bạn có thể đi qua một cạnh chỉ một hướng.
Cá nhân, tôi cho rằng phần mở rộng lý thuyết đồ thị tuyệt vời nhất (không liên quan chính xác đến câu hỏi của bạn, nhưng nếu bạn quan tâm đến việc tìm hiểu thêm về đồ thị nói chung chắc chắn giá trị của bạn) là khái niệm về "mạng lưu lượng": http://en.wikipedia.org/wiki/Flow_network. Đó là một cách tính toán, nói rằng, bao nhiêu điện có thể phân phối trên các ngôi nhà với một loạt các nhu cầu năng lượng và các yêu cầu, và một loạt các nhà máy điện.
Nhận xét của bạn hữu ích và sâu sắc. Cảm ơn bạn đã dành thời gian và tôi đã chấp nhận câu trả lời. –
Tên chính xác cho "các thành phần được kết nối hoàn toàn" là * các thành phần được kết nối mạnh mẽ *. –
thuật toán Graph
Tất cả các thuật toán ở một nơi
từ điển các thuật toán và cấu trúc dữ liệu:
Bằng diện tích: http://xlinux.nist.gov/dads/termsArea.html
Bằng về gõ: http://xlinux.nist.gov/dads/termsType.html
Danh sách tất cả các triển khai trong khác biệt. ngôn ngữ: http://xlinux.nist.gov/dads/termsImpl.html
Dijkstra không tìm thấy cây bao trùm tối thiểu. – KingNestor
Rất tiếc, tôi đã tôn kính cả hai trong danh sách của mình. Đã sửa. –
Không thực sự chắc chắn lý do tại sao câu hỏi này đã được downvoted, đó là một câu hỏi liên quan đến lập trình hợp pháp, và không phải là một bản sao. –