Graph
GitDeveloperKim edited this page Feb 20, 2022
·
81 revisions
- Vertex : 정점
- Edge : 간선
- DAG(Directed Acyclic Graph) : 싸이클이 없는 유향그래프
- 인접 행렬 (Adjacent Matrix) : 2차원 배열로 간단하게 표현, 메모리 낭비가 심하다
- 인접 리스트 (Adjacent List) : List를 이용하여 메모리 낭비가 적다, 구현이 복잡
- 인접 셋 (Adjacency Set)
- 간선의 배열
// list 배열로 그래프 간선 표현하기 -> 어느 한쪽이 고정되어 있을 때 많이 사용
// declare
public static ArrayList< Node > g [];
//init
g = new ArrayList[N+1];
for (int i = 0;i <= N; i++) {
g[i] = new ArrayList<>();
}
//input
for (int e = 1; e <= E; e++) {
st = new StringTokenizer(br.readLine());
int a = Integer.parseInt(st.nextToken());
int b = Integer.parseInt(st.nextToken());
int c = Integer.parseInt(st.nextToken());
// 무방향 그래프
g[a].add(new Node(b,c));
g[b].add(new Node(a,c));
}
// 이중 리스트로 그래프 간선 표현하기 -> 메모리 최적으로 많이 사용된다
// LinkedList 를 사용하면 순차적으로 검색하여 찾아가기때문에 시간초과
// 따라서 ArrayList를 많이 사용
// declare
public static ArrayList < ArrayList < Integer > > graph;
// init
graph = new ArrayList< ArrayList < Integer > >();
// input
for (int i = 0; i < N+1; i++) {
graph.add(new ArrayList());
}
// adjacent list example
for (int i = 0; i < M; i++) {
int []temp = new int[2];
temp[0] = in.nextInt(); // src
temp[1] = in.nextInt(); // dst
graph.get(temp[0]).add(temp[1]); // from src to dst
}
// 한 정점에 붙어있는 인접 행렬 순회할때 참조
for (int[] next : g.get(cur)) { // 간단하게 나타낼수있다
// next ....
}
- 순환하지 않는 방향그래프에서 사용 (DAG: Direct Acyclic Graph)
- 여러가지 답이 존재
- 모든 원소를 방문하기 전에 큐가 빈다면 사이클이 존재한다고 판단
- DFS 로도 구현 가능
- 위상정렬 개념 click
- 진입 차수 (indegree) : 특정한 노드로 들어오는 간선의 개수
- 진출차수 (outdegree) : 특정한 노드에서 나가는 간선의 개수
- 시간복잡도 O(V+E)
- 진입차수가 0인 모든 노드를 큐에 넣는다
- 큐가 빌 때까지 다음의 과정을 반복한다
- 큐에서 원소를 꺼내 해당 노드에서 나가는 선을 그래프에서 제거한다
- 새롭게 진입차수가 0이된 노드를 큐에 넣는다.
- 결과적으로 각 노드가 큐에 들어온 순서가 위상 정렬을 수행한 결과와 같다
// input
for (int i = 0; i < M; i++) {
cin >> a;
cin >> b;
++indegree[b]; // 두번째 도착지 갯수를 저장해둔다
topology[a].push_back(b);
}
// init
queue q;
for (int i = 1; i <= N; i++) {
if (indegree[i] == 0) {
q.push(i);
}
}
// topology sort
while (!q.empty()) {
int temp = q.front();
q.pop();
cout << temp << " ";
for (int i = 0; i < topology[temp].size(); i++) {
if (--indegree[topology[temp][i]] == 0) {
q.push(topology[temp][i]);
}
}
}
for (int i=1; i<=N; i++) {
cycle += indegree[i]; // indegree가 0이 아닌 수가 남아있다? -> 위상정렬 다 못돌린것 -> 사이클 체크
}
- 깊이 우선탐색 (DFS) -> O(N^2) ?확인필요
- 너비 우선탐색 (BFS) -> O(V+E) ?확인필요
- bfs & dfs 코드
- 0-1 BFS dfs vs 01bfs vs 다익스트라
- 0-1 BFS 시간 복잡도 O(E+V) click
- 0-1 BFS 코드
public static int bfs () {
int answer = 0;
dq = new ArrayDeque<>();
dq.add(new Node(1,1,input[1][1]));
visited[1][1] = true;
while (!dq.isEmpty()) {
Node cur= dq.pollFirst();
answer = cur.sum;
int nx = cur.x;
int ny = cur.y;
if (nx == M && ny == N) {
return answer;
}
for (int i = 0; i < 4; i++) {
nx = cur.x + x[i];
ny = cur.y + y[i];
if (nx < 1 || nx > M || ny < 1 || ny > N)
continue;
if (visited[ny][nx])
continue;
visited[ny][nx] = true;
if (input[ny][nx] == 1) {
dq.addLast(new Node(nx,ny,answer+input[ny][nx])); // 1을 맨 뒤에 넣는다
} else {
dq.addFirst(new Node(nx,ny,answer+input[ny][nx])); // 0을 맨 앞에 넣어 먼저 꺼낸다
}
}
}
return answer;
}
- 비가중 그래프에서 최단 경로
- 가중 그래프에서 최단경로
- 한곳에서 다른 곳으로 이동하는 가장 빠른길 찾기
- 한 도시에서 다른 도시로 데이터를 보내거나 이동하는 가장 경제적인 방법 찾기
- 간선의 가중치가 있는 그래프에서 두 정점 사이의 경로들 중에 간선의 가중치의 합이 최소인 경로
- 다익스트라 최적화
- 특징 : 음의 간선으로 표현, 그리디 알고리즘
- 알고리즘 설명
- 출발 노드 설정
- 최단 거리 테이블 초기화(무한대)
- 방문하지 않은 노드 중에서 최단거리가 가장 짧은 노드 선택
- 해당 노드를 거쳐 다른 노드로 가는 비용을 계산하여 최단거리 테이블 갱신
- 3-4 과정 반복
// 가중치 그래프 init
mat = new ArrayList>();
for (int i = 1 ; i <= n+1; i++) {
mat.add(new ArrayList<>());
}
// 선언부
d = new int [n+1]; // 각 노드에서 최단거리 가중치 저장
path = new int [300]; // 잡하장 개수 <= 200
pq = new PriorityQueue<>((int [] a, int [] b)-> (a[1] > b[1])? 1: -1); // 거리가 짧은 순 오름차순
for (int i = 0; i < m; i++) {
int src = in.nextInt();
int dst = in.nextInt();
int value = in.nextInt();
mat.get(src).add(new int[] {dst, value}); // 양방향 그래프임
mat.get(dst).add(new int[] {src, value}); // 문제에서 "그 사이를 오가는데 필요한 시간"
}
// 다익스트라 알고리즘
public static void dijkstra (int src) {
pq.add(new int[] {src, 0}); // 현재 위치 + 해당 위치에서 가중치, 0 에서 시작
for (int i = 1; i < n+1; i++) {
d[i] = Integer.MAX_VALUE; // 각 시발점마다 초기화
}
d[src] = 0; // 시작점
while (!pq.isEmpty()) {
int [] node = pq.poll(); // 현재 시작점
int cur_node = node[0];
int cur_dist = node[1];
// 최적화 2021-03-26 추가 (나동빈님 다익스트라 강의 참조)
if (cur_dist > d[cur_node]) // 이미 방문이 끝난 것으로 간주
continue;
for (int i = 0; i < mat.get(cur_node).size(); i++) {
int next_node = mat.get(cur_node).get(i)[0];//현재노드에서 다음 노드로 이동할때 cost
int cost = mat.get(cur_node).get(i)[1]; //현재노드에서 다음 노드로 이동할때 cost
if (d[next_node] > cost + cur_dist) {
d[next_node] = cost + cur_dist; //최단거리 배열 업데이트
path [next_node] = cur_node; // 정답 출력을 위 next_node 최단거리를 위한 cur_node 인덱스 저장, 끝점에서 거꾸로 추적할 수 있다
pq.add(new int[] {next_node, d[next_node]}); // 다음노드 큐에 넣기
}
}
}
}
- 모든 간선이 양수인 경우
- 음수 간선이 있는 경우
- 음수 간선 순환은 없는 경우
- 음수 간선 순환이 있는 경우
- 음수 간선의 순환을 감지할 수 있다
- 벨만 포드의 기본 시간 복잡도는 O(VE)로 다익스트라 알고리즘에 비해 느립니다.
- 출발 노드를 설정
- 최단 거리 테이블을 초기화
- 다음 과정을 N-1번 반복
- 전체 간선 E개를 하나씩 확인한다
- 각 간선을 거쳐 다른 노드로 가는 비용을 계산하여 최단 거리 테이블을 갱신
- 만약 음수 간선 순환이 발생하는지 체크하고 싶다면 3번의 과정을 한번 더 수행
- 이때 최단 거리 테이블이 갱신 된다면 음수 간선 순환이 존재
- 다익스트라 알고리즘
- 매번 방문하지 않은 노드 중에서 최단 거리가 가장 짧은 노드를 선택
- 음수간선이 있으면 사용 불가
- 벨만 포드 알고리즘
- 매번 모든 간선을 전부 확인
- 음수 간선 순환 탐지
- 모든 노드에서 다른 모든 노드까지의 최단경로를 모두 계산
- 단계별로 거쳐가는 노드를 기준으로 알고리즘을 수행
- 매 단계마다 방문하지 않은 노드 중에 최단 거리를 갖는 노드를 찾는 과정이 필요없다
- 플로이드 워셜은 2차원 테이블에 최단거리 정보를 저장 (dp)
- 테이블의 크기가 500을 넘어가지 않는경우에 사용
- 각 단계마다 특정한 노드 K를 거쳐 가는 경우를 확인
- a에서 b로 가는 최단 거리보다 a에서 k를 거쳐 b로 가는 거리가 더 짧은지 검사
- 점화식 : Dab = min(Dab, Dak+Dkb)
V = in.nextInt(); // 정점
E = in.nextInt(); // 간선
g = new int[V+1][V+1]; // 경로
for (int i = 0; i <= V; i++) {
for (int j = 0; j <=V; j++) {
g[i][j] = INF; // 최대값으로 세팅
}
}
for (int i = 0; i < E; i++) {
int from = in.nextInt();
int to = in.nextInt();
int value = in.nextInt();
// 경로 채우기
g[from][to] = value;
}
// 거쳐 가는 노드
for (int k = 1; k <= V; k++) {
// 출발 노드
for (int i = 1; i <= V; i++) {
// 도착 노드
for (int j = 1; j <= V; j++) {
g[i][j] = Math.min(g[i][j], g[i][k]+g[k][j]); // 기존 값과 k를 거쳐서 온 값 비교해 최소값 입력, 점화식 암기!!
}
}
}
for (int i = 1; i <= V; i++) {
answer = Math.min(g[i][i], answer); // 출력
}
- 신장 트리는 어떤 그래프의 부분 그래프로 그래프의 모든 노드와 간선 일부를 포함하여 모든 노드간에 경로가 존재하는것
- 연결그래프이며 사이클이 없다
- 최소 신장 트리는 신장 트리 중 가중치가 가장 작은 것을 의미한다
- Prim -> O(n+mlogm)
- Kruskal -> O(mlogm)
- n : 노드 / m : 간선
- 사이클 판별 알고리즘
- 각 간선을 하나씩 확인함 두 노드의 루트 노드를 확인
- 루트 노드가 서로 다르다면 두 노드에 대하여 합집합(Union) 연산을 수행
- 루트 노드가 서로 같다면 사이클이 발생
- 그래프에 포함되어 있는 모든 간선에 대하여 1번 과정 반복
- 참고로 방향 그래프에서의 사이클 여부는 DFS를 이용하여 판별
- union-find
- 백준1197 최소 스패닝 트리 소스
class Node implements Comparable{
int src;
int dst;
int weight;
Node (int s, int d, int w) {
src = s;
dst = d;
weight = w;
}
@Override
public int compareTo(Node o) {
return this.weight - o.weight;// 가중치로 오름차순 정렬
}
}
Collections.sort(arr); // 가중치로 오름차순 정렬
answer = 0;
for (Node node : arr) {
// 부모노드가 같은지 보고
if (find(node.src) != find(node.dst)) {
answer += node.weight;
// 같지않으면 합쳐준다
union(node.src, node.dst);
}
}
System.out.println(answer);