📈 DSA using Python: Graph 📉

Follow Me

✅ 1. What is a Graph?

A Graph is a collection of:

• Vertices (nodes) – Represent entities

• Edges (connections) – Represent relationships between vertices

Graphs can be:

• Directed or Undirected

• Weighted or Unweighted

• Cyclic or Acyclic

Types of Graph

✅ Types of Graphs in Data Structures

Graphs can be classified based on direction, weight, connectivity, cycles, and completeness:

🔹 1. Directed Graph (Digraph)

• Edges have a direction (from one vertex to another).

• Represented as ordered pairs (A → B).

🧠 Use-case: Web page links, road maps with one-way streets.

🔹 2. Undirected Graph

• Edges have no direction.

• Represented as unordered pairs (A — B).

🧠 Use-case: Social networks (mutual friendships), electrical circuits.

🔹 3. Weighted Graph

• Each edge has a weight or cost (e.g., distance, time, cost).

• Can be directed or undirected.

🧠 Use-case: Google Maps (shortest route), network latency.

🔹 4. Unweighted Graph

• No weights on edges.

• Just shows connections.

🧠 Use-case: Graphs for basic structure or logic.

🔹 5. Cyclic Graph

• Contains at least one cycle.

• A cycle is a path that starts and ends at the same vertex.

🧠 Use-case: Circular dependencies in systems.

🔹 6. Acyclic Graph

• Contains no cycles.

• If directed and acyclic → DAG (Directed Acyclic Graph).

🧠 Use-case: Task scheduling, dependency resolution, Git commits.

🔹 7. Connected Graph

• Every vertex is reachable from every other vertex (in undirected graph).

🧠 Use-case: LAN networks, team communication.

🔹 8. Disconnected Graph

• Some vertices are not connected.

• Has two or more separate components.

🧠 Use-case: Incomplete systems, unconnected subnetworks.

🔹 9. Complete Graph

• Each vertex is connected to every other vertex.

• For n vertices → n(n-1)/2 edges (undirected).

🧠 Use-case: Dense networks, test cases in algorithms.

🔹 10. Sparse Graph

• Few edges compared to the number of vertices.

• E.g., Tree or Linked List structure.

🔹 11. Dense Graph

• Many edges, close to complete graph.

• May include loops or multiple edges.

🔹 12. Multigraph

• Can have multiple edges (parallel edges) between the same pair of vertices.

🧠 Use-case: Transportation routes with multiple options.

🔹 13. Subgraph

• A portion of a graph formed using some of its vertices and edges.

🔹 14. Tree (a special graph)

• A connected, acyclic, undirected graph.

• Has n-1 edges for n vertices.

🧠 Use-case: Hierarchies, file systems.

🧠 Summary Table:

Type	Directed?	Weighted?	Cycles?	Connected?
Directed Graph	✅	❌/✅	❌/✅	❌/✅
Undirected Graph	❌	❌/✅	❌/✅	❌/✅
Weighted Graph	❌/✅	✅	❌/✅	❌/✅
Acyclic Graph	❌/✅	❌/✅	❌	✅/❌
Complete Graph	❌	❌/✅	✅	✅
Tree	❌	❌/✅	❌	✅

✅ Basic Graph Terminologies

Term	Meaning
Graph (G)	A collection of vertices (nodes) and edges (connections).
Vertex (Node)	A point in the graph (like a city, person, etc.).
Edge	A connection between two vertices.
Adjacent	Two vertices are adjacent if there is an edge between them.
Degree	Number of edges connected to a vertex.
Directed Edge	Edge that has a direction (from one vertex to another).
Undirected Edge	Edge without direction (mutual connection).
Weighted Edge	An edge with a cost or weight (e.g., distance, time).
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.
Acyclic Graph	A graph with no cycles.
Connected Graph	Every vertex is reachable from any other vertex.
Disconnected Graph	At least one vertex is not reachable from others.
Complete Graph	Each vertex is connected to every other vertex.
Subgraph	A smaller part (subset of nodes/edges) of a graph.
Sparse Graph	A graph with few edges compared to the number of vertices.
Dense Graph	A graph with many edges, close to complete.
Multigraph	A graph where multiple edges can exist between two vertices.
Self-loop	An edge that connects a vertex to itself.

