One of the most foundational data structures in computer science is the graph. This simple yet flexible construct can be used to model a wide variety of problems, from social network analysis to pathfinding in video games.
These problems often require a bit more sophistication in the form of weighted graphs, where each edge or relation is assigned a numerical value or weight. In this tutorial, we will walk you through how to implement a weighted graph in Python.
Step 1: Define the Node Class
We will first define a Node class that can store the value of the node and a list of its neighbors. This will form the basic building block for our graph.
1 2 3 4 |
class Node: def __init__(self, value): self.value = value self.neighbors = {} |
Step 2: Implement the Weighted Graph
Next, we’ll implement the weighted graph. This will have methods to add nodes, add edges, and find nodes.
1 2 3 4 5 6 7 8 9 10 |
class WeightedGraph: def __init__(self): self.nodes = {} def add_node(self, node_value): self.nodes[node_value] = Node(node_value) def add_edge(self, node1_value, node2_value, weight): self.nodes[node1_value].neighbors[node2_value] = weight self.nodes[node2_value].neighbors[node1_value] = weight |
Step 3: Testing our Graph
Let’s add nodes and edges to our graph and print out each node and its neighbors to verify whether our program works as expected.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 |
g = WeightedGraph() # adding nodes for i in range(6): g.add_node(i) # adding edges with weights g.add_edge(0, 1, 2) g.add_edge(0, 4, 1) g.add_edge(1, 2, 4) g.add_edge(2, 3, 6) g.add_edge(3, 4, 8) g.add_edge(4, 5, 9) # print nodes and their neighbors for node in g.nodes: print(f'{node}: {g.nodes[node].neighbors}') |
Output:
0: {1: 2, 4: 1} 1: {0: 2, 2: 4} 2: {1: 4, 3: 6} 3: {2: 6, 4: 8} 4: {0: 1, 3: 8, 5: 9} 5: {4: 9}
Step 4: Usage of Weighted Graph
Weighted graphs are widely used in numerous fields such as graph theory, computer science, physics, and lots more. In computer science, it is often associated with algorithms like Dijkstra’s shortest path algorithm, A* search algorithm etc for finding the shortest path in a weighted graph.
Full Code:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 |
class Node: def __init__(self, value): self.value = value self.neighbors = {} class WeightedGraph: def __init__(self): self.nodes = {} def add_node(self, node_value): self.nodes[node_value] = Node(node_value) def add_edge(self, node1_value, node2_value, weight): self.nodes[node1_value].neighbors[node2_value] = weight self.nodes[node2_value].neighbors[node1_value] = weight g = WeightedGraph() # adding nodes for i in range(6): g.add_node(i) # adding edges with weights g.add_edge(0, 1, 2) g.add_edge(0, 4, 1) g.add_edge(1, 2, 4) g.add_edge(2, 3, 6) g.add_edge(3, 4, 8) g.add_edge(4, 5, 9) # print nodes and their neighbors for node in g.nodes: print(f'{node}: {g.nodes[node].neighbors}') |
Output:
0: {1: 2, 4: 1} 1: {0: 2, 2: 4} 2: {1: 4, 3: 6} 3: {2: 6, 4: 8} 4: {0: 1, 3: 8, 5: 9} 5: {4: 9}
Conclusion
In this tutorial, we have implemented a weighted graph using Python. You should now understand how to define nodes, create a graph, and add nodes and edges with relative weights to them. This provides a good starting point for more advanced graph-based problems like shortest path and minimum spanning tree algorithms.