This project is about graph algorithms. Data structures that utilized is an adjacency list. This project programs to solve three problems, which are to check if the default graph is strongly connected, has a cycle, and compute the shortest path. The main graph functions in this project are add edge, delete edge, reset graph, random edge and print graph.
Default graph:
Implementation of the graph using adjacency list:
{('Tokyo', 'HochiMinh'): 4329, ('HochiMinh', 'Los Angeles'): 13135, ('Los Angeles', 'Asmara'): 14015, ('Prague', 'Asmara'): 4450, ('Tokyo', 'Prague'): 9073, ('Asmara', 'Tokyo'): 9961, ('Los Angeles', 'Tokyo'): 8811
Graph Functions
- Add edge
- Remove edge
- Strong connectivity in graph
- Cycle detection in graph
- Shortest path in graph
- Reset graph
This program allows user to choose different functions:
Add edge function: The program will ask source node, destination node and also destination weight for user to enter. Then, the program will display updated adjacency list of the cities with added edge.
Remove edge function: The program will ask source node and destination node to delete. Then, the program will display updated adjacency list of current cities.
Strong connectivity function: This function will determine whether the graph is strong connectivity or not.
Cycle detection function: This function will determine whether the graph has a cycle or not.
Shortest path function: This function allow user to select two vertices and compute the shortest path. The program will print the shortest path and add random edges if there is no path between the chosen vertices.
