Graphical programming on the chart

Question

I am new to Scheme, now using MIT Scheme. I am trying to understand how to implement popular graph algorithms, such as shortest path algorithms, BFS, DFS. Are there any tutorials that can help me understand the recursion that will be involved, as well as the corresponding data structures? I tried googling my way, but it did not give me good results.

EDIT . I apologize for not being more specific before. My question was about going through the whole graph, not finding the path between the start and the target of the node. So, given the graph G (V, E), where V is the set of vertices, and E is the set of edges, starting from any node n, what is the path generated so that at the end of this tour all nodes are visited.

Most of the implementations that I found during Googling were those who had the beginning and purpose of the node. My version (one of the answers) selects one vertex and visits all the others.

Take, for example, the following graph: -

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

This DAG has (4-> 2), (2-> 3), (5-> 6) and (5-> 7), which I cannot represent in the diagram. :-)

The path traveled from 1 can be:

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

Answer 1

Spent some time, but I finally started working! My conclusion is the sequence in which nodes would be visited bypassing through DFS.

Please note that I'm still just studying the Scheme, and my programming approach may not be the best. If you find something wrong, wrong, or something that can be better expressed, leave a comment!

  (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 '() '())) 

The sample input can be: (dfs' ((1 (2)) (2 (3)) (3 (4)) (4 (2)) (5 ​​(3 6)) (6 ())))

Answer 2

First, a search for width and depth occurs as examples in How to develop programs , starting with section 28 . I think this will probably most specifically help you with the use of recursion in graph processing.

Answer 3

If you represent such graphs, i.e. as a list of host names and the names of their neighbors:

 (define Graph '((A (BE)) (B (EF)) (C (D))) 

which has the advantage that you can even represent cyclic graphs without resorting to a destructive modification of your data structure ( set-cdr! etc.) if you allow multiple entries in the list for each key.

Alternatively, you can store not only the names, but also the complete representation of each neighbor in the list, so that you can go around the schedule without any name searches:

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

To make a loop graph this way, you need to use set! or some option. Therefore, the best performance really depends on the application.