The graph is a mathematical object composed of vertices<\/strong> and edges<\/strong>. A graph consists of nodes and the edges connecting those nodes. Graphs can be classified into two forms:<\/p>\n Graphs can be represented in various ways. The most common methods are:<\/p>\n Now, let’s solve a practical problem of representing a graph.<\/p>\n 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.<\/p>\n Input format:<\/p>\n Output format:<\/p>\n The first line should output the adjacency list, and the second line should output the adjacency matrix. Each vertex starts from 1.<\/p>\n<\/blockquote>\n The steps to solve the above problem are as follows:<\/p>\n First, receive the vertex and edge information from the user. Use the 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.<\/p>\n 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.<\/p>\n Finally, output the created adjacency list and adjacency matrix.<\/p>\n The above Python code consists of the following procedures:<\/p>\n For example, if we have a graph with 5 vertices and 6 edges, the input and output would be as follows:<\/p>\n 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.<\/p>\n Try solving various graph problems while studying algorithms. Thank you!<\/p>\n <\/body><\/p>\n","protected":false},"excerpt":{"rendered":"
\n Graphs play a vital role in data structures and are an efficient way to solve various complex problems.
\n In this article, we will explain the basic concepts of graphs and cover how to represent and explore graphs using Python.<\/p>\n1. Basic Concepts of Graphs<\/h2>\n
\n
2. Representation Methods of Graphs<\/h2>\n
\n
3. Problem Solving: Representation of Graphs<\/h2>\n
Problem Description<\/h3>\n
\n
\n
4. Steps to Solve the Problem<\/h3>\n
4.1. Input Processing<\/h4>\n
input()<\/code> function in Python to receive input and convert it to the appropriate format.<\/p>\n4.2. Create Adjacency List<\/h4>\n
4.3. Create Adjacency Matrix<\/h4>\n
4.4. Output the Results<\/h4>\n
5. Code Implementation<\/h3>\n
def graph_representation():\n # Input\n N = int(input(\"Enter the number of vertices (1 \u2264 N \u2264 100): \"))\n M = int(input(\"Enter the number of edges (1 \u2264 M \u2264 1000): \"))\n \n # Initialize adjacency list\n adj_list = [[] for _ in range(N + 1)]\n \n # Initialize adjacency matrix\n adj_matrix = [[0] * (N + 1) for _ in range(N + 1)]\n \n # Input edge information\n for _ in range(M):\n A, B = map(int, input(\"Enter edge information (A B): \").split())\n adj_list[A].append(B)\n adj_list[B].append(A) # Undirected graph\n adj_matrix[A][B] = 1\n adj_matrix[B][A] = 1 # Undirected graph\n \n # Output adjacency list\n print(\"Adjacency List:\")\n for i in range(1, N + 1):\n print(f\"{i}: {adj_list[i]}\")\n \n # Output adjacency matrix\n print(\"Adjacency Matrix:\")\n for i in range(1, N + 1):\n print(\" \".join(map(str, adj_matrix[i][1:])))\n \n# Function call\ngraph_representation()<\/code><\/pre>\n6. Code Explanation<\/h3>\n
\n
7. Example Execution<\/h3>\n
Enter the number of vertices (1 \u2264 N \u2264 100): 5\nEnter the number of edges (1 \u2264 M \u2264 1000): 6\nEnter edge information (A B): 1 2\nEnter edge information (A B): 1 3\nEnter edge information (A B): 2 4\nEnter edge information (A B): 3 4\nEnter edge information (A B): 4 5\nEnter edge information (A B): 2 5\nAdjacency List:\n1: [2, 3]\n2: [1, 4, 5]\n3: [1, 4]\n4: [2, 3, 5]\n5: [2, 4]\nAdjacency Matrix:\n0 1 1 0 0\n1 0 0 1 1\n1 0 0 1 0\n0 1 1 0 1\n0 1 0 1 0<\/code><\/pre>\n8. Conclusion<\/h3>\n