[자료구조] 인접 행렬(Adjacent Matrix)을 이용한 그래프 구현하기

1. 순차 자료구조 방식을 이용한 그래프 구현: 인접 행렬

그래프를 구성하는 정점과 두 정점을 연결한 간선의 유무를 저장하기 위해서 2차원의 정방 행렬을 사용합니다.

 

n개의 정점을 가진 그래프는 각 정점에 대한 행과 열을 나타내야 하므로 n x n 정방 행렬을 사용하고 두 정점이 인접하면 1, 인접하지 않으면 0으로 표현합니다. 이런 방법으로 그래프를 표현한 행렬을 인접 행렬이라고 합니다.

① 무방향 그래프

무방향 그래프의 인접 행렬 표현

· 임의의 한 정점에서 자기 자신을 가리키는 간선은 없기 때문에 인접 행렬의 대각선은 항상 0입니다.

· 간선 (Vi, Vj)는 간선 (Vj, Vi)와 같은 의미이기 때문에 행렬의 (i, j)값과 (j, i)값은 항상 같습니다. 따라서 무방향 그래프에서 인접 행렬은 대각선을 기준으로 대칭을 이룹니다.

· 행 i의 합은 열 i의 합과 같고 정점 i의 차수가 됩니다.

 

· AdjMatrixForUndirectedGraph

public class AdjMatrixForUndirectedGraph {
	// 그래프를 구성하는 정점과 두 정점을 연결한 간선의 유무를 저장하기 위한 2차원 인접 행렬
	private int matrix[][] = new int[10][10];
	private int totalVertex = 0;

	// 정점 추가
	public void insertVertex() {
		totalVertex++;
	}

	// 두 정점 v1과 v2을 연결하는 간선 추가
	public void insertEdge(int v1, int v2) {
		if (v1 >= totalVertex || v2 >= totalVertex) {
			System.out.println("그래프에 없는 정점입니다.");
		}
		matrix[v1][v2] = 1;
	}

	// 임의의 정점 v의 차수 반환
	public int getVertexDgree(int v) {
		int degree = 0;

		if (v >= totalVertex) {
			System.out.println("그래프에 없는 정점입니다.");
			return -1;
		} else {
			for (int i = 0; i < totalVertex; i++) {
				if (matrix[v][i] == 1) {
					degree++;
				}
			}
			return degree;
		}
	}

	// 정점의 개수 반환
	public int getTotalVertex() {
		return this.totalVertex;
	}

	// 간선의 개수 반환
	public int getTotalEdge() {
		int count = 0;
		// 무방향 그래프는 대각선을 중심으로 대칭을 이루기 때문에 대각선을 기준으로 오른쪽 탐색
		for (int i = 0; i < totalVertex; i++) {
			for (int j = i + 1; j < totalVertex; j++) {
				if (matrix[i][j] == 1) {
					count++;
				}
			}
		}
		return count;
	}

	// 그래프 출력
	public void printMatrix() {
		for (int i = 0; i < totalVertex; i++) {
			for (int j = 0; j < totalVertex; j++) {
				System.out.printf("%-2d", matrix[i][j]);
			}
			System.out.println();
		}
	}
}

 

· MainForUndirectedGraph

public class MainForUndirectedGraph {
	public static void main(String[] args) {
		AdjMatrixForUndirectedGraph g = new AdjMatrixForUndirectedGraph();

		// 그래프에 정점 4개 추가
		for (int i = 0; i < 4; i++) {
			g.insertVertex();
		}

		// 정점을 연결하는 간선 추가
		g.insertEdge(0, 1);
		g.insertEdge(0, 3);
		g.insertEdge(1, 0);
		g.insertEdge(1, 2);
		g.insertEdge(1, 3);
		g.insertEdge(2, 1);
		g.insertEdge(2, 3);
		g.insertEdge(3, 0);
		g.insertEdge(3, 1);
		g.insertEdge(3, 2);

		System.out.println("1. 무방향 그래프 G의 인접행렬");
		g.printMatrix();

		System.out.println("\n2. 그래프 G의 정점의 개수: " + g.getTotalVertex());
		System.out.println("\n3. 그래프 G의 간선의 개수: " + g.getTotalEdge());
		System.out.println("\n4. 그래프 G의 각 정점의 차수");
		for (int i = 0; i < 4; i++) {
			System.out.printf("정점 %c의 차수: %d\n", (i + 65), g.getVertexDgree(i));
		}
	}
}

 

· 실행 결과

② 방향 그래프

방향 그래프의 인접 행렬 표현

