What Is Graph Data Structure Python?

//

Larry Thompson

In Python, a graph data structure is used to represent relationships between objects. A graph consists of a set of vertices (also known as nodes) and a set of edges (also known as arcs) that connect these vertices. This data structure is widely used in computer science and can be found in various applications such as social networks, web page ranking algorithms, and route planning.

Vertices and Edges

A vertex represents an object or entity in a graph. For example, in a social network graph, each person can be represented by a vertex.

An edge connects two vertices and represents the relationship between them. In the social network example, an edge could represent a friendship between two people.

Let’s take a look at how we can represent a graph using Python:

class Graph:
    def __init__(self):
        self.vertices = {}
    
    def add_vertex(self, vertex):
        self.vertices[vertex] = []
    
    def add_edge(self, vertex1, vertex2):
        self.vertices[vertex1].append(vertex2)
        self.vertices[vertex2].append(vertex1)

Adding Vertices and Edges

To create a graph instance, we initialize an empty dictionary called vertices. The keys of this dictionary will be the vertices in the graph, and the values will be lists representing the connected vertices.

The add_vertex() method allows us to add new vertices to the graph by adding them as keys to the vertices dictionary. Initially, each vertex will have an empty list as its value.

The add_edge() method is used to create connections between vertices. It takes two parameters – vertex1 and vertex2. By appending vertex2 to the list of connected vertices for vertex1, and vice versa, we establish a bidirectional relationship.

Traversing the Graph

Once we have constructed a graph, we may need to traverse it to perform various operations. There are several algorithms available for graph traversal, such as depth-first search (DFS) and breadth-first search (BFS).

Let’s take a look at an example of depth-first search:

def depth_first_search(graph, start_vertex, visited=None):
    if visited is None:
        visited = set()
    
    visited.add(start_vertex)
    print(start_vertex)
    
    for neighbor in graph.vertices[start_vertex]:
        if neighbor not in visited:
            depth_first_search(graph, neighbor, visited)

The depth_first_search() function takes three parameters – graph, start_vertex, and an optional set called visited. It uses recursion to explore the graph starting from the specified vertex. The visited set keeps track of the vertices that have been visited during the traversal.

We add the start_vertex to the visited set and print it. Then, for each neighboring vertex of the current vertex that has not been visited yet, we recursively call the depth_first_search() function.

In Conclusion

A graph data structure is a powerful tool for representing relationships between objects in Python. It allows us to model complex systems and solve problems efficiently. By using proper graph algorithms and techniques, we can analyze and manipulate graph data effectively.

Discord Server - Web Server - Private Server - DNS Server - Object-Oriented Programming - Scripting - Data Types - Data Structures

Privacy Policy