[자료구조 스터디] chap.10 그래프 I

10.1 그래프란?

10.2 그래프의 정의와 용어

10.3 그래프의 표현 방법

10.4 그래프의 탐색

10.5 깊이 우선 탐색

10.6 너비 우선 탐색

10.1 그래프란?

그래프(graph)

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

- ex) 트리, 전기회로 소자 연결, 지도 도시 연결

오일러 정리

- 오일러 문제: 모든 다리 "한번씩만" 건너서 처음 출발 장소로 return

- bridge = edge or link 간선

- region = vertex or node 정점

- 모든 정점에 연결된 간선의 수가 짝수이면 오일러 경로 존재!!

10.2 그래프의 정의와 용어

그래프 정의

- G = (V, E)

정점 (vertices) = node

= 여러가지 특성 가질 수 있는 객체를 의미

- V(G) : 그래프 G의 정점들 집합

- |V| = 총 정점 개수

간선 (edge) = link

= 정점들 간의 관계를 의미

- E(G) : 그래프 G의 간선들 집합

- |E| = 총 간선 개수

그래프 종류

undirected graph 무방향 그래프

V(G1) = {0, 1, 2, 3}

E(G1) = {(0,1), (0,2), (0,3), (1,2), (2,3)}

ㄴ 방향 x undirected graph

- 무방향 그래프 정점의 차수 : 하나의 정점에 연결된 다른 정점 수

ㄴ 정점 0의 차수: 3

∑ 정점차수 = 간선수 X 2

- 인접정점 : 하나의 정점에서 간선에 의해 직.접. 연결된 정점

ㄴ 정점 0의 인접 정점: 정점1, 2, 3

directed graph 방향 그래프

V(G3) = {0, 1, 2}

E(G3) = {<0,1>, <1,0>,<1,2>}

ㄴ 방향 ㅇ directed graph

- 방향 그래프 정점의 차수

=> 진입 차수: 외부에서 오는 간선의 수 / 진출 차수: 외부로 향하는 간선의 수

정점 1의 차수 : 내차수(in-degree) 1 , 외차수(out-degree) 2

∑ 진입 or 진출 차수 = 간선수

(the higher degree, the higher connectivity)

weighted graph 가중치 그래프 (=네트워크)

- 간선에 비용(cost)나 가중치(weight)가 할당

<== ex)

정점: 각 도시

간선: 도시 연결하는 도로

가중치: 도로의 길이

subgraph 부분 그래프

- V(G)와 E(G)의 부분집합으로 이루어진 그래프

- 그래프 G1의 부분 그래프들

V(S) ⊆ V(G)

E(S) ⊆ E(G)

그래프의 경로(path)

- 무방향 그래프의 정점 s로부터 정점 e까지의 경로

=> 정점의 나열 s, v1, v2, ..., vk, e

=> 나열된 정점들 간에 반드시 간선 (s,v1), (v1, v2), ..., (vk, e) 존재

- 단순 경로(simple path) : 경로 중에서 반복되는 노드 X 경로

- 사이클(cycle) : 단순 경로의 시작 정점 = 종료 정점

- 단순 사이클(simple cycle) : 시작점 = 종료점 경로 , 반복 노드 X

**오일러사이클 (모든 간선 한번만 건너 처음으로 돌아오는) 은 simple cycle (X)

**해밀턴사이클 (모든 정점 한번만 방문하여 제자리 돌아오는)은 simple cycle (O)

그래프의 연결 정도

- 연결 그래프(connected graph) : 무방향 그래프의 모든 정점 쌍에 대하여 항상 경로 존재

- bridge : 없어지면 비연결 그래프가 되는 간선

- 완전 그래프(complete graph) : 모든 정점이 서로 연결되어 있는 그래프

=> n개의 정점 무방향 완전그래프의 간선 수 : n X (n-1) / 2

그래프 표현 방법 2가지

인접 행렬 방법 (2차원 배열 사용)

if ( 간선 (i, j) 존재) M[i][j] = 1;

else M[i][j] = 0;

=> (b)

degree(i) = ∑(j=0~2) M[i][j]

=> (c)

out_degree(i) = ∑(j=0~2) M[i][j]

in_degree(j) = ∑(i=0~2) M[i][j]

인접행렬의 크기 = |V|^2

인접행렬 값 1 항의 개수 = 2|E| (무방향) or |E| (방향)

인접행렬 알고리즘

#include <stdio.h>
#include <stdlib.h>

#define MAX_VERTICES 50 //최대 50개 노드
typedef struct GraphType
{
   int n; //정점 개수 n=|V| <= MAX_VERTICES(50)
   int adj_mat[MAX_VERTICES][MAX_VERTICES];
} GraphType;


