그래프 - 깊이 우선 탐색(dfs)

그래프 - 깊이 우선 탐색​

- 깊은 것을 우선적으로 탐색하는 알고리즘
- 전체 노드를 맹목적으로 탐색하고자 할 때 사용
- 스택 자료구조에 기초해 구현이 간단
- 재귀함수로 구현할 경우 O(N)
- 빠르게 모든 경우의 수를 탐색하고자 할 때 굿

 

​

알고리즘

1. 탐색 시작 노드를 스택에 삽입하고 방문 처리
2. 스택의 최상단 노드에 방문하지 않은 인접 노드가 있으면 그 노드를 스택에 넣고 방문 처리
3. 방문하지 않은 인접 노드가 없으면 스택에서 최상단 노드를 꺼냄
4. 2~3번을 더이상 수행할 수 없을 때까지 반복

​

#include <stdio.h>
#include <stdlib.h>
#define MAX_SIZE 1001
​
typedef struct Node {
  int index;
  struct Node *next;
} Node;
​
Node **a;
int n, m, c[MAX_SIZE];
// n : 정점
// m : 간선
// c :  방문 여부 체크 변수
​
void addFront(Node *root, int index)
{
  Node *node = (Node *)malloc(sizeof(Node));
  node->index = index;
  node->next = root->next;
  root->next = node;
}
​
void dfs(int x)
{
  if (c[x])
        return ; // 해당 노드 방문했으면 리턴
  c[x] = 1;
  printf("%d ", x);
  Node *cur = a[x]->next;
  while (cur != NULL)
  {
    int next = cur->index;
    dfs(next);
    cur = cur->next;
  }
}
​
int    main(void)
{
  scanf("%d %d", &n, &m);
  a = (Node**)malloc(sizeof(Node*) * (MAX_SIZE));
  for (int i = 1; i <= n; i++)
  {
      a[i] = (Node*)malloc(sizeof(Node));
      a[i]->next = NULL;
  }
  for (int i = 0 ; i < m ; i++)
  {
    int x, y;
    scanf("%d %d", &x, &y);
    addFront(a[x], y);
    addFront(a[y], x); //서로 연결
  }
  dfs(1);
}

​

:exclamation: 방문 순서가 명시되지 않음