Python Coding Test Course, Representation of Graphs

The graph is a mathematical object composed of vertices and edges.
Graphs play a vital role in data structures and are an efficient way to solve various complex problems.
In this article, we will explain the basic concepts of graphs and cover how to represent and explore graphs using Python.

1. Basic Concepts of Graphs

A graph consists of nodes and the edges connecting those nodes. Graphs can be classified into two forms:

  • Directed Graph: A graph where edges have direction. That is, when an edge points from A to B, there may not be an edge from B to A.
  • Undirected Graph: A graph where edges do not have direction. An edge connecting A and B exists in both directions.

2. Representation Methods of Graphs

Graphs can be represented in various ways. The most common methods are:

  1. Adjacency List: Represents the graph by maintaining a list of vertices connected to each vertex. This method is memory efficient.
  2. Adjacency Matrix: Represents all vertices of the graph in a matrix form. Each element of the matrix indicates whether two vertices are connected.

3. Problem Solving: Representation of Graphs

Now, let’s solve a practical problem of representing a graph.

Problem Description

Write a program that receives the number of vertices and the information of edges, and represents the graph in both adjacency list and adjacency matrix forms based on the given information.

Input format:

  • The first line contains the number of vertices N (1 ≤ N ≤ 100).
  • The second line contains the number of edges M (1 ≤ M ≤ 1000).
  • From the third line, the edge information (A, B) is given over M lines. A and B are integers from 1 to N, indicating they are connected.

Output format:

The first line should output the adjacency list, and the second line should output the adjacency matrix. Each vertex starts from 1.

4. Steps to Solve the Problem

The steps to solve the above problem are as follows:

4.1. Input Processing

First, receive the vertex and edge information from the user. Use the input() function in Python to receive input and convert it to the appropriate format.

4.2. Create Adjacency List

The adjacency list uses a list of lists to store the connected vertices for each vertex. Since the vertex numbers start from 1, an empty list is added in advance to match the list’s index.

4.3. Create Adjacency Matrix

The adjacency matrix uses a 2D array to store the connection status between vertices. The initial value is set to 0, and if an edge exists, it is set to 1. In the case of an undirected graph, when there is a connection A-B, both (A, B) and (B, A) in the matrix should be updated.

4.4. Output the Results

Finally, output the created adjacency list and adjacency matrix.

5. Code Implementation

def graph_representation():
    # Input
    N = int(input("Enter the number of vertices (1 ≤ N ≤ 100): "))
    M = int(input("Enter the number of edges (1 ≤ M ≤ 1000): "))
    
    # Initialize adjacency list
    adj_list = [[] for _ in range(N + 1)]
    
    # Initialize adjacency matrix
    adj_matrix = [[0] * (N + 1) for _ in range(N + 1)]
    
    # Input edge information
    for _ in range(M):
        A, B = map(int, input("Enter edge information (A B): ").split())
        adj_list[A].append(B)
        adj_list[B].append(A)  # Undirected graph
        adj_matrix[A][B] = 1
        adj_matrix[B][A] = 1  # Undirected graph
    
    # Output adjacency list
    print("Adjacency List:")
    for i in range(1, N + 1):
        print(f"{i}: {adj_list[i]}")
    
    # Output adjacency matrix
    print("Adjacency Matrix:")
    for i in range(1, N + 1):
        print(" ".join(map(str, adj_matrix[i][1:])))
        
# Function call
graph_representation()

6. Code Explanation

The above Python code consists of the following procedures:

  • Input Processing: Receives the number of vertices and edges, and gets the information for each edge.
  • Initialize Adjacency List: Creates an empty list according to the number of vertices N.
  • Initialize Adjacency Matrix: Initializes a matrix of size N x N to 0.
  • Input Edge Information and Update List/Matrix: Updates the adjacency list and matrix based on the input A, B in a loop.
  • Output Results: Outputs the adjacency list and adjacency matrix respectively.

7. Example Execution

For example, if we have a graph with 5 vertices and 6 edges, the input and output would be as follows:

Enter the number of vertices (1 ≤ N ≤ 100): 5
Enter the number of edges (1 ≤ M ≤ 1000): 6
Enter edge information (A B): 1 2
Enter edge information (A B): 1 3
Enter edge information (A B): 2 4
Enter edge information (A B): 3 4
Enter edge information (A B): 4 5
Enter edge information (A B): 2 5
Adjacency List:
1: [2, 3]
2: [1, 4, 5]
3: [1, 4]
4: [2, 3, 5]
5: [2, 4]
Adjacency Matrix:
0 1 1 0 0
1 0 0 1 1
1 0 0 1 0
0 1 1 0 1
0 1 0 1 0

8. Conclusion

In this lecture, we learned about the concept of graphs and various representation methods. We also learned how to create adjacency lists and adjacency matrices through a problem, enhancing our understanding of the basic structure of graphs. There are many more problems to tackle, such as graph traversal (DFS, BFS), so I hope you build upon this knowledge and move to the next level.

Try solving various graph problems while studying algorithms. Thank you!