//그래프 초기화
void init(GraphType* g)
{
   int r,c;
   g->n = 0; //정점 총 개수 0개
   for (r=0; r < MAX_VERTICES; r++)
     for (c=0; c < MAX_VERTICES; c++)
        g->adj_mat[r][c] = 0; //간선이 전혀 없다고 초기화 
}


//정점 삽입 연산 
void insert_vertex(GraphType* g, int v)
{
   if (((g->n) + 1) > MAX_VERTICES) //정점개수+1 이 50보다 작으면
   {
      fprintf(stderr, "그래프: 정점의 개수 초과");
      return;
   }
   g->n++;
}


//간선 삽입 연산
void insert_edge(Graphtype* g, int start, int end)
{
   if (start >= g->n || end >= g->n)
   {
      fprintf(stderr,"그래프: 정점 번호 오류");
      return;
   }
   g->adj_mat[start][end]=1; 
   g->adj_mat[end][start]=1; //undirected graph에서 
}


//main 함수 
void main() 
{
   GraphType* g;
   g = (GraphType*)malloc(sizeof(GraphType));
   init(g);
   for(int i=0; i < 4; i++) 
      insert_vertex(g,i);
   
   insert_edge(g,0,1);
   insert_edge(g,0,2);
   insert_edge(g,0,3);
   insert_edge(g,1,2);
   insert_edge(g,2,3);
   print_adj_mat(g);

   free(g);
}

인접 리스트 방법 (연결 리스트 사용)

- 각 정점에 인접한 정점들을 연결리스트로 표현

- 인접리스트 총 노드(data+link) 개수 = 2|E| (무방향) or |E| (방향)

인접리스트 알고리즘

#include <stdio.h>
#include <stdlib.h>

#define MAX_VERTICES 50 //최대 50개 노드
typedef struct GraphNode
{
   int vertex; 
   struct GraphNode *link;
} GraphNode;

typedef struct GraphType
{
   int n; //정점 개수 n=|V| <= MAX_VERTICES(50)
   GraphNode* adj_list[MAX_VERTICES];
} GraphType;


//그래프 초기화
void init(GraphType* g)
{
   int v;
   g->n = 0; //정점 총 개수 0개
   for (v=0; v < MAX_VERTICES; v++)
      g->adj_list[v] = NULL; 
}


//정점 삽입 연산 
void insert_vertex(GraphType* g, int v)
{
   if (((g->n) + 1) > MAX_VERTICES) //정점개수+1 이 50보다 작으면
   {
      fprintf(stderr, "그래프: 정점의 개수 초과");
      return;
   }
   g->n++;
}


//간선 삽입 연산, v를 u의 인접 리스트에 삽입 
void insert_edge(Graphtype* g, int u, int v)
{
   GraphNode* node;
   if (u >= g->n || v >= g->n)
   {
      fprintf(stderr,"그래프: 정점 번호 오류");
      return;
   }
   node = (GraphNode*)malloc(sizeof(GraphNode));
   node->vertex = v;
   node->link = g->adj_list[u];
   g->adj_list[u] = node;
}


void print_adj_list(GraphType* g)
{
  for (int i=0; i<g->n; i++) {
    GraphNode* p = g->adj_list[i];
    printf("정점 %d의 인접 리스트 ", i);
    while (p!=NULL) {
       printf("-> %d ", p->vertex);
       p=p->link;
    }
  }
}


//main 함수 
void main() 
{
   GraphType* g;
   g = (GraphType*)malloc(sizeof(GraphType));
   init(g);
   for(int i=0; i < 4; i++) 
      insert_vertex(g,i);
   
   insert_edge(g,0,1);
   insert_edge(g,1,0);
   insert_edge(g,0,2);
   insert_edge(g,2,0);
   insert_edge(g,0,3);
   insert_edge(g,3,0);
   insert_edge(g,1,2);
   insert_edge(g,2,1);
   insert_edge(g,2,3);
   insert_edge(g,3,2);
   print_adj_list(g);

   free(g);
   return 0;
}

실행결과

정점 0의 인접 리스트 -> 3 -> 2 -> 1

정점 1의 인접 리스트 -> 2 -> 0

정점 2의 인접 리스트 -> 3 -> 1 -> 0

정점 3의 인접 리스트 -> 2 -> 0

인접 행렬 VS 인접 리스트

10.4 그래프 탐색

- 하나의 정점에서 시작하여 차례대로 모든 정점들을 한번씩 방문

그래프 탐색 알고리즘 2가지 -> DFS, BFS

10.5 깊이 우선 탐색 (DFS - depth first search)

