Binaryseop
[자료구조] 인접 행렬(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));
}
}
}
· 실행 결과
'자료구조' 카테고리의 다른 글
[자료구조] 그래프(Graph)의 개념 설명 (0) | 2021.11.01 |
---|---|
[자료구조] 이진 트리(Binary Tree) 개념과 구현 (3) | 2021.10.30 |
[자료구조] 덱(Deque, Double-ended Queue) 설명 및 구현 (0) | 2021.10.30 |
[자료구조] 연결 큐(Linked Queue) 설명 및 구현 (0) | 2021.10.28 |
[자료구조] 원형 큐(Circular Queue) 설명 및 구현 (0) | 2021.10.28 |