1) 깊이 우선 탐색(Depth First Search)
- 탐색을 함에 있어서 보다 깊은 것을 우선적으로 하여 탐색하는 알고리즘
- 깊이 우선 탐색은 기본적으로 전체 노드를 맹목적으로 탐색하고자 할 때 사용한다.
- 스택(Stack) 자료구조에 기초한다.
- 모든 경우의 수를 탐색하고자 할 때 쉽게 사용할 수 있다.
- 시간복잡도 : O(N) -> 정점의 갯수만큼 반복하기 때문에
탐색방법)
- 1. 탐색 시작 노드를 스택에 삽입하고 방문처리를 한다.
- 2. 스택의 최상단 노드에게 방문하지 않은 인접 노드가 하나라도 있으면 그 노드를 스택에 넣고 방문처리를 한다. 방문하지 않은 인접 노드가 없으면 스택에서 최상단 노드를 꺼낸다.
- 3. 2번의 과정을 더 이상 수행할 수 없을 때까지 반복한다.
#define _CRT_SECURE_NO_WARNINGS
#include <studio.h>
#include <studio.h>
#define MAX_SIZE 1001
typedef struct{
int index;
struct Nodee *node
} Node;
Node** a;
int n, m, c[MAX_SIZE];
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++){
int x, y;
scanf("%d %d", &x, &y);
addFront(a[x], y);
addFront(a[y], x);
}
dfs(1);
system("pause");
return 0;
}
레알 무슨소린지 모르겠다 하하
'컴퓨터 기본 개념' 카테고리의 다른 글
| 14장. 다차원 배열과 포인터 배열 (0) | 2020.07.29 |
|---|---|
| 15강. 동적메모리할당 (0) | 2020.07.28 |
| 35강. 깊이 우선 탐색 (0) | 2020.07.28 |
| 자료구조와 알고리즘 - 그래프 개념과 구현 (0) | 2020.07.27 |
| 33강. 탐색-순차 탐색과 이진 탐색 (0) | 2020.07.27 |
| 13강. 컴퓨터가 변수를 처리하는 방법 (0) | 2020.07.27 |