- 한 방향(source node에서 멀어지는 방향)으로 갈 수 있을 때까지 가다가 더 이상 못가면 가장 가까운 갈림길로 돌아와서(후입선출)이 곳으로부터 다른 방향으로 다시 탐색 진행

- 두가지 방법 구현 가능 (1. 순환 호출, 2. 명시적 스택으로 저장하고 꺼내는것)

- 되돌아가기 위해서는 스택 필요 (순환함수 호출로 묵시적인 스택 이용)

depth_first_search(v): //v는 source node
1. v를 방문되었다고 표시; //필요한 연산(printf) 수행
2. for all u ∈ (v에 인접한 정점) do
3. if (u가 아직 방문되지 않았으면)
4. then depth_first_search(u) //v의 인접 행렬인 u가 다시 새로운 소스노드가 되는 것!!

**dfs-tree unique (X)

DFS 인접 행렬 버전 프로그램 ========>> O(n^2)

//인접 행렬로 표현한 그래프에 대한 깊이 우선 탐색 
void dfs_mat(GraphType* g, int v) 
{
   int w;
   visted[v] = TRUE; //정점 v 방문 표시
   printf("정점 %d -> ", v) //방문한 정점 출력
   
   for (w=0; w < g->n; w++) //인접 정점 탐색
      if (g->adj_mat[v][w] && !visited[w])
          dfs_mat(g,w); //정점 w에서 DFS 새로 시작 
}


//main 함수 
int main(void)
{
   GraphType* g;
   g = (GraphType*)malloc(sizeof(GraphType));
   init(g);
   for (int i=0; i < 4; i++)
      insert_vertex(g,i);
      
   insert_edge(g,0,1);
   insert_edge(g,0,2);
   insert_edge(g,0,3);
   insert_edge(g,1,2);
   insert_edge(g,2,3);
   
   printf("깊이 우선 탐색\n");
   dfs_mat(g,0);
   printf("\n");
   free(g);
   return 0;
}

실행결과

깊이 우선 탐색

정점 0 -> 정점 1 -> 정점 2 -> 정점 3 ->

즉,

아직 방문 안된 인접노드(v)가 있다면 push(v) 하고

아직 방문 안된 인접노드가 없다면 pop(return)

DFS 인접 리스트 버전 프로그램 ========>> O(n+e)

연결리스트의 노드는 데이터필드(인접 정점 번호 저장) + 링크 필드(다음 인접 정점 가리키는 포인터 저장)로 이루어짐

//struct 정의 추가
typedef struct GraphNode {
  int vertex; 
  struct GraphNode* link;
} GraphNode;

typedef struct GraphType {
  int n;
  GraphNode* adj_list[MAX_VERTICES]l
}GraphType;


int visited[MAX_VERTICES];


//인접 리스트로 표현한 그래프에 대한 깊이 우선 탐색 
void dfs_list(GraphType* g, int v) 
{
   GraphNode* w;
   visted[v] = TRUE; //정점 v 방문 표시
   printf("정점 %d -> ", v) //방문한 정점 출력
 
   for (w = g->adj_list[v]; w; w = w->link) //인접 정점 탐색
      if (!visited[w->vertex])
          dfs_list(g,w->vertex); //정점 w에서 DFS 새로 시작 
}

명시적인 스택을 이용한 깊이 우선탐색 구현

- 스택을 하나 생성해서 시작 정점을 스택에 넣고, 다시 꺼내서 탐색.

DFS - iterative(G, v):
1. 스택 S 생성
2. S.push(v)
3. while (not is_empty(S)) do
4. v = S.pop()
5. if (v가 방문되지 않았으면)
6. v를 방문되었다고 표시 //출력
7. for all u ∈ (v에 인접한 정점) do
8. if (u가 아직 방문되지 않았으면)
9. S.push(u)

10.6 너비 우선 탐색 (BFS - breadth first search)

- 시작 정점으로부터 가까운 정점을 (선입선출) 먼저 방문하고 멀리 떨어져 있는 정점을 나중에 방문하는 순회 방법

- 큐로 구현

breadth_first_search(v):
1. v를 방문되었다고 표시; //visted[v] = TRUE;
2. 큐 Q에 정점 v를 삽입;
3. while (Q가 공백이 아니면) do
4. Q에서 정점 w를 삭제;
5. for all u ∈ (w에 인접한 정점) do
6. if (u가 아직 방문되지 않았으면)
7. then u를 큐에 삽입;
8. u를 방문되었다고 표시;

BFS 인접 행렬 버전 프로그램 ========>> O(n^2)

