그래프 개념과 탐색

 

그래프 개념

• 오래된 그래프 문제로 다음과 koenigsberg 다리 문제가 있다.
• 임의의 한곳(A,B,C,D)에서 출발하여 a부터 f까지 “모든 다리를 한 번씩 건널 수 있는가? 하는 문제이다.
•  

정의

• 그래프의 수학적 정의
  • 그래프 : G(V,E)이고 V,E는 다음과 같다.
    • V(G): 정점
    • E(G) : 간선, 정점을 연결하는 선, VXV의 부분집합
  • 우방향 그래프 : 예를 들면 쌍방 통행이 가능한 도로의 지도이다.
    • 정점을 연결하는 선에 방향이 없다
  • 방향 그래프 : 예를 들면 일방 통행만 있는 도로의 지도이다
    • 정점을 연결하는 선에 방향이 있다.
• 그래프의 예와 수학적인 표현 : 그래프를 표현하는 방법은 여러 가지이다. 아래 방법은 그림으로 그리는 그래프의 모습과 수학적인 기로호 표현하는 방법이다.

• 그래프에서의 제한 사항
  1. 자기 자신을 향하는 간선은 없다
  2. 중복된 간선을 허용하지 않는다.

 

용어들

1. 완전그래프
   • 그래프에서 간선의 수가 최대인 그래프를 말한다.
   • 정점이 3개인 그래프는 간선의 최대 개수가 3개 정점이 4개인 그래프는 간선의 최대 개수는 6개이다
   • 정점이 n개면?
     • 무방향
       • n(n-1)/2
     • 방향그래프
       • n(n-1)
2. 인접
   • 무방향 그래프에서 정점 a,b에 대하여 간선(a,b)가 있으면 정점 a는 정점 b에 인접이라고 한다.
3. • 무방향 그래프에서 정점 a,b에 대하여 간선(a,b)가 있으면 간선 (a,b)는 정점 a와 정점 b에 부속한다고 한다.부속
4. 부분그래프
5.  경로
   • 정점 vp에서 정점 vq으로 가는 경로
   • 정점의 연속인 vp, v1, v2,v3,…,vn-1, vq가 다음과 같은 간선이 존재 할 때 정점 vq에서 정점 vp로 가능 경로가 있다고 한다.
   • 방향 그래프에서 다음의 간선들이 존재한다.
   • <vp,v1>,,,,
6. 경로의 길이
   • 경로상에 있는 간선의 수
   • n개의 엣지를 지나며 총 n+1개의 노드를 거친다
7. 단순 경로
   • 처음과 마지막을 제외하고 정점이 모두 다른 경로, 즉 겨오상의 정점이 중복되지 않는 경로를 단순 경로라고 한다.
8. 사이클
   • 처음과 마지막 정점이 같은 단순 경로 즉 단순 경로 중 경로가 다시 원점에 도달하는 경우이며 사이클을 형성한다
   • 방향성 그래프에서는 방향성 사이클이라 한다
9. 연결됨
   • 정점 v0와 정점 v1이 연결되 있다는 것은 그래프 G에서 정점 v0에서 v1로 가는 경로가 있는 경우이다.
   • 지도에서 말하면 통행로가 있는 경우이다.
10. 연결된 부분
    • 부분 그래프에서 최대로 연결된 그래프, 즉 그래프에서 모든 정점이 연결되지 않을 수 있다. 이 경우 최대로 연결된 부분 그래프를 connected component라고 한다.
    
11. 트리
    • 트리를 그래프로 정의할 수 있다. 사이클이 없으며 연결된 그래프로 루트노드가 1개 존재하는 그래프를 트리라고 한다. 트리는 그래프의 일종이다.

그래프의 표현

인접 행렬

• 그래프 G=(V,E), |V|=n(≥1)일 때 그래프를 이차원 행렬에 다음과 같이 저장하는 방법이다
• 필요한 기억장소 크기 = 공간복잡도 : S(n)=n^2
• 무방향 그래프에서는 행렬이 대각선을 중심으로 대칭이다.

 

인접리스트

• n개의 연결리스트로 그래프를 표현한다. 그래프의 각 정점에 대하여 정점과 연결된 간선을 한 개의 연결리스트에 저장
• 전체 연결리스트는 n개가 되며 이 연결리스트를 배열로 표현한다.

그래프 탐색

깊이 우선 탐색(DFS)

방법

자동차로 여 행할 경우 방문지가 있으면 무조건 방문하는 방법이다. 즉 후진하지 않고 가는 방법이며 후진하는 경우는 길이 막히거나, 이미 방문했던곳일 경우이다. 후진하여 방문할 곳은 마지막에 갈수 있었던 곳 중 가지 않았던 1길이다:

이 방법을 깊이 우선 탐색이라고 하며 탐색 중 방문 가능한 곳은 스택 자료를

이용하여 저장해 둔다.

1. 단계 : 하나의 노드를 택한다.
2. 단계 • 노드를 방문하여 필요한 작업을 한 다음 연결된 다음 노드를 찾는다. 현재 방문
   • 노드는 스택에 저장한다. 2단계를 반복하면서 방문을 계속한다. 막히면 3단계로 간다.
3. 단계 : 더 이상 방문할 노드가 없으면 스택에서 노드를 쫴내 다음 방문 노드를 찾아 2)번 과정을 다시 반복한다.

특징

• 스택을 이용한다.
• visited[MAX_VERICES] 배열을 사용하여 방문했던 것을 표시한다.초기 값은 FALSE 이고 방문하면 TRUE

#define FALSE 0

#define TRUE 1

short int visited[MAX_VERTICES];

 

넓이 우선 탐색(BFS)

방법

자동차로 여행할 경우 가까운 곳 부터 방문하는 방법이다.즉 어느지점에서 가까운 곳을 방문하고 다음 방문 가능 지점은 모두 저 장해 둔다. 다음 방문자는 항상 저 장해 둔 곳에서 순서대로 꺼 낸다. 예를 들어 종로 1 가에서 시작하여 종로의 버스정류장을 모두 방문해야 한다고 하면 종로 1 가의 한 정류장 거리를 다 방문하고 끝나면 두 정류장 거리에 있는 정류장을 모두 방문하고 이러한 순서로 진행한다. 두 정류장 거리에 있는 정류장들은 첫번째 정류장을 방문할 경우 기억을 해둔다. 먼저 기억된 정류장이 다음 번에 먼저 방문을 하게 된다. 즉 큐의 자료구조를 이용하여 다음 방문지를 선택한다.

1. 단계 : 하나의 노드를 택한다.
2. 단계 : 노드를 방문하여 필요한 작업을 한 다음 연결된 다음 노드를 찾는다.노드들을 큐에 저장한다. 더 이상 방문할 곳이 없으면 3단계로 간다.
3. 단계 : 큐의 맨 앞의 노드를 빼내 2단계를 반복한다.

특징

• 큐를 이용한다.
• visited[MAX_VERTlCES] 배열을 사용하여 방문했던 것을 표시한다.

초기 값은 FALSE 이고 방문하면 TRUE

#define FALSE 0

#define TRUE 1

short int visited [MAX_VERTICES] ;