In modern algorithm problem solving, graphs are a very important and fundamental data structure. In this article, we will explain the representation of graphs and learn how to solve related problems using C++.
What is a graph?
A graph is a data structure composed of vertices and edges, which is useful for expressing various relationships. For instance, graphs can be utilized in various scenarios such as relationships between users in a social network, connections between cities in a road network, and links between web pages.
Methods of graph representation
Graphs are generally represented in two ways: Adjacency Matrix and Adjacency List. Each method has its own advantages and disadvantages, so it is important to choose the appropriate method according to the nature of the problem.
1. Adjacency Matrix
An adjacency matrix is a way to represent a graph using a two-dimensional array. The size of the matrix is V x V (where V is the number of vertices), and each element of the matrix (i, j) indicates whether there is an edge between vertex i and vertex j.
// Declaration of adjacency matrix in C++
const int MAX = 100; // Maximum number of vertices
int adj[MAX][MAX]; // Adjacency matrix
int V; // Number of vertices
The advantage of an adjacency matrix is that it allows you to check the existence of a specific edge in O(1) time. However, in terms of memory, it uses the square of V, making it inefficient when there are many vertices but few edges.
2. Adjacency List
An adjacency list is a method that uses a list of vertices connected to each vertex. This is more suitable for sparse graphs.
// Declaration of adjacency list in C++
#include
#include
using namespace std;
vector adj[MAX]; // Adjacency list
int V; // Number of vertices
The adjacency list uses memory more efficiently and requires O(E) time to traverse the list of edges.
Problem: Finding Connected Components
In this problem, you need to find all components that are interconnected in the given directed graph. In other words, you need to identify the set of vertices that can be reached starting from a single vertex.
Problem Description
Given the number of vertices V and the number of edges E, with each edge provided as a pair of two vertices, write a program to find and output all connected components in this graph.
Input Format
- First line: Number of vertices V (1 ≤ V ≤ 1000)
- Second line: Number of edges E (0 ≤ E ≤ 10000)
- Next E lines: Each line represents an edge in the form (u, v)
Output Format
Output the number of connected components and the vertices of each component in ascending order.
Problem-solving Process
To solve the problem, we will use an adjacency list to store the graph and find connected components using depth-first search (DFS).
Step 1: Constructing the Adjacency List
First, we need to take the input and construct the adjacency list. We will input the number of vertices and edges and complete the list representing the relationships through each edge.
Step 2: Finding Connected Components with DFS
Whenever a search occurs, we mark the visited vertex, and repeat this until there are no more vertices to visit, thereby finding the components. The implementation of DFS can be easily done recursively.
#include
#include
#include
using namespace std;
vector adj[1001]; // Adjacency list
bool visited[1001]; // Visit check
vector> components; // Store connected components
void dfs(int v, vector &component) {
visited[v] = true; // Mark as visited
component.push_back(v); // Add to the component
for (int u : adj[v]) {
if (!visited[u]) {
dfs(u, component); // Recursion
}
}
}
int main() {
int V, E;
cin >> V >> E;
for (int i = 0; i < E; i++) {
int u, v;
cin >> u >> v; // Input edge
adj[u].push_back(v); // Construct adjacency list
adj[v].push_back(u); // Assuming an undirected graph
}
// Finding connected components for each vertex
for (int i = 1; i <= V; i++) {
if (!visited[i]) {
vector component;
dfs(i, component); // DFS search
components.push_back(component); // Store found component
}
}
// Output results
cout << components.size() << "\n"; // Number of connected components
for (const auto &component : components) {
sort(component.begin(), component.end()); // Sort the component
for (int v : component) {
cout << v << " "; // Output vertices
}
cout << "\n";
}
return 0;
}
The above code implements the logic to find and output connected components from the input graph. It sorts and outputs each component in ascending order.
Conclusion
We have examined the representation of graphs and the process of solving problems using DFS. Graphs play an important role in various algorithm problems, and learning them is fundamental to achieving good results in coding tests. I hope this course enhances your basic understanding of graphs and your problem-solving skills.