//인접 행렬로 표현한 그래프에 대한 너비 우선 탐색 
void bfs_mat(GraphType* g, int v) 
{
   int w;
   QueueType q;
   
   queue_init(&q); //큐 초기화 
   visted[v] = TRUE; //정점 v 방문 표시
   printf("정점 %d -> ", v) //방문한 정점 출력
   enqueue(&q, v); //시작 정점을 큐에 저장 
   
   while (!is_empty(&q)) {
      v = dequeue(&q); //큐에 정점 추출
      for (w=0; w<g->n; w++) //인접 정점 탐색
         if (g->adj_mat[v][w] && !visited[w]) {
             visited[w] = TRUE;
             printf("%d 방문 -> ", w); 
             enqueue(&q, w); //방문한 정점을 큐에 저장 
         }
   }
}


//main 함수 
int main(void)
{
   GraphType* g;
   g = (GraphType*)malloc(sizeof(GraphType));
   graph_init(g);
   for (int i=0; i < 6; i++)
      insert_vertex(g,i);
      
   insert_edge(g,0,2);
   insert_edge(g,2,1);
   insert_edge(g,2,3);
   insert_edge(g,0,4);
   insert_edge(g,4,5);
   insert_edge(g,1,5);
   
   printf("너비 우선 탐색\n");
   bfs_mat(g,0);
   printf("\n");
   free(g);
   return 0;
}

실행결과

너비 우선 탐색

0 방문 -> 2 방문 -> 4 방문 -> 1 방문 -> 3 방문 -> 5 방문 ->

BFS 인접 리스트 버전 프로그램 ========>> O(n+e)

//struct 정의 추가
typedef struct GraphNode {
  int vertex; 
  struct GraphNode* link;
} GraphNode;

typedef struct GraphType {
  int n; //|V|
  GraphNode* adj_list[MAX_VERTICES]
}GraphType;


//인접 리스트로 표현한 그래프에 대한 너비 우선 탐색 
void bfs_list(GraphType* g, int v) 
{
   GraphNode* w;
   Queuetype q;
   
   init(&q); //큐 초기화
   visted[v] = TRUE; //정점 v 방문 표시
   printf("%d 방문 -> ", v) //방문한 정점 출력
   enqueue(&q, v); //시작정점을 큐에 저장
   while (!is_empty(&q)) {
     v = dequeue(&q); //큐에 저장된 정점 선택
     for (w=g->adj_list[v]; w; w=w->link) //인접 정점 탐색
        if (!visited[w->vertex]) { //미방문 정점 탐색 
            visited[w->vertex] = TRUE; //방문 표시
            printf("%d 방문 -> ", w->vertex); 
            enqueue(&q, w->vertex); //정점을 큐에 삽입 
        }
  }
}

'Study > Data Structure' 카테고리의 다른 글

자료구조 전체 (0)	2023.12.08
[자료구조 스터디] chap.13 탐색 (0)	2023.12.01
[자료구조 스터디] chap.12 정렬 (0)	2023.11.21
[자료구조 스터디] chap.11 그래프 II (0)	2023.11.16

Coding Diary

[자료구조 스터디] chap.10 그래프 I

10.1 그래프란?

그래프(graph)

오일러 정리

10.2 그래프의 정의와 용어

그래프 정의

그래프 종류

그래프의 경로(path)

그래프의 연결 정도

그래프 표현 방법 2가지

인접행렬 알고리즘

인접리스트 알고리즘

10.4 그래프 탐색

10.5 깊이 우선 탐색 (DFS - depth first search)

DFS 인접 행렬 버전 프로그램 ========>> O(n^2)

DFS 인접 리스트 버전 프로그램 ========>> O(n+e)

10.6 너비 우선 탐색 (BFS - breadth first search)

BFS 인접 행렬 버전 프로그램 ========>> O(n^2)

BFS 인접 리스트 버전 프로그램 ========>> O(n+e)

'Study > Data Structure' 카테고리의 다른 글

티스토리툴바

[자료구조 스터디] chap.10 그래프 I

10.1 그래프란?

그래프(graph)

오일러 정리

10.2 그래프의 정의와 용어

그래프 정의

그래프 종류

그래프의 경로(path)

그래프의 연결 정도

그래프 표현 방법 2가지

인접행렬 알고리즘

인접리스트 알고리즘

10.4 그래프 탐색

10.5 깊이 우선 탐색 (DFS - depth first search)

DFS 인접 행렬 버전 프로그램 ========>> O(n^2)

DFS 인접 리스트 버전 프로그램 ========>> O(n+e)

10.6 너비 우선 탐색 (BFS - breadth first search)

BFS 인접 행렬 버전 프로그램 ========>> O(n^2)

BFS 인접 리스트 버전 프로그램 ========>> O(n+e)

'Study > Data Structure' 카테고리의 다른 글

'Study/Data Structure' Related Articles

티스토리툴바