그래프

그래프

문제의 여러가지 상황들을 그래프로 그린 다음 그래프 알고리즘을 적용

 

 

출처: 최백준알고리즘강의

그래프의 표현

 

그래프 저장 방법

 

1. 인접 행렬

공간 복잡도: O(V^2)

 

2. 인접 리스트

공간 복잡도: O(E)

- 리스트는 크기를 동적으로 변경할 수 있어야 한다.

- 링크드 리스트나 길이를 동적으로 변경할 수 있는 배열을 사용한다

 

그래프의 탐색

목적: 임의의 정점에서 시작해서 연결되어 있는 모든 정점을 1번씩 방문하는 것

 

DFS: 깊이 우선 탐색 --> 스택 이용

BFS: 너비 우선 탐색 -->큐 이용

 

DFS(깊이 우선 탐색)

스택을 이용해서 갈 수 있는 만큼 최대한 많이 가고, 갈 수 없으면 이전 정점으로 돌아간다

 

재귀 호출을 통해서 구현할 수 있다

 

* 인접 행렬을 이용한 구현

void dfs(int x)
{
	check[x]=true;
    for(int i=1;i<=n;i++)
    {
    	if(a[x][i]==1 && check[i]==false)
        {
        	dfs(i);
        }    
    }
}

 

* 인접 리스트를 이용한 구현

void dfs(int x)
{
	check[x]=true;
    for(int i=0;i<a[x].size();i++)
    {
    	int y=a[x][i];
        if(check[y]==false)
        {
        	dfs(y);
        }
    }
}

 

 

BFS(너비 우선 탐색)

- 큐를 이용해서 지금 위치에서 갈 수 있는 것을 모두 큐에 넣는 방식

- 큐에 넣을 때 방문했다고 체크해야 한다

 

BFS의 구현은 큐를 이용해서 할 수 있다

 

* 인접 행렬을 이용한 구현

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]==1 && check[i]==false)
        {
        	check[i]=true;
            q.push(i);
        }
    }
}

 

*인접 리스트를 이용한 구현

queue<int> q;
check[1]=true;
q.push(1); //시작

while(!q.empty())
{
	int x=q.front();
    q.pop();
    for(int i=1;i<a[x].size();i++)
    {
    	int y=a[x][i];
        if(check[y]==false)
        {
        	check[y]=true;
            q.push(y);
        }
    }
}