Graph 정의
프로그래밍에서의 그래프는 여러개의 점들이 서로 복잡하게 연결되어 있는 관계를 표현한 자료구조 입니다.
단순히 노드와 그 노드를 연결하는 간선을 하라노 모아 놓은 자료구조라고 표현할 수도 있습니다.
* 연결되어 있는 객체 간의 관계를 표현할 수 있는 자료 구조.
→ 활용 : 지도, 지하철노선도, 도로 통행길,
Graph의 종류
무방향 그래프 (Undirected Graph)
* 무방향 그래프의 간선은 간선을 통해서 양 방향으로 갈 수 있다.
* 정범 A와 정점 B를 연결하는 간선은 (A,B)와 같이 정점의 쌍으로 표현한다.
(A,B) == (B,A)
ex) 양방향 통행 도로()
방향그래프 (Directed Graph)
* 간선에 방향성이 존재하는 그래프
* A -> B로만 갈 수 있는 간선은 <A,B>로 표시한다.
<A,B> != <B,A> <ㅡ 둘은 다르다
ex) 일방 통행도로
가중치 그래프(Weighted Graph)
* 간선에 비용이나 가중치가 할당된 그래프
* 네트워크라고도 한다.
ex) 도로의 길이, 통신망 사용료, 도시와 도시의 연결 등..
연결 그래프(Connected Graph) // 비연결 그래프(Disconnected Graph)
연결 그래프 (Connected Graph)
* 모든 두 꼭짓점 사이에 경로가 존재하는 그래프
-> 무방향 그래프에 있는 모든 정점쌍에 대해서 항상 경로가 존재하는 경우
ex) 트리구조(Tree): 사이클을 가지지않는 특징을 가지고 있는 연결 그래프임.
비연결 그래프(Disconnected Graph)
*무방향 그래프에서 특정 정점쌍 사이에 경로가 존재하지 않는 경우
사이클 VS 비순환 그래프
사이클 (Cycle)
* 단순 경로의 시작 정점과 종료 정점이 동일한 경우 (결국 순환한다는 내용)
단순 경로란? : 경로 중에서 반복되는 정점이 없는 경우
비순환 그래프(Acylic Graph)
* 사이클이 없는 그래프이다. (순환하지 않는 그래프)
완전 그래프(Complete Graph)
* 그래프에 속해 있는 모든 정점이 서로 연결 되어있는 그래프.
* 무방향 완전 그래프 (한곳으로 향하는데 모두 연결되어 있는 그래프)
-> 정점의수가 = n 이면 // 간선의수는 n*(n-1) /2 가 된다.
Graph의 표현방식 (그래프를 구현하는 방법 2가지)
인접 리스트
인접 리스트 언제 사용할까?
메모리를 효율적으로 사용하고 싶을때 인접 리스트를 사용하게 된다.
* 인접 행렬은 연결 가능한 모든 경우의 수를 저장하기 때문에 상대적으로 메모리를 많이 차지하게 되는데 그래서 인접 리스트를 가장 일반적으로 많이 사용한다.
모든 정점(혹은 노드)를 인접 리스트에 저장한다. 즉 각각의 정점에 인접한 정점들을 리스트로 표시한다.
** 배열(혹은 해시테이블)과 배열의 각 인덱스마다 존재하는 또 다른 리스트(Array, ArrayList, LinkedList)를 이용해서 인접 리스트를 표현하게 된다.
그래프를 이용하여 DFS 구현해보기 ↓
// 그래프를 이용하여 DFS 구현해보기!
Public class Graph{
private LinkedList<Integer>[] mimi; // 인접 리스트 생성하기.
private int v; // vertex 정점 생성.
// 그래프의 생성 및 초기화 작업
Graph(int v){
this.v = v; // 정점 개수를 초기화해줌
visit = new boolean[v] // 방문했는지 여부를 true false로 확인하기.
mimi = new LinkedList[v+1] // v로 하면 0부터 시작되니 보기 간편하게 1부터 시작하게둠.
// 0은 공백으로 할 것임.
//인접리스트 초기화 작업
for(int i = 0; int < v+1; i++) {
mimi[i] = new LinkedList(); // mimi인접리스트 각 요소를 초기화함.
}
}
//그래프 인자끼리 연결해주기.
void GraphEdge(int v1, int v2){
mimi[v1].add(v2); // 인접리스트의 mimi[v1]에 v2를 추가해 연결해주고.
mimi[v2].add(v1); // 인접리스트의 mimi[v2]에 v1d을 추가해 연결해주기.
}
public static void main(String args[]){
Graph dfs_graph = new Graph(5); // dfs_graph를 만들어주고 Graph에 5인자값 넣기.
dfs_graph.GraphEdge(1,2); // 그래프의 1과 2를 연결하고
dfs_graph.GraphEdge(1,3); // 그래프의 1과 3을 연결하고
dfs_graph.GraphEdge(3,4); // 그래프의 3과 4를 연결하고
dfs_graph.GraphEdge(3,5); // 그래프의 3과 5를 연결하기.
// 인자값 1 부터 출력하기 1부터인 이유는 우리가 v를 보기좋게 v+1부터 했기 때문임.
for(int i = 1; i< dfs_graph.length; i++){
System.out.printLn(i + " : " + dfs_graph.mimi[i]; // 출력할겁니다 i + 스트링" : " 값과 +
// dfs.graph.mimi[i] dfs.graph에 들어가있는. mimi를 출력하는것임.
}
}
}
/*
출력 결과:
1: [2,3] // dfs.graph.GraphEdge로 1에 2,3을 연결해줬고.
2: [1] // dfs_graph.GraphEdge(1,2) 이 메서드로 인해서 1이랑 연결됐고
3: [1,4,5] // dfs_graph.GraphEdge(1,3) 메서드로 1이랑 연결되고, 직접 4와 5를 연결함 dfs_graph.GraphEdge(3,4); dfs_graph.GraphEdge(3,5);
4: [3] // dfs_graph.GraphEdge(3,4)의 이유로 3과 연결됐고,
5: [3] // dfs_graph.GraphEdge(3,4);의 이유로 3과 연결됐다
*/인접리스트는 작성해본 위의 예제와 같이 확인해볼 수 있다.
인접 행렬 [말 그대로 2차원 배열로 구현한 것. ]
인접 행렬 언제 사용할까?
한 개의 큰 표와 같은 모습을 한 인접 행렬은 두 정점 사이에 관계가 있는지, 없는지 확인하기에 용이하다.
ex) A에서 B로 진출하는 간선이 있나 파악하기 위해서 0번재 줄의 1번째 열에 어떤 값이 저장되어있는지 바로 확인하기.
가장 빠른 경로찾기(Shortest Path)에 주로 활용된다. (** 코딩 테스트에서 구현할때 주로 많이 사용된다.)
인접행렬은 말그대로 너무 쉽게 작성할 수 있는데
int[][] mimi = {{0,0,0,0},{0,0,0,0},{0,0,0,0},{,0,0,0}};와 같이 적으면 된다.
0과 1을 이용해 정수 행렬(Integer Matrix)을 사용할 수도 있다.
// 0과 1을 이용해서 정수 행렬을 사용하기.
if(간선 (i,j)가 그래프에 있다면)
matrix[i][j] = 1;
else
matrix[i][j] = 0;ex) 정수 행렬을 활용한 예제 ↓
// 간선은 두개가 이어져 있다는 사실만 알려 줄 뿐 그 외의 정보는 포함하지 않는다.
// 이렇게 추가적인 정보를 파악할 수 없는 그래프를 비가중치 그래프라고 한다.
/*
Ex) 1 서울 / 2 부산 / 3 대전
0 연결되지 않은 상태, 1은 연결된 상태
*/
[1] = [0,1,1] // 1 서울은 부산과 연결되어 있고, 대전과 연결되어 있음.
[2] = [1,0,1] // 2 부산은 서울과 연결되어 있고, 대전과 연결되어 있음.
[3] = [1,1,0] // 3 대전은 서울과 연결되어 있고, 부산과 연결되어 있음.
** 인접 리스트와 인접 행렬의 선택 방법
인접 리스트
그래프 내의 적은 숫자의 간선만을 가지는 *희소 그래프(아래 주석 참고)인 경우 사용.
장점:
* 노드에 인접한 노드들을 쉽게 찾을 수 있다. (연결되어있는 간선의 데이터만 나타내기 때문에 메모리를 적게 차지함.)
* 연결되어 있는 간선의 데이터만 나타내기 때문에 연결되어 있는 모든 노드를 방문하려 할 때 효율적이다.
* 특정 노드의 인접 노드들은 바로 알 수 있다.
단점:
* 노드간의 연결 여부를 확인하기 위해서는 모든 노드를 탐색해야해서 비효율적이다.
인접 행렬
그래프에 간선이 많이 존재하는 *밀집 그래프(아래 주석 참고) 의 경우 사용.
장점:
노드 간의 연결 정보를 바로 알 수 있으며 구현이 쉽다. (두 정점을 연결하는 간선의 존재 여부 M[i][j]를 빠르게 알 수 있다.)
단점:
* 어떤 노드에 인접한 노드를 찾기 위해서는 모든 노드를 전부 순회해야 한다.
-> (특정 노드 N을 방문하기 위해서 Graph[i][0]부터 Graph[i][N]까지 모두 확인해봐야 하기때문에 비효율적이다.
* 모든 노드의 관계를 기록하기 때문에 크기가 커질수록 메모리를 많이 차지한다.
인접 리스트와 인접 행렬의 선택 방법 결론:
간선이 많고 적음을 근거로 판단하면 된다.
간선이 많을때에는 인접행렬 사용. : 빠르게 연결 여부를 확인 할 수 있기 때문에.
간선이 적을때에는 인접 리스트 사용. : 인접 노드를 빠르게 알 수 있기 때문에.
깊이 우선 탐색 DFS(Depth-First Search) 너비 우선 탑색BFS(Breadth-First Search)은 할말도 많고
중요한 내용이기에 다음 포스팅에서 다뤄보도록 하겠다.
TIL:
그래프의 개념과 특징을 파악했고, 코드로도 직접 작성 해보고 알고리즘 문제도 풀어보았다. ♥
오늘도 열심히 살았다!! ㅎㅎ
주석:
희소 그래프(Sparse Graph) : 간선이 얼마 없는 그래프는 희소 그래프.
밀집 그래프(Dense Graph) : 간선의 수가 최대 간선의 수에 가까운 그래프.
단어 설명:
정점(Vertex) : 노드라고도 하며 데이터가 저장되는 그래프의 기본 원소이다.
간선(Edge) : 정점 간의 관계를 나타냅니다. (정점을 이어주는 선이다.)
인접(Adjacent): 두 정점 간에 간선이 직접 이어져 있다면 이 두정점은 인접한 정점이다.
인접 정점(Adjacent vertex): 하나의 정점에서 간선에 의해 직접 연결되어 있는 정점을 뜻한다.
가중치 그래프(Weighted Graph): 연결의 강도(추가적인 정보가 주어짐)가 얼마나 되는지 적혀있는 그래프
비가중치 그래프(Unweighted Graph): 연결의 강도가 적혀있지 않은 그래프
무(방)향 그래프(Undirected Graph): 서울에서 부산으로 갈 수 있듯이 부산에서도 서울로 갈 수 있다.
하지만 단방향(Directed) 그래프로 구현된다면 서울에서 부산은 갈 수 있지만 부산에서 서울을 가지는 못한다.
즉 무방향 -> 양방통행
단방향 -> 일방통행 으로 이해하면 쉽다.
진입차수(in-degree) / 진출차수(out-degree) : 한 정점에 진입(들어오는 간선)하고 진출(나가는 간선)하는 간선이 몇개인지를 나타낸다.
자기 루프(Self loop): 정점에서 진출하는 간선이 곧바로 자기 자신에게 진입하는 경우 자기 루프를 가졌다 라고 표현한다.
다른 정점을 거치지 않는다는것이 특징이다.
사이클(Cycle): 한 정점에서 출발해서 다시 해당 정점으로 돌아갈 수 있다면 사이클이 있다라고 표현한다.
위에 코드블럭에 예시를 적은 네비게이션 그래프는 서울 -> 대전 -> 부산 -> 서울로 이동이 가능하기에 사이클이 존재하 는 그래프 이다.
Tree 구조란?
https://mininkorea.tistory.com/31
Tree 구조 (트리 구조) 자료구조 / 트리 순회 방법 세가지 전위, 중위, 후위 순회 알고리즘 문제
Tree(트리) 구조란? 자료구조 Tree는 이름 그대로 나무를 거꾸로 뒤집은 형태를 가지고 있습니다. 트리구조는 하나 이상의 데이터에 무방향으로 연결된 계층적 자료구조입니다. 데이터를 순차적으
mininkorea.tistory.com
이미지 출처
https://en.wikipedia.org/wiki/Graph_theory
'JAVA' 카테고리의 다른 글
| Tree 구조 (트리 구조) 자료구조 / 트리 순회 방법 세가지 전위, 중위, 후위 순회 알고리즘 문제 (0) | 2023.01.18 |
|---|---|
| JSON 직렬화, 역직렬화 Convert Java Object to JSON (0) | 2023.01.13 |
| 객체지향 프로그래밍 - 클래스(Class)와 객체(Object) // (개발자 기초용어) *알기쉽게 정리 (2) | 2022.12.27 |
| StringBuffer 와 String 의 차이점? (0) | 2022.12.26 |
| Java 문자열 뒤집기 StringBuilder.reverse() (Reverse Stirng ) (0) | 2022.12.26 |
댓글