✅ Additional Terminologies for Advanced Graphs

Term	Meaning
Directed Graph (Digraph)	Graph where all edges have direction.
Undirected Graph	Graph where edges have no direction.
DAG (Directed Acyclic Graph)	A directed graph with no cycles.
Tree	A connected, acyclic, undirected graph.
Rooted Tree	A tree with a root node from where traversal starts.
Traversal	Visiting all vertices/nodes (e.g., BFS, DFS).
Bridge	An edge whose removal increases the number of connected components.
Articulation Point	A vertex whose removal disconnects the graph.
Isolated Vertex	A node not connected to any other node.
Component	A maximally connected subgraph.

🧠 Graph Implementations in Python – Definitions

• Adjacency List

  • A dictionary where each key is a node, and its value is a list (or set) of adjacent nodes.

  • ✅ Memory-efficient for sparse graphs.

  • ✅ Easy to iterate over neighbors.

  • ❌ Slower edge lookup: O(n) time (if using list).

  Example:

  graph = {
      'A': ['B', 'C'],
      'B': ['A', 'D'],
      'C': ['A'],
      'D': ['B']
  }

• Adjacency Matrix

  • A 2D matrix (list of lists) where matrix[i][j] = 1 if there is an edge from node i to j.

  • ✅ Fast edge lookup: O(1).

  • ❌ Consumes more memory (O(n²)) even for sparse graphs.

  Example:

  graph = [
      [0, 1, 1, 0],  # A
      [1, 0, 0, 1],  # B
      [1, 0, 0, 0],  # C
      [0, 1, 0, 0],  # D
  ]

• Dictionary of Sets or Lists

  • A variation of adjacency list where each node points to a set or list.

  • ✅ Sets offer faster lookup (O(1)) than lists (O(n)).

  • ✅ Prevents duplicate edges.

  • ❌ Sets are unordered, which may be less intuitive for traversals.

  Example using sets:

  graph = {
      'A': {'B', 'C'},
      'B': {'A', 'D'},
      'C': {'A'},
      'D': {'B'}
  }

🎯 Diagram: Comparison

                    +---------------------+
                    |     Adjacency List  |
                    |  (List or Set Based)|
        +-----------+---------------------+-----------+
        |                      |                      |
        |                      |                      |
        |                      |                      |
        |  Fast Iteration      |     Fast Lookup      |
        |  over Neighbors      |     O(1) Lookup      |
        |                      |     for Edges        |
        |                      |                      |
        |     +------------------------------+        |
        |     |     Dictionary of Sets       |        |
        |     +------------------------------+        |
        |                      |                      |
        |                      |                      |
        |                      |                      |
        |                      |                      |
        |         +------------+-------------+        |
        |         |     Adjacency Matrix     |        |
        |         +--------------------------+        |
        |                      |                      |
        +----------------------+----------------------+

✅ Summary Table

Feature	Adjacency List	Adjacency Matrix	Dictionary of Sets
Space Efficient	✅ Yes	❌ No (O(n²))	✅ Yes
Fast Neighbor Lookup	✅ Yes	❌ No	✅ Yes
Fast Edge Lookup	❌ No (O(n))	✅ Yes (O(1))	✅ Yes (O(1))
Prevents Duplicates	❌ No	✅ Yes	✅ Yes

🔧 Basic Graph Operations (using Adjacency List method):

We'll implement:

1. Add Vertex (Node)

2. Add Edge

3. Remove Vertex

4. Remove Edge

5. Check for Edge

6. Display Graph

7. Traverse Graph (BFS and DFS)

⚙️ 1. Create a Graph Class

class Graph:
    def __init__(self):
        self.graph = {}  # Adjacency list

👉 We start with an empty dictionary to store our graph.

➕ 2. Add Vertex

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

✅ Explanation: If the vertex is not already in the graph, we add it with an empty list (no connections yet).

