Menu
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)
868
A graph is a type of non-linear data structure that is used to store data in the form of nodes and edges. The following is a typical representation of Graph: G = (V, E) Here G is the Graph, V is the set of vertices or nodes and E is the set of edges in the Graph G.
A graph is a non-linear data structure, which consists of vertices(or nodes) connected by edges(or arcs) where edges may be directed or undirected. In Computer science graphs are used to represent the flow of computation.
Graphs in data structures are non-linear data structures made up of a finite number of nodes or vertices and the edges that connect them. Graphs in data structures are used to address real-world problems in which it represents the problem area as a network like telephone networks, circuit networks, and social networks.
In Incidence matrix representation, graph can be represented using a matrix of size: Total number of vertices by total number of edges. It means if a graph has 4 vertices and 6 edges, then it can be represented using a matrix of 4X6 class. In this matrix, columns represent edges and rows represent vertices.
Breadth-first and Depth-first search both occur as examples in How To Design Programs, starting in section 28. I think that this will probably help you most specifically with your question about the uses of recursion in graph processing.
86
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
