[삼성 알고리즘] 그래프 (1)

그래프는 알고리즘에서 주로 사용되는 수학으로 여러 표현 방법이 있다.(여러 방법으로 그래프를 나타낼 수 있음 이 때 문제 조건이랑 상황에 맞게 표현 방법을 선택해야 함)

 

1. 그래프의 표현

1. 인접 리스트

N번 노드에서 다른 노드로 이동이 가능한 경우 vector나 2차원 배열을 통해 이동가능한 노드 값들을 저장하는 것이다.

예를 들어 vertex 2가 3,1이랑 연결되어 있다면

Vector<int> arr의 arr.at(2)=1,3 값이 들어있다.

위와 같이 딱 연결된 노드 값들만 저장하기 때문에 쓸데없는 저장공간을 가지진 않는다.

 

1. 인접 행렬

해당 방법은 간선을 0,1로 행렬로 나타내는 것이다. 예를 들어 1~4까지의 vertext가 존재한다면

0 0 0 0

0 0 0 0

0 0 0 0

0 0 0 0

과 같이 4x4행렬을 이용하며 두 vertex를 이어주는 간선이 없는 경우에는 0 있는 경우에는 1을 입력

추가로 여기서 가중치가 존재한다면 1이 아닌 가중치 값을 넣을 수 있다.

 

1. 간선 리스트

간선 리스트의 방법은 간선들을 인접리스트와 같이 vector나 배열에 넣어주는 방법이다.

예를 들어 1)의 예시와 같이 vertext 2가 3,1이랑 연결되어있다면

Vector<pair<int,int>> arr 벡터 배열에는

arr.push_back({1,2});

arr.push_back({2,3});

과 같이 간선들을 저장해서 다룬다. 이 경우에는 만약 wegith가 있는 경우 pair가 아닌 triple을 이용해서 처리 한다.

 

 

1. 그래프의 순회

• BFS, DFS
• 사이클

사이클의 존재 여부는 간단한 수식으로 알 수 있다.

N개의 vertex가 존재할 때 N-1개의 간선이 존재한다면 사이클이 없지만 N개 이상의 간선이 존재한다면 이 때는 사이클이 존재하는 경우이다.

• 이분성

이분성이란 노드에 두 가지 색을 입힐 때 이웃된 노드끼리 같은 색을 입히지 않을 수 있는 경우를 말한다   첫 노드를 준으로 DFS등을 통해 순회를 하며서 색칠을 진행하고 이 때 이웃된 색끼리 같은 색이 칠해지지 않는다면 이분성이 확립된다.

만약 이분성이 성립한다면, 첫 노드 색을 정한 순간 모든 노드의 색은 정해진 것과 다름없다.

(여기서 색이 3개이상이면 NP-HARD 문제이다 알고리즘 문제로 나오진 않을듯..)

 

 

1. 그래프의 최단 경로

• 가중치가 없는 경우

해당 경우에는 BFS를 이용하면 최적의 답을 구할 수 있다.

 

• 가중치가 있는 경우

벨만포드 알고리즘 (https://bluemoon-1st.tistory.com/17?category=851281)

다익스트라 알고리즘 (https://bluemoon-1st.tistory.com/16?category=851281)

플로이드-워셜 알고리즘 (https://bluemoon-1st.tistory.com/18?category=851281)

 

• 플로이드-워셜 소스 코드

#include<iostream>

#include<algorithm>>

 

using namespace std;

 

int weights[4][4];

 

int main(void) {

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

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

if (i == j)

weights[i][j] = 0;

else

weights[i][j] = 10000;        //This mean infinity

}

}

weights[0][1] = 7;

weights[0][2] = 5;

weights[1][3] = 3;

weights[2][0] = 2;

weights[2][1] = 1;

weights[2][3] = 8;

weights[3][1] = 4;

weights[3][2] = 2;

 

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

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

if (i == j)

continue;

for (int k = 0; k < 4; k++) {

weights[j][k] = min(weights[j][i] + weights[i][k], weights[j][k]);

}

}

}

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

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

cout << weights[i][j] << " ";

}

cout << endl;

}

return 0;

}