🔗 3. Add Edge (Undirected)

    def add_edge(self, v1, v2):
        if v1 in self.graph and v2 in self.graph:
            self.graph[v1].append(v2)
            self.graph[v2].append(v1)

✅ Explanation:

• Adds an edge between v1 and v2.

• Since it's undirected, we add both ways (v1 → v2 and v2 → v1).

❌ 4. Remove Vertex

    def remove_vertex(self, vertex):
        if vertex in self.graph:
            for neighbor in self.graph[vertex]:
                self.graph[neighbor].remove(vertex)
            del self.graph[vertex]

✅ Explanation:

• Removes the vertex.

• Also removes it from every other vertex's neighbor list.

✂️ 5. Remove Edge

    def remove_edge(self, v1, v2):
        if v1 in self.graph and v2 in self.graph:
            if v2 in self.graph[v1]:
                self.graph[v1].remove(v2)
            if v1 in self.graph[v2]:
                self.graph[v2].remove(v1)

✅ Explanation: Deletes the connection from both nodes.

🔍 6. Check for Edge

    def has_edge(self, v1, v2):
        return v1 in self.graph and v2 in self.graph[v1]

✅ Explanation: Returns True if there is a direct edge from v1 to v2.

📤 7. Display Graph

    def display(self):
        for vertex in self.graph:
            print(f"{vertex} --> {self.graph[vertex]}")

✅ Explanation: Prints the full graph in an easy-to-read format.

🔄 8. Graph Traversals

A. BFS (Breadth-First Search)

    def bfs(self, start):
        visited = set()
        queue = [start]

        while queue:
            vertex = queue.pop(0)
            if vertex not in visited:
                print(vertex, end=' ')
                visited.add(vertex)
                queue.extend([v for v in self.graph[vertex] if v not in visited])

✅ Explanation:

• Visits level by level.

• Uses queue (FIFO).

• Good for finding shortest path.

B. DFS (Depth-First Search)

    def dfs(self, start, visited=None):
        if visited is None:
            visited = set()
        visited.add(start)
        print(start, end=' ')

        for neighbor in self.graph[start]:
            if neighbor not in visited:
                self.dfs(neighbor, visited)

✅ Explanation:

• Visits as deep as possible before backtracking.

• Uses recursion (or stack).

• Good for exploring all paths.

✅ Full Example

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.display()

print("\nBFS from A:")
g.bfs('A')

print("\nDFS from A:")
g.dfs('A')

print("\nHas Edge A-B:", g.has_edge('A', 'B'))

g.remove_edge('A', 'B')
print("After removing edge A-B:")
g.display()

g.remove_vertex('D')
print("After removing vertex D:")
g.display()

📌 Output:

A --> ['B', 'C']
B --> ['A', 'D']
C --> ['A']
D --> ['B']

BFS from A:
A B C D 

DFS from A:
A B D C 

Has Edge A-B: True

After removing edge A-B:
A --> ['C']
B --> ['D']
C --> ['A']
D --> ['B']

After removing vertex D:
A --> ['C']
B --> []
C --> ['A']

📝 Summary Table

Operation	Tool Used	Time Complexity
Add Vertex	Dictionary	O(1)
Add Edge	List Append	O(1)
Remove Vertex	List Remove	O(V)
Remove Edge	List Remove	O(E)
Has Edge	List Lookup	O(E)
Display	Print	O(V + E)
BFS Traversal	Queue	O(V + E)
DFS Traversal	Recursion/Stack	O(V + E)

🎨Basic Graph Operations

Insert Vertex

📌 1. Insert Vertex (Add Vertex)

🧠 Definition:

To add a new node to the graph that does not have any edges yet.

✅ Example:

Let’s add a vertex ‘D’ to this graph:

Before:

A --- B
|
C

After adding ‘D’:

A --- B
|     D
C

➡ ‘D’ is added but has no connections yet.

Delete Vertex

❌ 2. Delete Vertex (Remove Vertex)

🧠 Definition:

To remove a vertex from the graph and all edges connected to it.

✅ Example:

Delete vertex ‘B’ from this graph:

