- No suggested jump to results
-
In this repository All GitHub ↵
Jump to ↵
-
In this organization All GitHub ↵
Jump to ↵
-
In this repository All GitHub ↵
Jump to ↵
-
Dashboard Pull requests Issues
Explore Codespaces Sponsors Settings 
Sign out
New repository Import repository New gist New organization
Sorry, something went wrong.
{{ message }}
![]()
LambdaSchool / Graphs Public
-
Unwatch
Stop ignoring
Watch
Participating and @mentions
Only receive notifications from this repository when participating or @mentioned.
All Activity
Notified of all notifications on this repository.
Ignore
Never be notified.
Custom
Select events you want to be notified of in addition to participating and @mentions.
# Custom
Select events you want to be notified of in addition to participating and @mentions.
Issues
Pull requests
Releases
Discussions
Security alerts
Apply Cancel
-
Fork
If this dialog fails to load, you can visit the fork page directly.
More
master
Switch branches/tags
Branches
Tags
Could not load branches
Nothing to show
Could not load tags
Nothing to show
- Go to file T
- Go to line L
- Copy path
- Copy permalink
Cannot retrieve contributors at this time
Searching and Generating Graphs Part 1: Graph Class Part 2: Implement Breadth-First Traversal Part 3: Implement Depth-First Traversal with a Stack Part 4: Implement Depth-First Traversal using Recursion Part 5: Implement Breadth-First Search Part 6: Implement Depth-First Search Part 7: Implement Depth-First Search using Recursion
73 lines (48 sloc) 3.22 KB
- Open with Desktop
- View raw
- Copy raw contents Copy raw contents
Copy raw contents
Copy raw contents
- View blame
- Edit file
- Delete file
This is a multi-stage project to implement a basic graph class and traversals.
In the file graph.py, implement a Graph class that supports the API in the example below. In particular, this means there should be a field vertices that contains a dictionary mapping vertex labels to edges. For example:
{
'0': {'1', '3'},
'1': {'0'},
'2': set(),
'3': {'0'}
}
This represents a graph with four vertices and two total (bidirectional) edges. The vertex '2' has no edges, while '0' is connected to both '1' and '3'.
You should also create add_vertex and add_edge methods that add the specified entities to the graph. To test your implementation, instantiate an empty graph and then try to run the following:
graph = Graph() # Instantiate your graph
graph.add_vertex('0')
graph.add_vertex('1')
graph.add_vertex('2')
graph.add_vertex('3')
graph.add_edge('0', '1')
graph.add_edge('1', '0')
graph.add_edge('0', '3')
graph.add_edge('3', '0')
print(graph.vertices)
You should see something like the first example. As a stretch goal, add checks to your graph to ensure that edges to nonexistent vertices are rejected.
# Continuing from previous example
graph.add_edge('0', '4') # No '4' vertex, should raise an Exception!
Write a function within your Graph class that takes takes a starting node as an argument, then performs BFT. Your function should print the resulting nodes in the order they were visited. Note that there are multiple valid paths that may be printed.
Write a function within your Graph class that takes takes a starting node as an argument, then performs DFT. Your function should print the resulting nodes in the order they were visited. Note that there are multiple valid paths that may be printed.
Write a function within your Graph class that takes takes a starting node as an argument, then performs DFT using recursion. Your function should print the resulting nodes in the order they were visited. Note that there are multiple valid paths that may be printed.
Write a function within your Graph class that takes takes a starting node and a destination node as an argument, then performs BFS. Your function should return the shortest path from the start node to the destination node. Note that there are multiple valid paths.
Write a function within your Graph class that takes takes a starting node and a destination node as an argument, then performs DFS. Your function should return a valid path (not necessarily the shortest) from the start node to the destination node. Note that there are multiple valid paths.
Write a function within your Graph class that takes takes a starting node and a destination node as an argument, then performs DFS using recursion. Your function should return a valid path (not necessarily the shortest) from the start node to the destination node. Note that there are multiple valid paths.
Go
You can’t perform that action at this time.
You signed in with another tab or window. Reload to refresh your session. You signed out in another tab or window. Reload to refresh your session.