Graph
그래프의 정의
현상이나 사물을 정점과 간선으로 표현한것이 그래프이다.
정점: 대상
간선: 정점들과의 관계
간선으로 연결된 두 정점을 인접하다 라고 한다.
정점 u 간선 v , 표현 => (u,v) , {u,v}
{u,v}, (u-v) 는 무방향 간선
(u,v), (u->v) 는 방향 간선
기본적인 그래프 (무향 그래프)
무향 그래프 + 숫자 => 가중 그래프
무향 그래프 + 화살표 => 방향그래프 (유향 그래프)
그래프의 표현
- 인접행렬
- 그래프가 n*n 행렬 A[][]로 표시됨
- 정점 i와 j의 간선 존재여부를 A[i][j]에 기록
그래프의 용어
차수
특정 정점에 인접한 정점의 수
방향그래프에서는 진입 차수와 진출 차수가 있음
경로
시작정점 u 부터 도착점 v 까지 정점들을 나열하여 표현 [a,b,c,d]
단순 경로
경로상의 정점이 모두 다른경우
사이클
시작지점과 도착지점이 동일한 단순 경로
연결성분
그래프에서 정점들이 연결되어있는 부분
부분 그래프
주어진 그래프의 정점과 간선의 일부분(집합)으로 이루어진 그래프
인접 행렬
기본적인 그래프 (무향 그래프)
행은 본인 열은 대상
012345
0 011101
1 101000
2 110010
3 100001
4 001001
5 100110가중치가 있는 경우
행은 본인 열은 대상
012345
0 097506
1 909000
2 790050
3 500005
4 005001
5 600510유향 그래프
행은 본인 열은 대상
012345
0 011101
1 101000
2 010010
3 100001
4 000001
5 000010가중치도 같음
인접 리스트
인접 리스트 표현
그래프가 n개의 연결 리스트로 표시됨
가중치가 있으면 함께 기록
다음은 그래프의 관계를 리스트로 표현하는 방법이다.
각 배열에 리스트가 존재하고
각 리스트에 노드를 추가한다.
리스트의 값은 간선의 개수
(노드 = 대상의 값 + 링크노드)
가중치가 없는 경우
노드 = 대상의 값을 가지는 노드 + 링크 노드
가중치가 있는 경우
노드 = 대상의 값을 가지는 노드 + 가중치를 가지는 노드 + 링크 노드
인접 배열
인접 배열 표현
하나의 배열로 인접 배열을 처리하는 경우
배열의 시작값이 0 이기 때문에 첫번째 배열의 간선 개수가 1작게 나온다.
인접 해시 테이블
인접 해시 테이블
하나의 배열이 인접 배열의 크기의 2배이다.
DFS BFS
깊이우선 너비우선
DFS
깊이우선탐색방식이다. 즉 트리의 루트부터 리프노드까지 탐색하는 방법이다.
BFS
너피우선탐색방식이다. 즉 트리의 같은 레벨을 우선적으로 탐색후 레벨을 늘려가며 순차적으로 접근한다.
