In this article, we will solve an algorithm problem to prepare for a Java coding test. The topic is “Finding the Order of Building Construction.” This problem combines graph traversal algorithms and sorting algorithms that can be utilized in various fields. I will explain the theoretical background and code implementation methods needed to solve the problem in detail.
Problem Description
You are planning to construct several buildings in a city. Each building has an order based on its dependencies with one another. In other words, if building A must be constructed before building B, then the dependency is represented as A -> B. You need to solve the problem of determining the construction order of all buildings according to these rules.
Below is the number of buildings N and the dependency information given as input. You need to output the construction order of all buildings.
For example, let’s assume the following dependencies are given:
5 4
2 1
3 1
4 2
5 3
This input indicates that there are 5 buildings and the following dependencies exist.
Building 1 must be constructed after building 2, building 1 after building 3, building 2 after building 4, and building 3 after building 5.
In this case, a possible construction order of the buildings could be:
1, 2, 3, 4, 5 or 1, 2, 3, 5, 4, etc.
Strategy for Problem Solving
To solve this problem, we can utilize the concept of topological sorting from graph theory. Topological sorting is the act of arranging all vertices (nodes) in a directed graph according to the direction of the edges. In this case, if there is an edge A -> B, A must come before B.
The main steps of the algorithm are as follows:
- Implement the graph in the form of an adjacency list.
- Calculate the in-degree of each node.
- Add the nodes with an in-degree of 0 to a queue to start processing.
- While removing nodes from the queue, record the order and decrease the in-degree of the other connected nodes. If any node’s in-degree becomes 0, add it back to the queue.
- Repeat until all nodes are processed.
Java Implementation Code
Based on the algorithm described above, let’s implement the code in Java. Below is the Java code that performs topological sorting.
public class BuildingOrder {
import java.util.*;
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
// Receiving input for buildings and dependencies
int N = scanner.nextInt(); // Number of buildings
int M = scanner.nextInt(); // Number of dependencies
List> graph = new ArrayList<>();
int[] inDegree = new int[N + 1]; // In-degree
for (int i = 0; i <= N; i++) {
graph.add(new ArrayList<>());
}
for (int i = 0; i < M; i++) {
int a = scanner.nextInt();
int b = scanner.nextInt();
graph.get(a).add(b);
inDegree[b]++;
}
// Implementing the process to perform topological sorting
StringBuilder result = new StringBuilder();
Queue queue = new LinkedList<>();
// Adding nodes with in-degree of 0 to the queue
for (int i = 1; i <= N; i++) {
if (inDegree[i] == 0) {
queue.offer(i);
}
}
while (!queue.isEmpty()) {
int current = queue.poll();
result.append(current).append(" ");
for (int neighbor : graph.get(current)) {
inDegree[neighbor]--;
if (inDegree[neighbor] == 0) {
queue.offer(neighbor);
}
}
}
// Outputting the result
System.out.println("Construction order of buildings: ");
System.out.println(result.toString().trim());
scanner.close();
}
}
The above code first receives the number of buildings and their dependencies, initializes the graph and in-degrees based on this input, and then determines the construction order through topological sorting and prints it.
Input and Output Examples
Example Input
5 4
2 1
3 1
4 2
5 3
Example Output
Construction order of buildings:
1 2 3 4 5 or 1 2 3 5 4
Advanced Learning
The topological sorting algorithm can be used in many real-world situations. For example, it is useful for project schedule management, grammar parsing in compilers, and solving problems with precedence relationships among multiple tasks. Understanding and effectively utilizing such algorithms can greatly aid in problem-solving not only for coding tests but also across various fields.
Practice Problems:
1. Use topological sorting to determine the construction order for the following graph.
2. Implement the following dependencies and visualize the graph to think about what issues might arise.