[자료구조] 그래프

그래프 

- 연결되어있는 객체간의 관계를 표현한 자료구조

- 오일러 

• 오일러 문제 : 모든 다리를 한번만 건너서 처음 출발했던 장소로 돌아오는 문제
• 위치 : 정점(node), 다리 : 간선(edge)
• 오일러 경로 : 정점에 연결된 간선의 개수가 짝수이면 존재

용어

그래프 G = (V , E) : 정점과 간선의 집합으로 구성된다

- V : 정점들의 집합

- E : 간선들의 집합 

 

인접 정점 : 간선에 의해 연결된정점

>> 그래프에서 두 정점 A와 B가 연결되어 간선 (A, B)가 있을 때, 두 정점 A와B 를 인접한다고 한다.

 

차수 : 그 정점에 인접한 정점의 개수 

 

경로 : 간선으로 연결된 정점을 순서대로 나열한 리스트

- 단순 경로 : 모두 다른 정점으로 구성된 경로

- 사이클 : 단순 경로 중에서 경로의 시작 정점과 마지막 정점이 같은 경로

 

경로의 길이: 경로를 구성하는데 사용된 간선의 수

 

 

종류

(1) 무방향 그래프

: 정점 간의 간선을 통해 양방향으로 이동할 수 있는 그래프

- (A, B) = (B, A)

 

(2) 방향 그래프

: 방향성이 존재하는 간선, 한쪽으로만 이동할 수 있음

- < A, B> != <B , A>

 

(3) 가중치 그래프

: 정점을 연결하는 간선에 가중치(weight)를(또는 비용) 할당한 그래프

- 방향, 무방향 둘 다 될 수 있음

 

(4) 완전 그래프 , 부분 그래프

- 완전그래프는 한 정점에서 다른 모든 정점과 연결되어 최대 간선 수를 갖는 그래프이다

: 정점이 n개인 완전 그래프에서 최대 간선 수는 n(n-1)/2 이고 방향 그래프에서는 n(n-1)

- 부분그래프는 기존의 그래프에서 일부 정점이나 간선이 제외된 그래프이다. 

 

연산

• create_graph() ::= 그래프를 생성한다.
• init(g) ::= 그래프 g를 초기화한다.
• insert_vertex(g,v) ::= 그래프 g에 정점 v를 삽입한다.
• insert_edge(g,u,v) ::= 그래프 g에 간선 (u,v)를 삽입한다.
• delete_vertex(g,v) ::= 그래프 의 정점 v를 삭제한다.
• delete_edge(g,u,v) ::= 그래프 g의 간선 (u,v)를 삭제한다.
• is_empty(g) ::= 그래프 g가 공백 상태인지 확인한다.
• adjacent(v) ::= 정점 v에 인접한 정점들의 리스트를 반환한다.
• destroy_graph(g) ::= 그래프 8를 제거한다.

 

표현방법

1. 인접 행렬(adjacent matrix) ; 2차원 배열 사용
2. 인접리스트(adjacency list); 연결리스트 사용

//인접행렬방법
if(간선 (i, j)가 그래프에 존재)
  M[i][j] = 1,;

else
  M[i][j] = 0;

 

그래프 탐색

1. 깊이 우선 탐색 ( DFS: depth-first search)

트리에서 생각했을 때 트리를 탐색할 때 시작 정점에서 한 방향으로 계속 가다가 더이상 탐색할 수 없으면 다시 가장 가까운 길로 돌아와서 다른 방향으로 다시 탐색을 진행하는 방식과 유사하다

즉 특정 노드에서 시작해 다음 분기로 넘어가기 전에 해당 분기를 완전히 탐색하는 방법이다.

DFS는 스택을 사용해 구현한다.

스택에는 방문한 정점들을 push하고 더 이상 진행하지않으면 인접 노드가 없는 노드는 pop으로 돌아온다.(이는 다시 이전 정점으로 돌아간것과 같다, 마지막으로 방문한 정점 정보는 스택에 저장되어있기 때문)

 

결국 모든 정점을 방문하고 나면 스택에는 아무 데이터도 남아있지 않는 상태가 된다.

 

//DFS 알고리즘
dfs(v)

v를 방문되었다고 표시;
for all u <- (v에 인접한 정점) do
  if(u 가 아직 방문되지 않음) //방문한 곳 = false, 방문 안한 곳 = true
  then dfs(u)

 