Before:

A --- B
|
C

After deleting ‘B’:

A
|
C

➡ Node B and edge A–B are removed.

Insert Edge

🔗 3. Insert Edge (Add Edge)

🧠 Definition:

To add a connection (edge) between two existing vertices.

✅ Example:

Add an edge between ‘B’ and ‘C’:

Before:

A --- B    C

After adding edge B–C:

A --- B --- C

➡ ‘B’ and ‘C’ are now connected.

Delete Edge

✂️ 4. Delete Edge (Remove Edge)

🧠 Definition:

To remove a connection (edge) between two existing vertices without deleting the vertices.

✅ Example:

Delete edge between A and B:

Before:

A --- B
|
C

After deleting edge A–B:

A     B
|
C

➡ ‘A’ and ‘B’ are now not connected, but both still exist.

🖼️ Combined Mini Diagrams

Operation	Diagram Before	Operation	Diagram After
Insert Vertex	A---B     |     C	Add D	A---B     | D     C
Delete Vertex	A---B     |     C	Remove B	A     |     C
Insert Edge	A---B  C	Add B–C	A---B---C
Delete Edge	A---B     |     C	Remove A–B	A  B     |     C

Diagram of Operations

🌐 Graph Traversal Algorithms

Graph traversal means visiting every node in a graph in a systematic way.

The two main traversal methods are:

1. BFS (Breadth-First Search)

2. DFS (Depth-First Search)

We'll cover both with diagrams, Python code, and explanation.

🔄 1. Breadth-First Search (BFS)

📌 Definition:

• Visits level by level

• Uses queue (FIFO)

• Best for finding shortest paths in unweighted graphs

✅ Python Code:

from collections import deque

def bfs(graph, start):
    visited = set()
    queue = deque([start])

    while queue:
        vertex = queue.popleft()  # remove from front
        if vertex not in visited:
            print(vertex, end=' ')
            visited.add(vertex)
            queue.extend([neighbor for neighbor in graph[vertex] if neighbor not in visited])

✅ Graph Example:

graph = {
    'A': ['B', 'C'],
    'B': ['D', 'E'],
    'C': ['F'],
    'D': [],
    'E': ['F'],
    'F': []
}
bfs(graph, 'A')

🔍 Output:

A B C D E F

🧠 Code Explanation:

• visited: Keeps track of visited nodes

• queue: Holds nodes to explore (FIFO)

• while loop: Runs until queue is empty

• queue.popleft(): Gets next node to visit

• visited.add(): Marks it as visited

• queue.extend(): Adds unvisited neighbors to the queue

🔁 2. Depth-First Search (DFS)

📌 Definition:

• Visits as deep as possible before backtracking

• Uses stack or recursion

• Good for path finding and cycle detection

✅ Python Code (Recursive):

def dfs(graph, start, visited=None):
    if visited is None:
        visited = set()
    print(start, end=' ')
    visited.add(start)
    
    for neighbor in graph[start]:
        if neighbor not in visited:
            dfs(graph, neighbor, visited)

✅ Graph Example:

graph = {
    'A': ['B', 'C'],
    'B': ['D', 'E'],
    'C': ['F'],
    'D': [],
    'E': ['F'],
    'F': []
}
dfs(graph, 'A')

🔍 Output:

A B D E F C

🧠 Code Explanation:

• visited: Keeps track of visited nodes

• Starts from node ‘A’

• Goes to B → D → E → F → C

• Uses recursive calls to go deeper

📊 BFS vs DFS Comparison

Feature	BFS	DFS
Data Structure	Queue (FIFO)	Stack (via recursion or list)
Visit Order	Level-by-Level	Deep First, then backtrack
Finds Shortest Path	✅ Yes	❌ No
Good For	Shortest path, Web crawlers	Maze solving, Topological sort
Time Complexity	O(V + E)	O(V + E)

Where:

• V = number of vertices

• E = number of edges

✅ Summary

• Use BFS when you need the shortest path or work level-wise.

• Use DFS when you want to go deep into paths or solve backtracking problems.

BFS and DFS Traversal in Graph