[java] 인접 행렬로 그래프 구현하기
그래프는 정점(Vertex)과 간선(Edge)로 구성된 자료구조로, 실세계의 복잡한 관계를 표현할 때 사용됩니다. 이번에는 그래프를 인접 행렬(Adjacent Matrix)을 사용하여 구현하는 방법에 대해 알아보겠습니다.
인접 행렬이란?
인접 행렬은 그래프의 각 정점들 사이의 연결 관계를 2차원 배열로 표현하는 방법입니다. 배열의 각 요소는 각 정점들 사이의 연결 상태를 나타내며, 간선이 존재하면 1로 표시하고 존재하지 않으면 0으로 표시됩니다.
인접 행렬 구현하기
다음은 인접 행렬을 이용하여 그래프를 구현하는 자바 코드 예시입니다.
public class Graph {
private int[][] adjMatrix;
private int numVertices;
public Graph(int numVertices) {
this.numVertices = numVertices;
this.adjMatrix = new int[numVertices][numVertices];
}
public void addEdge(int source, int destination) {
adjMatrix[source][destination] = 1;
adjMatrix[destination][source] = 1;
}
public void removeEdge(int source, int destination) {
adjMatrix[source][destination] = 0;
adjMatrix[destination][source] = 0;
}
public void printGraph() {
for (int i = 0; i < numVertices; i++) {
for (int j = 0; j < numVertices; j++) {
System.out.print(adjMatrix[i][j] + " ");
}
System.out.println();
}
}
}
위의 코드에서 Graph 클래스는 인접 행렬을 이용한 그래프를 구현한 클래스입니다. addEdge() 메소드는 두 정점 사이에 간선을 추가하고, removeEdge() 메소드는 간선을 제거합니다. printGraph() 메소드는 현재 그래프의 상태를 출력합니다.
사용 예시
다음은 위에서 정의한 Graph 클래스를 사용하는 예시입니다.
public class Main {
public static void main(String[] args) {
Graph graph = new Graph(5);
graph.addEdge(0, 1);
graph.addEdge(0, 4);
graph.addEdge(1, 2);
graph.addEdge(1, 3);
graph.addEdge(1, 4);
graph.addEdge(2, 3);
graph.addEdge(3, 4);
graph.printGraph();
}
}
위의 예시 코드에서는 5개의 정점을 가진 그래프를 생성하고, addEdge() 메소드를 사용하여 간선을 추가한 후, printGraph() 메소드를 호출하여 그래프를 출력합니다.
결론
인접 행렬을 사용하여 그래프를 구현하면 간단하고 직관적인 방식으로 그래프를 표현할 수 있습니다. 그러나 정점의 개수가 많아질수록 메모리를 많이 사용하게 되는 단점도 있으므로, 그래프의 크기가 크거나 간선의 개수가 적은 경우에 적합한 자료구조입니다.