동작 순서

1. 현재 정점 v를 방문한다

2. v에 인접한 모든 정점 u 탐색

3. 재귀 호출 - > 현재 정점의 모든 인접 정점이 탐색될 때까지 반복, 탐색 완료되면 재귀 호출 스택에서 탈출

 

---

DFS 구현

1. 스택 구조를 함수 호출로 구현(DFS)
2. 인접 행렬 DFS >> 모든 정점 탐색
3. 인접 리스트 DFS >> 인접한 정점만 탐색(시간 단축)

인접행렬 DFS

//DFS 인접 행렬
void dfs_matrix(GraphType *g, int v)
{
  int w;
  visited[v] = TRUE; //정점 v 방문표시
  printf("%d", v); //방문한 정점 출력
  for(w = 0; w<g->n; w++) //그래프의 정점 개수 g->n 만큼 반복
  if(g->adf_matrix[v][w] && !visited[w]) //g->adj_matrix[v][w]를 통해 정점v와 다른 정점 w가 연결되어있는지
                                         //!visited[w] 는 아직 방문하지 않은 정점   
    dfs_matrix(g, w); //재귀 호출
}

 

 

시간복잡도

 

이 DFS 구현의 시간 복잡도는 **O(V²)**입니다.

• 이유: 인접 행렬 기반 탐색에서는 정점 v마다 다른 모든 정점 w를 확인해야 합니다.

비교: 인접 리스트 기반 DFS의 시간 복잡도는 O(V+E)O(V+E), 인접 행렬보다 효율적입니다.

 

 

인접리스트 DFS

//DFS 인접리스트
void dfs_list(GraphType *g, int v)
{
  GraphType *w;
  visited[v] = TRUE;
  printf("%d", v);
  for(w=g->adj_list[v]; w;w=w->link) //정점 v의 인접 리스트를 순회하며 연결된 정점 W->vertex 를 탐색
    if(!visited[w->vertex]) //아직 방문하지 않은 정점에 대해서만 탐색을 진행한다.
      dfs_list(g, w->vertex); //인접 정점 w->vertex를 재귀적으로 호출하여 깊이 탐색
}

 

 

시간복잡도

 

DFS의 시간 복잡도는 그래프의 간선과 정점의 수에 따라 결정됩니다.

• 인접 리스트의 시간 복잡도:
  • O(V + E),
    VV: 정점 수, EE: 간선 수
  • 이유:
    • 모든 정점을 한 번씩 방문 (O(V)O(V)).
    • 각 정점의 모든 간선을 한 번씩 확인 (O(E)O(E)).

비교: 인접 행렬 기반 DFS의 시간 복잡도는 O(V2)O(V2), 인접 리스트가 희소 그래프(간선 수가 적은 그래프)에서 훨씬 효율적입니다.

 

신장트리(spanning tree) 

그래프내의 모든 정점을 포함하는 트리

신장 트리는 모든 정점들이 연결되어 있어야하고 또한 사이클을 포함해서는 안된다.

 

알고리즘

//신장트리
depth_first_search(v)

v를 방문되었다고 표시;
for all u <- (v에 인접한 정점) do
  if(u가 아직 방문되지 않았다면)
    then (v, u)를 신장 트리 간선이라고 표시;
      depth_first_search(u)

 

인접 정점 탐색:

• vv에 인접한 모든 정점 uu를 확인.
• 아직 방문하지 않은 정점 uu에 대해 아래 작업 수행:
  • (v,u)(v,u)를 신장 트리의 간선으로 추가.
  • 정점 uu에 대해 재귀적으로 DFS를 수행하여 트리를 확장.

---

2. 너비우선탐색(BFS)

시작 정점으로부터 가까운 정점을 먼저 방문하고 멀리 떨어져있는 정점을 나중에 방문하는 순회 방법, 큐를 사용해서 구현한다. BFS는 큐를 사용해 구현하며 DFS와 마찬가지로 인접 행렬로 표현된 그래프와 인접 리스트로 표현된 그래프의 경우에 달라진다.

 

BFS 진행 과정

1. 시작정점을 방문하고 큐에 넣는다

2. 큐에서 가장 앞의 노드를 빼고 해당 노드의 인접 정점을 방문하지 않았다면 모두 방문하고 큐에 넣는다

3. 큐가 빌 때까지. 2를 반복한다.

 

BFS 구현