그래프란 무엇인가?
그래프는
정점과간선으로 이루어진 자료구조 입니다.
그래프와 트리는 굉장히 유사합니다. 트리와 차이점은 그래프는 Cyclic하고 트리는 UnCyclic 합니다.
Cyclic이 어떤 차이를 가져올까요?
트리는 한 노드에서 다른 노드로 향하는 방법이 1가지입니다. 그러나 그래프는 Cyclic 하기때문에 한 노드에서 다른 노드로 갈 수 있는 방법이 여러가지 존재할 수 있습니다.
그래프는 무방향 그래프 와 방향 그래프 2가지 종류가 있습니다. 0 노드에서 1 노드로 갈 때 무방향 은 0 -> 1 , 1 -> 0 둘 다 가능합니다. 그러나 방향 그래프 는 1 -> 0 만 가능합니다.
그래프에 대해 깊은 학습을 위해 그래프 구조에 대해 알아보겠습니다.
그래프 구조
- 정점 : 각 노드에 해당합니다. (0, 1, 2, 3)이 해당합니다.
- 간선 : 노드와 노드를 연결하는 선입니다.
- 인접 정점 : 간선 하나를 두고 연결된 정점입니다. 0 을 기준으로 1, 2가 인접 정점입니다.
- 정점의 차수 : 무방향 그래프에서 하나의 정점에 인접한 정점의 수 입니다.
무방향 그래프의 모든 정점 차수의 합 = 그래프 간선 수의 2배 입니다. - 진입 차수 : 방향 그래프에서 외부에서 오는 간선의 수 입니다.
- 진출 차수 : 진입 차수와 반대로 외부로 나가는 간선의 수 입니다.
- 경로 길이 : 경로를 구성하는데 사용된 간선의 수 입니다.
1 -> 0으로 갈 때 1 -> 2 -> 0 은 길이가 2, 1 -> 0 은 길이가 1 입니다. - 단순 경로 : 경로 중에 반복되는 정점이 없는 경우 입니다.
만약 1 -> 2 -> 0 -> 1 -> 3 으로 진행할 수 있다고 할 때 1이 두번 반복되니 단순 경로가 아닙니다. - 사이클 : 단순 경로의 시작 정점과 끝 정점이 동일한 경우입니다.
그래프의 표현
-
무방향의 그래프는
A - B와B - A는 같습니다. 그리고 (A, B) 로 표현합니다. -
방향 그래프는
A -> B,B -> A는 서로 다릅니다. 표현은 <A, B> 로 합니다.
그래프의 구현
그래프 탐색 - DFS
각 노드에 방문했는지 여부를 체크할
배열과스택을 이용하여 구현합니다.
그래프 탐색 - BFS
각 노드에 방문했는지 여부를 체크할
배열과큐를 이용하여 구현합니다.
인접 행렬
간선 정보의
확인과업데이트가 빠릅니다O(1). 그러나메모리 공간을 차지합니다.
- 2차원 배열을 활용하여 구현합니다.
- 2차원 배열은 어떤 노드에서 어떤 노드로 향하는지 정보가 저장되어 있습니다.
- 간선 정보는 인덱싱을 통해 빠른 확인이 가능합니다.
인접 리스트
메모리 사용량이 상대적으로 적고, 노드의
추가삭제가 빠릅니다. 그러나확인이 상대적으로 오래 걸립니다.
인접 리스트 VS 인접 행렬
-
인접 행렬
노드의 개수가 적고 간선의 수가 많을 때는 인접행렬이 유리합니다. 밀집 그래프, 완전 그래프와 같은 형태가 유리합니다.
-
인접 리스트
노드의 개수가 많고 간선의 수가 적을 때 유리합니다. 희소 그래프와 같은 형태가 유리합니다.
그래프 구현
인접 행렬을 이용한 그래프 구현
class MyGraphMatrix {
char[] vertices;
int[][] adjMat;
int elemCnt;
public MyGraphMatrix(){}
public MyGraphMatrix(int size){
this.vertices = new char[size];
this.adjMat = new int[size][size];
this.elemCnt = 0;
}
public boolean isFull() {
return this.elemCnt == this.vertices.length;
}
public void addVertex(char data) {
if (isFull()) {
System.out.println("Graph is Full!!!");
return;
}
this.vertices[elemCnt++] = data;
}
public void addEdge(int x, int y) {
this.adjMat[x][y] = 1;
this.adjMat[y][x] = 1;
}
public void addDirectedEdge(int x, int y) {
this.adjMat[x][y] = 1;
}
public void deleteEdge(int x, int y) {
this.adjMat[x][y] = 0;
this.adjMat[y][x] = 0;
}
public void deleteDirectedEdge(int x, int y) {
this.adjMat[x][y] = 0;
}
public void printAdjacentMatrix() {
System.out.print(" ");
for (char item : this.vertices) {
System.out.print(item + " ");
}
System.out.println();
for (int i = 0; i < this.elemCnt; i++) {
System.out.print(this.vertices[i] + " ");
for (int j = 0; j < this.elemCnt; j++) {
System.out.print(this.adjMat[i][j] + " ");
}
System.out.println();
}
}
}
public class Prac1 {
public static void main(String[] args) {
// TEST CODE
MyGraphMatrix graph = new MyGraphMatrix(4);
graph.addVertex('A');
graph.addVertex('B');
graph.addVertex('C');
graph.addVertex('D');
graph.addEdge(0, 1);
graph.addEdge(0, 2);
graph.addEdge(1, 2);
graph.addEdge(1, 3);
graph.addEdge(2, 3);
graph.printAdjacentMatrix();
}
}인접리스트를 이용한 그래프 구현
class Node {
int id;
Node next;
public Node(int id, Node next) {
this.id = id;
this.next = next;
}
}
class MyGraphList {
char[] vertices;
Node[] adjList;
int elemCnt;
public MyGraphList() {}
public MyGraphList(int size) {
this.vertices = new char[size];
this.adjList = new Node[size];
this.elemCnt = 0;
}
public boolean isFull() {
return elemCnt == this.vertices.length;
}
public void addVertex(char data) {
if (isFull()) {
System.out.println("Graph is Full!!");
return;
}
this.vertices[elemCnt++] = data;
}
public void addEdge(int x, int y) {
this.adjList[x] = new Node(y, this.adjList[x]);
this.adjList[y] = new Node(x, this.adjList[y]);
}
public void addDirectedEdge(int x, int y) {
this.adjList[x] = new Node(y, this.adjList[x]);
}
public void printDirectedEdge() {
for (int i = 0; i < this.elemCnt; i++) {
System.out.print(this.vertices[i] + " : ");
Node cur = this.adjList[i];
while (cur != null) {
System.out.print(this.vertices[cur.id] + " ");
cur = cur.next;
}
System.out.println();
}
}
}
public class Prac2 {
public static void main(String[] args) {
// Test Code
MyGraphList graph = new MyGraphList(4);
graph.addVertex('A');
graph.addVertex('B');
graph.addVertex('C');
graph.addVertex('D');
graph.addEdge(0, 1);
graph.addEdge(0, 2);
graph.addEdge(1, 2);
graph.addEdge(1, 3);
graph.addEdge(2, 3);
graph.printDirectedEdge();
}
}
인접행렬을 이용한 BFS, DFS
class MyGraphMatrix2 extends MyGraphMatrix {
public MyGraphMatrix2(int size) {
super(size);
}
public void dfs(int id) {
boolean[] visited = new boolean[this.elemCnt];
Stack<Integer> stack = new Stack<>();
stack.push(id);
visited[id] = true;
while (!stack.isEmpty()) {
int curId = stack.pop();
System.out.print(this.vertices[curId] + " ");
for (int i = this.elemCnt - 1; i >= 0; i--) {
if (this.adjMat[curId][i] == 1 && visited[i] == false) {
stack.push(i);
visited[i] = true;
}
}
}
System.out.println();
}
public void bfs(int id) {
boolean[] visited = new boolean[this.elemCnt];
Queue<Integer> queue = new LinkedList<>();
queue.offer(id);
visited[id] = true;
while (!queue.isEmpty()) {
int curId = queue.poll();
System.out.print(this.vertices[curId] + " ");
for (int i = this.elemCnt - 1; i >= 0; i--) {
if (this.adjMat[curId][i] == 1 && visited[i] == false) {
queue.offer(i);
visited[i] = true;
}
}
}
System.out.println();
}
}인접리스트를 이용한 BFS, DFS
class MyGraphList2 extends MyGraphList {
public MyGraphList2(int size) {
super(size);
}
public void dfs(int id) {
boolean[] visited = new boolean[this.elemCnt];
Stack<Integer> stack = new Stack<>();
stack.push(id);
visited[id] = true;
while (!stack.isEmpty()){
int cruId = stack.pop();
System.out.print(this.vertices[cruId] + " ");
Node cur = this.adjList[cruId];
while (cur != null) {
if (visited[cur.id] == false) {
stack.push(cur.id);
visited[cur.id] = true;
}
cur = cur.next;
}
}
System.out.println();
}
public void bfs(int id) {
boolean[] visited = new boolean[this.elemCnt];
Queue<Integer> queue = new LinkedList<>();
queue.offer(id);
visited[id] = true;
while (!queue.isEmpty()) {
int cruId = queue.poll();
System.out.print(this.vertices[cruId] + " ");
Node cur = this.adjList[cruId];
while (cur != null) {
if (visited[cur.id] == false) {
queue.offer(cur.id);
visited[cur.id] = true;
}
cur = cur.next;
}
}
System.out.println();
}
}
to mist