그래프

dragonappear·2021년 3월 21일
0

Algorithm

목록 보기
5/5

1.그래프

문제에 나와있는 상황을 그래프로 모델링하여 여러 알고리즘을 사용하여 문제를 푼다.

그래프란?

  • 자료구조의 일종

  • 정점(Node ,vertex)

  • 간선(Edge) : 정점간의 관계를 나타낸다.

  • G = (V,E) 로 나타낸다.

경로란?

정점 A에서 B로 가는 경로

  • A>C>D>E>B

  • A>B

  • A>C>B

  • A>C>E>B

사이클

정점 A에서 다시 A로 돌아오는 경로

  • A>C>B>A
  • A>C>E>B>A
  • A>C>D>E>B>A

단순경로와 단순사이클

경로/사이클에서 같은 정점을 두 번 이상 방문하지 않는 경로/사이클

방향있는 그래프

  • A>C와 같이 간선에 방향이 있다.
  • A>C는 있지만, C>A는 없다.

방향없는 그래프

  • A-C 와 같이 간선에 방향이 없다.
  • A-C는 A>C 와 C>A를 나타낸다.
  • 양방향 그래프라고도 한다.

가중치

  • 간선에 가중치가 있는 경우
  • A>B로 이동하는 거리,시간,비용 등등이 있다.
  • 가중치가 없는 경우에는 1이라고 생각하면 된다.

차수

  • 정점과 연결되어 있는 간선의 개수
  • 5의 차수 : 3
  • 4의 차수 : 4
  • 방향 그래프의 경우 In-degree , Out-degree 로 나누어서 차수를 계산한다.

2.그래프의 표현(저장)

그래프의 간선을 저장하는 것이다.

  • 정점: {1,2,3,4,5,6}
  • 간선:{(1,2),(1,5),(2,5),(2,3),(3,3),,(2,4),(4,5),(4,6)}

그래프 간선의 저장법 : 한 정점 X와 연결된 간선을 효율적으로 찾는 구조로 저장해야한다.

1. 인접행렬:

  1. 간선에 가중치가 없을때

  • 정점의 개수를 V라고 할때

  • V*V크기의 이차원 배열을 사용한다.

  • A[i][j] = 1 (i>j 간선이 있을때), 0(없을때)

  1. 간선에 가중치가 있을때:
  • A[i][j] = w (i>j 간선이 있을때, 그 가중치), 0(없을때)

한 정점에 연결된 모든 간선을 찾는데 걸리는 시간: O(V)
공간복잡도 O(V^2)

2. 인접리스트:

  • 리스트를 이용해서 구현한다.

  • A[i]= i와 연결된 정점을 리스트로 포함하고 있음

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

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

한 정점에 연결된 모든 간선을 찾는데 걸리는 시간: O(E)
공간복잡도: O(E)

한 정점에 연결된 모든 간선을 찾을때는 인접리스트를 주로 사용하고, (u,v) 간선이 있는지 없는지 검사할때는 인접행렬을 사용한다.

간선리스트:

  • 배열을 이용해서 구현한다.

  • 간선을 모두 저장한다.

  • 정렬 후 각 각선의 앞 정점을 기준으로 개수를 센다.

문제:

  1. 문제: ABCDE
  • 소스코드
  • 인접행렬, 인접리스트, 간선리스트를 사용해서 풀어보아라.

3.그래프의 탐색

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

1. DFS(깊이우선탐색)

  • 스택을 사용

  • 스택을 이용해서 갈 수 있는 만큼 최대한 많이 가고

  • 갈 수 없으면 이전 정점으로 돌아간다.

  • 모든 정점은 스택에 1번 들어갔다 1번 나온다!

  • check[i]: 정점을 방문했는지 체크하는 배열

과정:

코드:

재귀호출를 이용해서 구현

  1. 인접행렬을 이용한 구현
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)

  1. 인접리스트를 이용한 구현
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)

2. BFS(넓이우선탐색)

  • 큐를 사용

  • 큐를 넣을때 방문했다고 체크해야 한다.

  • 모든 정점은 큐에 1번 들어갔다 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)

  1. 인접리스트를 이용한 구현
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)

문제

  1. 문제 : DFS와BFS

4.연결 요소

  • 연결 요소에 속한 모든 정점을 연결하는 경로가 있어야 한다.

  • 다른 연결 요소에 속한 정점과 연결하는 경로가 있으면 안된다.

  • 위 그래프는 총 2개의 연결 요소로 이루어져 있다

  • 연결 요소를 구하는 것은 DFS 나 BFS 탐색을 이용해서 구할수있다.

문제:

  1. 문제: 연결 요소

5.이분 그래프

  • 그래프를 다음과 같이 A와 B로 나눌 수 있으면 이분 그래프라고 한다.

  • A에 포함되어 있는 정점끼리 연결된 간선 없음

  • B에 포함되어 있는 정점끼리 연결된 간선 없음

  • 모든 간선의 한 끝 점은 A에, 다른 끝 점은 B에 있다.

    그래프를 DFS 혹은 BFS 탐색으로 이분 그래프인지 아닌지 알수있다.

    문제:

  1. 문제: 이분 그래프

6.그래프 문제:

  1. 문제(연결요소): 단지번호 붙이기
    • 소스코드 : BFS
    • 소스코드 : DFS
  2. 문제(): 섬의 개수
  3. 문제(): 미로 탐색
  4. 문제(): 토마토
  5. 문제(): 나이트의 이동

참고:

코드플러스

0개의 댓글