Transversing graph

Could someone help me with transversing this graph. Essentially, I found the minimum spanning tree using prim’s algorithm. Now I want to go transverse through the graph and visit every node. There is no specific end node but it has to start with A. I would like it to work regardless of how the spanning tree looks like.

The aim of this project is to create a schedule. Each weight tells the distance between 2 nodes. Prim’s finds the min spanning tree. Then I wanna use the min spanning tree to create a route to determine which node to go to first. All nodes must be visited. The route is used to determine the schedule.

If there are any suggestions to do this more efficiently without using nearest neighbour, I will really appreciate it.

Here’s the link:

Hey, @TraceyO77! Is this a school assignment?

1 Like

This is just a part of my A level project and not a school assignment.

Sorry about that!

This is what AI suggests:

To traverse the graph and visit every node starting from a specific node (“A” in your case), after finding the minimum spanning tree (MST) using Prim’s algorithm, you can perform a depth-first search (DFS) or breadth-first search (BFS) on the MST. Both of these traversal methods work well for ensuring you visit every node in the graph starting from a specified node.

However, since you also want to create a schedule and consider the weights (distances) between nodes, using the MST directly can ensure you visit all nodes with a minimal total distance without specific constraints on the order of visiting each node apart from starting at “A”. If the order in which nodes are visited matters beyond just starting at “A” and ensuring minimal total distance, you might consider different algorithms or approaches, but for visiting all nodes while respecting the structure of the MST, a simple DFS or BFS starting from “A” suffices.

High-Level Plan

  1. Traverse the MST obtained from Prim’s algorithm. Since you already have the MST, you can traverse it using DFS or BFS starting from “A”. DFS can recursively visit nodes, keeping track of visited nodes to avoid cycles (which won’t appear in MST but it’s a good practice). This approach ensures each node is visited once.
  2. Create a Route: You collect nodes in the order they are visited during the DFS or BFS. This order forms the basis of your schedule.
  3. Schedule Building: Once you have the route, you can map each node to a specific task or person if needed, based on your project requirements.

Implementing DFS for Traversal and Schedule Creation

I’ll show you how to implement DFS for this purpose. Given the structure of your code, we’ll integrate the traversal directly after obtaining the MST.

def dfs(graph, node, visited=None):
  if visited is None:
  visited = []
  for neighbor, _ in graph[node]:
    if neighbor not in visited:
      dfs(graph, neighbor, visited)
  return visited 

# After obtaining the MST 'qw' and transforming it back into a graph format if needed
def mst_to_graph(mst_edges):
  mst_graph = {}
  for src, dest, weight in mst_edges:
    if src not in mst_graph:
     mst_graph[src] = []
    if dest not in mst_graph:
      mst_graph[dest] = []
    mst_graph[src].append((dest, weight))
    mst_graph[dest].append((src, weight))
  return mst_graph

# Convert the list of edges in the MST back into a graph format
mst_graph = mst_to_graph(qw)

# Perform a DFS on the MST starting from 'A'

route = dfs(mst_graph, 'A')print("DFS Route:", route)

# The route list now holds the order in which nodes are visited starting from 'A'

This code snippet integrates with the existing structure of your program. After generating the MST (qw), it converts the MST back into a graph representation (since your MST is likely a list of tuples representing edges). Then, it performs a DFS starting from “A” to traverse the MST and creates a route list that determines the order of visits, which you can use for scheduling.

Appolgiies if there are any weird things in here, I use AI to generate it and I factchecked the code

1 Like