Introduction to Graphs In python

Introduction to Graphs In Python

Graphs are fundamental data structures used in computer science and mathematics to model various relationships and connections between entities. They are versatile and find applications in a wide range of fields, including social networks, transportation systems, and computer networks.

In this article, we will explore the basics of graphs in Python, their types, representation, and common algorithms.

What is a Graph?

A graph is a collection of nodes (vertices) and edges. Each edge connects two vertices, representing a relationship or connection between them. Graphs can be used to model a wide array of scenarios, making them an essential data structure in computer science.

Types of Graphs

There are several types of graphs, and understanding their distinctions is crucial for various applications.

Directed Graphs

In a directed graph, edges have a specific direction, indicating a one-way relationship between nodes. For example, in a social media network, a directed edge could represent the “follow” relationship between users.

Undirected Graphs

Undirected graphs have edges without a specific direction, meaning the relationship is bidirectional. In a road network, an undirected edge represents a two-way road.

Weighted Graphs

In weighted graphs, each edge has a weight or cost associated with it. These weights can represent distances, costs, or any other relevant measure.

Unweighted Graphs

Conversely, unweighted graphs have edges without any associated weights.

Graph Representation: 

Graphs can be represented in two main ways: using an adjacency matrix or an adjacency list: 

Traversing a Graph: 

Traversing a graph is a fundamental operation in graph theory and computer science. It involves visiting all the vertices (nodes) and edges (connections) of a graph in a systematic manner. There are two main methods for graph traversal: depth-first traversal and breadth-first traversal.

  1. Depth-First Traversal (DFS):
    • In DFS, you start at an initial vertex and explore as far as possible along each branch before backtracking.
    • This can be implemented using recursion or a stack data structure.
    • DFS is often used to find paths, cycles, and connected components in a graph.

Here’s a simple pseudocode for DFS:

function DFS(graph, start_vertex):
    if start_vertex is not visited:
        mark start_vertex as visited
        for each neighbor in graph[start_vertex]:
            if neighbor is not visited:
                DFS(graph, neighbor)
  1. Breadth-First Traversal (BFS):
    • In BFS, you start at an initial vertex and explore all its neighbors before moving on to their neighbors.
    • This is typically implemented using a queue data structure.
    • BFS is often used to find the shortest path or to explore the graph level by level.

Here’s a simple pseudocode for BFS:

function BFS(graph, start_vertex):
    create an empty queue
    enqueue start_vertex into the queue
    mark start_vertex as visited

    while the queue is not empty:
        current_vertex = dequeue from the queue
        for each neighbor in graph[current_vertex]:
            if neighbor is not visited:
                enqueue neighbor into the queue
                mark neighbor as visited

Applications of Graphs: 

Graphs have a wide range of applications, including:

  • Social networks
  • Transportation systems
  • Recommendation systems
  • Network analysis
  • And many more 

Graph Algorithms : 

Various graph algorithms are used for solving specific problems.

Prime Course Trailer

Related Banners

Get PrepInsta Prime & get Access to all 200+ courses offered by PrepInsta in One Subscription

Get over 200+ course One Subscription

Courses like AI/ML, Cloud Computing, Ethical Hacking, C, C++, Java, Python, DSA (All Languages), Competitive Coding (All Languages), TCS, Infosys, Wipro, Amazon, DBMS, SQL and others

Checkout list of all the video courses in PrepInsta Prime Subscription

Checkout list of all the video courses in PrepInsta Prime Subscription