graphfunctional-programminglispscheme# Graph programming in Scheme

I'm new to Scheme, have been using MIT Scheme for sometime now. I'm trying to understand how to implement popular graph algorithms like the shortest path algorithms, BFS, DFS. Are there any tutorials that could help me out understand the recursion that'd be involved, along with the appropriate data structures? I have tried Googling my way around, but that didn't end up giving me good results.

**EDIT**: I apologize for not being more specific earlier. My question was pertaining to traversing the whole graph, and not finding the path between a *start* and *goal* node. So, given a graph *G(V, E)*, where *V* is the vertex set and *E* is the edge set, starting from any node *n*, what is the path generated so that at the end of this traversal, all nodes are visited.

Most implementations that I found while Googling were the ones with the *start* and *goal* node. My version (one of the answers), chooses one vertex, and visits all 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 unable to represent in the diagram. :-)

The Path traversed starting from **1** could be:

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

Solution

Took some time, but I got it working finally! My output is the sequence in which the nodes would've been visited in the traversal through DFS.

Note that I am still only learning Scheme, and my programming approach might not be the best. If you find something wrong, incorrect or something that can be expressed better, 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 '() '()))
```

Sample input could be: (dfs '((1 (2)) (2 (3)) (3 (4)) (4 (2)) (5 (3 6)) (6 ())))

- Why does my points() code not work? Plotting two variables with subsets of a third in r
- gnuplot: back arrow-style inconsistent with multiplot
- Specifying Color of Columns in MS Access Histogram Chart
- Using BFS for Weighted Graphs
- Removing a node in an undirected graph that destroys a path between two other nodes
- Interactive Graphviz graphs in a web application
- How to get red/green solid candlestick in eCharts graph
- NetworkX: how to add weights to an existing G.edges()?
- "add_transition() argument after ** must be a mapping, not str" : transitions python library
- Breadth First Search time complexity analysis
- Horn SAT algorithm using graphs
- Is there a way to build an interactive node graph in JavaScript?
- how to use gnuplot with one x and several y
- ggpplot2 join all points in a graph with a line
- ChartJS Bar chart - Modify legend
- How to draw a custom inclined line on Chartjs
- Microsoft Graph API, Add SharePoint List Item suddenly throws exception for null strings
- JpGraph: How to control x/y offset, margins and color in v3.5.0b1 when using AccBarPlot?
- matplotlib graphs: how to connect with lines points if there are emply values in a column
- How to calculate the maximum concurrency of nodes in a DAG?
- Matplotlib and Networkx - drawing a self loop node
- Visualization of Graphs Data
- Visualize a clickable graph in an HTML page
- Flutter fl_chart LineChart erroring out with more than a 4 day data differential
- Relationship between dpi and figure size
- Why is graph in Networkx pointing arrows in the wrong direction?
- Prevent recursive CTE visiting nodes multiple times
- How can I write a SQLAlchemy query that will return all descendants of a node in a graph?
- One way to construct graph adjacency list based on adjacency pairs similar to `fold` in MIT Scheme
- Distance between two nodes in a tree weighted