Lập trình đồ thị trong Đề án

Question

Tôi mới tham gia Đề án, đã và đang sử dụng Đề án MIT trong thời gian này. Tôi đang cố gắng hiểu cách triển khai các thuật toán đồ thị phổ biến như thuật toán đường dẫn ngắn nhất, BFS, DFS. Có bất kỳ hướng dẫn nào có thể giúp tôi hiểu được sự đệ quy có liên quan, cùng với các cấu trúc dữ liệu thích hợp không? Tôi đã thử Googling cách của tôi xung quanh, nhưng điều đó đã không kết thúc cho tôi kết quả tốt.

EDIT: Tôi xin lỗi vì không cụ thể hơn trước đó. Câu hỏi của tôi liên quan đến việc duyệt qua toàn bộ biểu đồ và không tìm đường đi giữa một nút bắt đầu và mục tiêu. Vì vậy, với một đồ thị G (V, E), nơi V là tập đỉnh và E là tập cạnh, bắt đầu từ bất kỳ nút n, những gì là con đường được tạo ra để ở phần cuối của này traversal, tất cả các nút được truy cập.

Hầu hết các triển khai mà tôi tìm thấy trong khi Googling là những mục nhập với nút bắt đầu và mục tiêu. Phiên bản của tôi (một trong các câu trả lời), chọn một đỉnh và truy cập tất cả các đỉnh khác.

Lấy ví dụ, đồ thị dưới đây: -

1 ----> 2   5 
     /|   /| 
    /|  /| 
    /|  /| 
    / |  / | 
/ | / | 
    4<----3 <---6  7 

này DAG có (4-> 2), (2-> 3), (5> 6) và (5> 7), mà tôi không thể đại diện trong biểu đồ. :-)

Con đường đi qua bắt đầu từ có thể là:

(1, 2, 3, 4, 5, 6, 7)

Answer 1

Mất chút thời gian, nhưng cuối cùng tôi đã làm việc đó! Đầu ra của tôi là chuỗi trong đó các nút sẽ được truy cập trong quá trình truyền tải thông qua DFS.

Lưu ý rằng tôi vẫn chỉ học Chương trình và cách tiếp cận lập trình của tôi có thể không phải là tốt nhất.Nếu bạn tìm thấy một cái gì đó sai, không chính xác hoặc một cái gì đó có thể được thể hiện tốt hơn, để lại một bình luận!

(define (dfs graph) 
     (define (dfshelper g unvisited stack path) 
      (cond 
      ((null? unvisited) path) 
       ((null? stack) 
        (dfshelper g 
           unvisited 
           (append (list (caar unvisited)) stack) 
           path)) 
       ((memq (car stack) path) (dfshelper g 
                unvisited 
                (cdr stack) 
                path)) 
       (else (dfshelper g 
           (cdr unvisited) 
           (append (car (neighbours (car stack) g)) (cdr stack)) 
           (append path (list (car stack))))))) 

    (define (neighbours node g) 
     (cond 
     ((null? g) '()) 
     ((equal? node (caar g)) (cdar g)) 
     (else (neighbours node 
          (cdr g))))) 

    (dfshelper graph graph '() '())) 

Đầu vào mẫu có thể là: (dfs '((1 (2)) (2 (3)) (3 (4)) (4 (2)) (5 ​​(3 6)) (6 ())))

Answer 2

Chiều rộng đầu tiên và Depth-first search cả xảy ra làm ví dụ trong How To Design Programs, bắt đầu từ phần 28. Tôi nghĩ rằng điều này có thể sẽ giúp bạn đặc biệt nhất với câu hỏi của bạn về việc sử dụng đệ quy trong xử lý đồ thị.

Answer 3

Nếu bạn đại diện các đồ thị như thế này, tức là như một danh sách tên của các nút và tên của người hàng xóm của họ:

(define Graph 
    '((A (B E)) 
    (B (E F)) 
    (C (D))) 

rằng có lợi thế mà bạn thậm chí có thể biểu diễn đồ thị có chu kỳ mà không cần đến sửa đổi phá hoại của cấu trúc dữ liệu của bạn (set-cdr! v.v.), miễn là bạn cho phép nhiều mục nhập trong danh sách cho mỗi khóa.

Cách khác, bạn có thể lưu trữ không chỉ tên nhưng đại diện đầy đủ của mỗi người hàng xóm trong một danh sách, do đó bạn có thể đi bộ biểu đồ mà không làm bất cứ tra cứu tên:

(define node-name car) 
(define node-children cdr) 
(define node-first-child cadr) 

(node-first-child (node-first-child node1)) 

Để thực hiện một đồ thị có chu kỳ này tuy nhiên, bạn cần phải sử dụng set! hoặc một số biến thể. Vì vậy, các đại diện tốt nhất thực sự phụ thuộc vào ứng dụng.