문제에 나와있는 상황을 그래프로 모델링하여 여러 알고리즘을 사용하여 문제를 푼다.
자료구조의 일종
정점(Node ,vertex)
간선(Edge) : 정점간의 관계를 나타낸다.
G = (V,E) 로 나타낸다.
정점 A에서 B로 가는 경로
A>C>D>E>B
A>B
A>C>B
A>C>E>B
정점 A에서 다시 A로 돌아오는 경로
경로/사이클에서 같은 정점을 두 번 이상 방문하지 않는 경로/사이클
그래프의 간선을 저장하는 것이다.
그래프 간선의 저장법 : 한 정점 X와 연결된 간선을 효율적으로 찾는 구조로 저장해야한다.
정점의 개수를 V라고 할때
V*V크기의 이차원 배열을 사용한다.
A[i][j] = 1 (i>j 간선이 있을때), 0(없을때)
한 정점에 연결된 모든 간선을 찾는데 걸리는 시간: O(V)
공간복잡도 O(V^2)
리스트를 이용해서 구현한다.
A[i]= i와 연결된 정점을 리스트로 포함하고 있음
리스트는 크기를 동적으로 변경할수있어야한다.
링크드 리스트나 길이를 동적으로 변경할수있는 배열을 사용한다.
한 정점에 연결된 모든 간선을 찾는데 걸리는 시간: O(E)
공간복잡도: O(E)
배열을 이용해서 구현한다.
간선을 모두 저장한다.
임의의 정점에서 시작해서 연결되어 있는 모든 정점을 1번씩 방분하는 것
스택을 이용해서 갈 수 있는 만큼 최대한 많이 가고
갈 수 없으면 이전 정점으로 돌아간다.
모든 정점은 스택에 1번 들어갔다 1번 나온다!
check[i]: 정점을 방문했는지 체크하는 배열
재귀호출를 이용해서 구현
void dfs(int x){
check[x] = true;
for(int i= 1; i<=n;i++){
if(a[x][i] == true && check[i]==false){
dfs[i];
}
}
}
시간복잡도: O(V^2)
void dfs(int x){
check[x]=true;
for(int i = 1; i<a[x].size();i++){
int y = a[x][i];
if(!check[y]){
dfs(y);
}
}
}
시간복잡도: O(V+E) = O(E)
큐를 사용
큐를 넣을때 방문했다고 체크해야 한다.
모든 정점은 큐에 1번 들어갔다 1번 나온다!
queue<int> q;
check[1]=true;
q.push(1); // 시작
while(!q.empty()){
int x = q.front();
q.pop();
for(int i=1 ; i<=n; i++){
if(a[x][i]==true && check[i]==false){
check[i]= true;
q.push(i);
}
}
}
시간복잡도: O(V^2)
queue<int> q;
check[1]=true;
q.push(1); // 시작
while(!q.empty()){
int x = q.front();
q.pop();
for(int i=1 ; i<=a[i].size(); i++){
int y = a[x][i];
if(check[y]==false){
q.push(y);
check[y]=true;
}
}
}
}
시간복잡도: O(V)
연결 요소에 속한 모든 정점을 연결하는 경로가 있어야 한다.
다른 연결 요소에 속한 정점과 연결하는 경로가 있으면 안된다.
위 그래프는 총 2개의 연결 요소로 이루어져 있다
연결 요소를 구하는 것은 DFS 나 BFS 탐색을 이용해서 구할수있다.
그래프를 다음과 같이 A와 B로 나눌 수 있으면 이분 그래프라고 한다.
A에 포함되어 있는 정점끼리 연결된 간선 없음
B에 포함되어 있는 정점끼리 연결된 간선 없음
모든 간선의 한 끝 점은 A에, 다른 끝 점은 B에 있다.
그래프를 DFS 혹은 BFS 탐색으로 이분 그래프인지 아닌지 알수있다.