Data Structures Explained with Python

Graph Data Structures in Python

A graph is a non-linear data structure consisting of a set of vertices (or nodes) and a set of edges that connect pairs of vertices. Graphs are used to represent networks, relationships between objects, and various other real-world scenarios.

Key Terminologies:

• Vertex (Node): A fundamental part of a graph.
• Edge (Link/Arc): A connection between two vertices. Edges can be directed (one-way) or undirected (two-way).
• Adjacency: Two vertices are adjacent if they are connected by an edge.
• Path: A sequence of vertices where each adjacent pair is connected by an edge.
• Cycle: A path that starts and ends at the same vertex.
• Degree of a Vertex: In an undirected graph, the number of edges incident to it. In a directed graph, it'''s split into in-degree (incoming edges) and out-degree (outgoing edges).
• Weighted Graph: A graph where each edge has an associated weight or cost.
• Connected Graph: An undirected graph where there is a path between every pair of vertices.
• Directed Acyclic Graph (DAG): A directed graph with no directed cycles.

Types of Graphs:

• Undirected Graph: Edges have no orientation (e.g., a friendship network on social media).
• Directed Graph (Digraph): Edges have a direction (e.g., a flowchart, web page links).
• Weighted Graph: Edges have associated weights (e.g., road networks with distances).
• Unweighted Graph: Edges do not have weights.
• Cyclic Graph: Contains at least one cycle.
• Acyclic Graph: Contains no cycles.

Graph Representations:

There are two common ways to represent graphs in memory:

1. Adjacency Matrix: A 2D array where matrix[i][j] = 1 (or weight) if there is an edge from vertex i to vertex j, and 0 (or infinity) otherwise. Space complexity is O(V^2), where V is the number of vertices. Good for dense graphs.
2. Adjacency List: An array of lists (or dictionaries/hash maps). For each vertex i, adj_list[i] stores a list of vertices adjacent to i. Space complexity is O(V+E) for undirected graphs and O(V+E) for directed graphs, where E is the number of edges. Good for sparse graphs.

Adjacency List Implementation in Python (using a dictionary):

class Graph:
    def __init__(self):
        self.adj_list = {}

    def add_vertex(self, vertex):
        if vertex not in self.adj_list:
            self.adj_list[vertex] = []

    # For an undirected graph
    def add_edge(self, v1, v2):
        if v1 in self.adj_list and v2 in self.adj_list:
            self.adj_list[v1].append(v2)
            self.adj_list[v2].append(v1) # For undirected, add both ways
        else:
            print("One or more vertices not found.")

    # For a directed graph
    def add_directed_edge(self, u, v):
        if u in self.adj_list and v in self.adj_list:
            self.adj_list[u].append(v)
        else:
            print("One or more vertices not found.")

    def print_graph(self):
        for vertex in self.adj_list:
            print(f"{vertex}: {self.adj_list[vertex]}")

# Example Usage (Undirected Graph):
g = Graph()
g.add_vertex('''A''')
g.add_vertex('''B''')
g.add_vertex('''C''')
g.add_vertex('''D''')

g.add_edge('''A''', '''B''')
g.add_edge('''A''', '''C''')
g.add_edge('''B''', '''D''')
g.add_edge('''C''', '''D''')

print("Undirected Graph Adjacency List:")
g.print_graph()
# Output:
# A: ['''B''', '''C''']
# B: ['''A''', '''D''']
# C: ['''A''', '''D''']
# D: ['''B''', '''C''']

# Example Usage (Directed Graph):
dg = Graph()
dg.add_vertex(0)
dg.add_vertex(1)
dg.add_vertex(2)
dg.add_vertex(3)

dg.add_directed_edge(0, 1)
dg.add_directed_edge(0, 2)
dg.add_directed_edge(1, 2)
dg.add_directed_edge(2, 0)
dg.add_directed_edge(2, 3)
dg.add_directed_edge(3, 3)

print("\nDirected Graph Adjacency List:")
dg.print_graph()
# Output:
# 0: [1, 2]
# 1: [2]
# 2: [0, 3]
# 3: [3]
        

Common Graph Algorithms:

• Breadth-First Search (BFS): Traverses the graph level by level. Used for finding shortest paths in unweighted graphs.
• Depth-First Search (DFS): Traverses the graph by exploring as far as possible along each branch before backtracking. Used for cycle detection, topological sorting, and finding connected components.
• Dijkstra'''s Algorithm: Finds the shortest path between nodes in a weighted graph with non-negative edge weights.
• Bellman-Ford Algorithm: Finds the shortest path in a weighted graph, can handle negative edge weights.
• Kruskal'''s and Prim'''s Algorithms: Find the Minimum Spanning Tree (MST) of a connected, undirected graph.
• Topological Sort: Linear ordering of vertices such that for every directed edge from vertex u to vertex v, vertex u comes before vertex v in the ordering. Applicable to DAGs.

Applications of Graphs:

• Social networks (Facebook, LinkedIn).
• Navigation systems (Google Maps, Waze).
• The World Wide Web (pages as vertices, links as edges).
• Recommendation systems.
• Biological networks (protein-protein interactions).
• Computer networks and circuit design.