#2-2 자료구조 - Graph

Graph

자바에는 요소들간에 직접적인 관계가 있을 경우, 두 점 사이를 이어주는 선들이 존재한다.

만약 간접적인 관계라면 몇 개의 점과 선에 걸쳐 이어진다.

이 하나의 점을 정점(Vertex)라고 하고, 하나의 선은 간선 (Edge)라고 한다.

Graph의 구조

위와 같은 정점들과 간선의 관계를 표현함에 있어 다양한 표현 방식이 있다.

 

1. [인접 행렬 : Adjacency Matrix]

인접 행렬은 서로 다른 정점들이 인접한 상태인지를 표시한 행렬로 2차원 배열의 형태로 나타낸다.

 

int[][] arr = new [][]{};

A : 0행

B: 1행

C: 2행

arr[0][0]  arr[0][1]  arr[0][2]  => { 0, 0, 1}

arr[1][0]  arr[1][1]  arr[1][2]       { 1, 0, 1}

arr[2][0]  arr[2][1]  arr[2][2]       { 1, 0, 0}

 

위와같이 요소들간의 관계에

간선이 있으면 1로 표기하며, 없으면 0으로 표기한다.

 

코드 예시

private int[][] graph;  // 배열 선언

 

public void setGraph (int size) {

graph = new int [size][size];

 

for ( int i = 0; i < size; i++) {

  for ( int j = 0; j < size; j++ ) {

    graph[i][j] = 0;

    }

  }

}

public int[][] getGraph () {

  return graph;

}

public void addEdge(int from, int to) {

  if(from >= graph.length || to >= graph.length) return;

  graph[from][to] = 1;          // from정점과 to정점 사이의 간선을 1로 추가.

}

 

public void removeEdge(int from, int to) {

  if(from >= graph.length || to >= graph.length) return;

  graph[from][to] = 0;          // from정점과 to정점 사이의 간선을 0으로 삭제.

}

 

2. [인접 리스트 : Adjacency List]

인접 리스트는 각 정점이 어떤 정점과 인접하는지를 리스트의 형태로 표현.

각 정점마다 하나의 리스트를 가지고 있으며, 자신과 인접한 다른 정점을 담고 있다.

인접 리스트의 형태

코드 예시

ArrayList<> graph = new ArrayList<>(); // 리스트 선언

 

public void setGraph (int size) {

for ( int i = 0; i < size; i++) {

graph.add( new ArrayList<>()); // [size만큼 빈 ArraysList 값으로 할당]

  }

}

 

public void addEdge(int from, int to) {

graph.get(from).add(to); // [graph 인접리스트에 추가]

graph.get(to).add(from); 

}

 

public void removeEdge (int from, int to) {

if ( graph.get(from).contains(to)) {

graph.get(from).remove((Integer) to); // [graph 인접리스트에 삭제]

  }

}

 

 

[알아두어야할 그래프 용어]

1. 정점 (Vertex)

노드(node) 라고도 하며, 데이터가 저장되는 그래프의 기본 요소.

 

2. 간선(Edge)

정점을 이어주는 선이며, 정점 간의 관계를 나타낸다.

 

3. 인접 정점(Adjacent Vertex)

하나의 정점에서 간선에 의해 직접 연결되어 있는 정점.

 

4. 가중치 그래프 (Weighted Graph)

연결의 강도(추가적인 정보)가 얼마나 되는지 적혀있는 그래프

 

5. 무방향 그래프(Undirected Graph) // 트리는 DIRECTED 그래프의 일종이지만 위에서 아래로 흐르기에 생략한거임.

네비게이션과 같이 간선의 흐름이 단 방향 (directed) 으로만 되어있지 않은 자유로운 진행이 가능한 그래프.

 

6. 진입차수(in-degree) / 진출차수 (out-degree)

한 정점에 진입(들어오는 간선)하고, 진출(나가는 간선)하는 간선이 몇 개인지 나타냄.

 

7. 인접 (adjacency)

두 정점 간에 간선이 직접 이어져 있다면, 이 두 정점은 인접한 정점이다.

 

8. 자기 루프 (self-loop)

정점에서 진출하는 간선이 자기 자신에게 진입하는 경우이며, 다른 정점을 거치지 않는다.

 

9. 사이클 (Cycle)

한 정점에서 출발하여, 다시 해당 정점으로 돌아갈 수 있다면, 사이클이 있다고 표현한다.

 

 

[그래프의 탐색]

DFS / BFS

DFS / BFS 순서도

1. DFS (stack 기반) 순회 순서 : 루트 > 좌측 자식 노드 기준으로 끝까지 순회했다가 우측 노드로 순회하는 방식.

(1) stack을 만들고 시작할 노드를 stack에 담는다.

(2) stack에 넣었던 요소를 꺼내며 출력한다.

(3) 출력한 요소의 자식 노드를 stack에 넣는다. // 단, 한번 들어갔던 노드는 다시 stack에 넣지 않는다.

 

<DFS를 구현할때 재귀함수를 이용하면 간결한 코드가 가능하다>

Graph 검색 DFS, BFS 구현 - 08:04

 

2. BFS (queue 기반) 순회 순서 : 루트 > 좌측부터 같은 레벨의 자식 노드들 순서로 순회.

(1) queue 만들고 시작할 노드를 queue에 넣는다.

(2) queue에 넣었던 요소를 꺼내며 출력한다.

(3) 출력한 요소의 자식 노드를 queue에 넣는다. // 단, 한번 들어갔던 노드는 다시 stack에 넣지 않는다.