알고리즘 그래프(Graph)

소개글

알고리즘 그래프(Graph)에 대한 보고서 자료입니다.

목차

1. 그래프의 정의와 종류
(1) 그래프란?
(2) 그래프의 용어
(3) 그래프의 종류
2. 그래프의 표현
(1) 인접 행렬(Adjacency Matrix)
(2) 인접 리스트(Adjacency List)
3. 그래프의 운행
(1) 깊이우선 검색방식(DFS:Depth First Search)
(2) 너비우선 검색방식(BFS:Breadth First Search)

본문내용

t_mark[w]==0)
dfs(v, visit_mark, t);
}
(2) 너비우선 검색방식(BFS:Breadth First Search)
너비우선 검색방식의 원리
- 시작 정점을 선정
- 해당 점점과 연결된 정점 모드를 방문
- 선택되지 않은 인접한 정점을 계속 방문
- 모든 정점을 방문하면 종료
* 큐의 자료구조가 이용 됨
너비우선 검색방식의 구현
① 선택된 정점에 visit mark
② 이동전에 연결된 다른 정점을 알아보고, visit mark 없는 정점을 큐에 넣음
③ 이동한 후 visit mark
④ 큐에서 하나씩 꺼내서 새롭게 선택을 함
⑤ 큐가 빌 때까지 ②~⑤의 과정을 반복
int visit_mark[N];
void bfs(int v){
int w;
visit_mark[v] = TRUE;
add_queue(v);
while(큐가 비어 있지 않음){ //큐에 노드 유무에 따름
v=delete_queue() //큐의 노드 하나 빼옴
printf("%d\n", v);
while(v에 인접한 모든 노드를 검사 검사당한 노드는 w)
if(!visit_mark[w]){
add_queue(w);
visit_mark[v] = TRUE;
}
}
}
}

키워드

알고리즘,   그래프,   graph