· 임의의 한 정점에서 자기 자신을 가리키는 간선은 없기 때문에 인접 행렬의 대각선은 항상 0입니다.

· 간선 <Vi, Vj>는 간선 <Vj, Vi>와 다르기 때문에 행렬의 (i, j)값과 (j, i)값은 다릅니다. 따라서 방향 그래프에서 인접 행렬은 대각선을 기준으로 대칭을 이루지 않습니다.

· 방향 그래프에 대한 인접행렬에서 행 i의 합은 정점 i의 진출차수가 되고, 열 i의 합은 정점 i의 진입차수가 됩니다.

 

· AdjMatrixForDirectedGraph

public class AdjMatrixForDirectedGraph {
	// 그래프를 구성하는 정점과 두 정점을 연결한 간선의 유무를 저장하기 위한 2차원 정방 행렬
	private int matrix[][] = new int[10][10];
	private int totalVertex = 0;

	// 정점 추가
	public void insertVertex() {
		totalVertex++;
	}

	// 두 정점 v1과 v2를 연결하는 간선 추가
	public void insertEdge(int v1, int v2) {
		if (v1 >= totalVertex || v2 >= totalVertex) {
			System.out.println("그래프에 없는 정점입니다.");
		}
		matrix[v1][v2] = 1;
	}

	// 임의의 정점 v의 진출차수 반환
	public int getVertexOutDegree(int v) {
		int outDegree = 0;

		if (v >= totalVertex) {
			System.out.println("그래프에 없는 정점입니다.");
			return -1;
		} else {
			for (int i = 0; i < totalVertex; i++) {
				if (matrix[v][i] == 1) {
					outDegree++;
				}
			}
			return outDegree;
		}
	}

	// 임의의 정점 v의 진입차수 반환
	public int getVertexInDegree(int v) {
		int inDegree = 0;

		if (v >= totalVertex) {
			System.out.println("그래프에 없는 정점입니다.");
			return -1;
		} else {
			for (int i = 0; i < totalVertex; i++) {
				if (matrix[i][v] == 1) {
					inDegree++;
				}
			}
			return inDegree;
		}
	}

	// 임의의 정점 v의 차수 반환
	public int getVertexDegree(int v) {
		int degree = 0;

		if (v >= totalVertex) {
			System.out.println("그래프에 없는 정점입니다.");
			return -1;
		} else {
			// 방향 그래프 정점 v의 차수 = 정점 v의 진출차수 + 정점 v의 진입차수
			degree = getVertexOutDegree(v) + getVertexInDegree(v);
			return degree;
		}
	}

	// 정점의 개수 반환
	public int getTotalVertex() {
		return this.totalVertex;
	}

	// 간선의 개수 반환
	public int getTotalEdge() {
		int count = 0;
		// 방향 그래프는 대각선을 중심으로 대칭을 이루기 않기 때문에 인접 행렬 전체를 탐색
		for (int i = 0; i < totalVertex; i++) {
			for (int j = 0; j < totalVertex; j++) {
				if (matrix[i][j] == 1) {
					count++;
				}
			}
		}
		return count;
	}

	// 그래프 출력
	public void printMatrix() {
		for (int i = 0; i < totalVertex; i++) {
			for (int j = 0; j < totalVertex; j++) {
				System.out.printf("%-2d", matrix[i][j]);
			}
			System.out.println();
		}
	}
}

 

· MainForDirectedGraph

public class MainForDirectedGraph {
	public static void main(String[] args) {
		AdjMatrixForDirectedGraph g = new AdjMatrixForDirectedGraph();

		// 그래프에 정점 4개 추가
		for (int i = 0; i < 4; i++) {
			g.insertVertex();
		}

		// 정점을 연결하는 간선 추가
		g.insertEdge(0, 1);
		g.insertEdge(0, 3);
		g.insertEdge(1, 2);
		g.insertEdge(1, 3);
		g.insertEdge(2, 3);

		System.out.println("1. 방향 그래프 G의 인접행렬");
		g.printMatrix();

		System.out.println("\n2. 그래프 G의 정점의 개수: " + g.getTotalVertex());
		System.out.println("\n3. 그래프 G의 간선의 개수: " + g.getTotalEdge());
		System.out.println("\n4. 그래프 G의 각 정점의 차수");
		for (int i = 0; i < 4; i++) {
			System.out.printf("정점 %c의 차수 = %d, 진입차수 = %d, 진출차수 = %d\n", (i + 65), g.getVertexDegree(i),
					g.getVertexInDegree(i), g.getVertexOutDegree(i));
		}
	}
}

 

· 실행 결과