그래프란 정점과 간선으로 이루어진 자료구조이다.
트리는 그래프의 일종이며 다음과 같은 특징이 있다.
- 단방향 그래프 2. 사이클이 없음 3. 부모자식 관계의 그래프임
이진트리 - 부모가 2명의 자식만 갖는 트리
이진트리는 1차원배열로 구현가능함
방법 )
1. 루트노드를 1번 인덱스로 저장
2. 왼쪽 자식 노드를 부모인덱스 2 , 오른쪽 자식 노드 부모인덱스 2 + 1로 처리
트리는 인접행렬이나 인접리스트로 구현 가능하다.
트리가 아닌 모양은 양방향이 될 수도 있다.
이러한 그래프를 탐색하기 위한 알고리즘이 DFS, BFS 알고리즘이다.
DFS -깊이우선탐색
- 최대한 깊이 탐색하고 더 이상 갈곳이 없으면 이전으로 돌아가 탐색
BFS -너비우선탐색 - 시장 정점 인근의 정점을 우선적으로 방문
DFS -
그래프는 트리와 달리 사이클이 존재할 수 있다 - 무한으로 계속 도는
그래서 한번 탐색한 곳은 들리지 않도록 설정해야한다.
그렇게 하기 위해서는 used배열을 만들어 첫번째 노드를 넣고 시작한다.
- 시작노드에서 연결된 노드가 있는지 찾는다.
- 다음 노드를 방문한 적이 있는지 확인한다.
- 방문한 적이 없으면 배열에 넣고 재귀호출을 한다.
================================================================
트리가 아닌 노드 dfs
#include
#include
using namespace std;
char name[5] = "BATK";
int map[4][4] = {
0,0,1,1,
1,0,1,0,
1,0,1,1,
0,0,0,0
};
int used[4]; //싸이클 방지하기 위해 used배열을 사용함
void dfs(int now)
{
cout << name[now] << " ";
for (int x = 0; x < 4; x++)
{
if (map[now][x] == 1)
{
if (used[x] == 1)continue;
used[x] = 1;
dfs(x);
}
}
}
int main()
{
used[1] = 1;
dfs(1); // 첫번째 0은 dfs시작 인덱스 , 두번째 0은 level노드
return 0;}
==================================================================
노드 level 2에서 트리 누적합 구하기
#include
#include
using namespace std;
int num[7] = { 4,7,9,1,3,6,8 };
int map[7][7] = {
0,1,1,0,0,0,0,
0,0,0,1,1,0,0,
0,0,0,0,0,1,1,
0,0,0,0,0,0,0,
0,0,0,0,0,0,0,
0,0,0,0,0,0,0,
0,0,0,0,0,0,0,
};
void dfs(int now, int level, int sum)
{
//cout << num[now] << " ";
if (level == 2)
{
cout << sum << " ";
}
for (int x = 0; x < 7; x++)
{
if (map[now][x] == 1)
{
dfs(x,level+1, sum+num[x]); //num배열중 내가 앞으로 들어갈 인덱스 (변수 x_)
}
}
}
int main()
{
dfs(0,0,4); // 첫번째 0은 dfs시작 인덱스 , 두번째 0은 level노드 세번째는 sum값
return 0;}
