• Hajipur, Bihar, 844101

☰
❮
❯

Python

Introduction to Python

Python Basics

Cotrol Structures

Data Structures

Date and Time

Functions and Module

File Handling

Python OOP

Advanced Concepts

Python DSA

Searching Algorithms

Sorting Algorithms

Python Graphs

← Previous Next →

A Graph is a non-linear data structure that represents relationships between pairs of elements (called nodes or vertices) using edges.

Graphs can be:

  • Directed or Undirected

  • Weighted or Unweighted

🔹 Basic Graph Terms

Term Meaning
Vertex A node in the graph
Edge A connection between two vertices
Adjacent Two vertices connected by an edge
Path A sequence of vertices connected by edges
Degree Number of edges connected to a node

🔹 Representing a Graph in Python

1. Using Adjacency List (Dictionary)
graph = {
    'A': ['B', 'C'],
    'B': ['D'],
    'C': ['E'],
    'D': ['F'],
    'E': [],
    'F': []
}
2. Using Adjacency Matrix
vertices = ['A', 'B', 'C']
matrix = [
    [0, 1, 1],
    [0, 0, 0],
    [0, 0, 0]
]

🔹 Depth-First Search (DFS)

def dfs(graph, node, visited):
    if node not in visited:
        print(node)
        visited.add(node)
        for neighbor in graph[node]:
            dfs(graph, neighbor, visited)

visited = set()
dfs(graph, 'A', visited)

✅ Output:

A
B
D
F
C
E

🔹 Breadth-First Search (BFS)

from collections import deque

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

    while queue:
        vertex = queue.popleft()
        if vertex not in visited:
            print(vertex)
            visited.add(vertex)
            queue.extend(graph[vertex])

bfs(graph, 'A')

✅ Output:

A
B
C
D
E
F

🔹 Directed vs Undirected Graph

  • Directed: Edges have direction → (A → B)

  • Undirected: Edges go both ways (A — B)

🔹 Use Cases of Graphs

  • Social networks (users connected to users)

  • Maps and navigation (cities connected by roads)

  • Web crawlers (pages connected via links)

  • Network routing

  • AI pathfinding (games, robotics)

Practice Questions

Q1. Write a Python program to create an undirected graph with 5 nodes using an adjacency list.

Q2. Write a Python program to implement a function to add new vertices to the graph.

Q3. Write a Python program to traverse the graph using Depth-First Search (DFS).

Q4. Write a Python program to traverse the graph using Breadth-First Search (BFS).

Q5. Write a Python program to count the number of connections (edges) for a given node.

Q6. Write a Python program to check if two nodes are connected directly.

Q7. Write a Python program to list all paths between two nodes using recursion or DFS.

Q8. Write a Python program to convert an adjacency list into an adjacency matrix.

Q9. Write a Python program to mark and print all visited nodes during a DFS traversal.

Q10. Write a Python program to create a weighted undirected graph using a dictionary of dictionaries or a tuple-based structure.

Python Graphs Quiz

Q1: What does a graph consist of?

A. Arrays and lists
B. Trees and nodes
C. Vertices and edges
D. Only numbers

Q2: What type of graph uses arrows to represent edges?

A. Directed
B. Undirected
C. Binary
D. Flow

Q3: Which search visits a node's neighbors first?

A. DFS
B. BFS
C. Inorder
D. Postorder

Q4: What data structure is commonly used for BFS?

A. Stack
B. Queue
C. Set
D. Dictionary

Q5: What is the degree of a vertex?

A. Value of the node
B. Number of digits
C. Number of edges connected
D. Number of neighbors

Q6: In DFS, which structure is used internally?

A. Queue
B. Heap
C. Stack
D. Tree

Q7: Which Python data structure best represents an adjacency list?

A. List
B. Tuple
C. Set
D. Dictionary

Q8: Which type of graph is commonly used to represent road networks?

A. Directed
B. Undirected
C. Cyclic
D. Binary

Q9: How many edges can a complete graph with n vertices have?

A. n
B. n - 1
C. n(n-1)/2
D. 2n

Q10: Which of the following is a real-world graph example?

A. Excel sheet
B. Binary tree
C. Website hyperlinks
D. Stack
← Previous Next →
Login
Go Back Top