꼭짓점(Vertex)와 간선(Edge)을 이용한 비선형 데이터 구조

• 방향이 있는 간선을 포함하면 방향 그래프(Directed Graph) : <A, B>
• 방향이 없는 간선을 포함하면 무방향 그래프(Undirected Graph) : (A, B)

• 어떤 데이터는 흐름의 방향뿐 아니라 양도 중요할 수 있고 그런 정도를 간선에 표현할 때 이를 가중치라고 한다.
• 가중치가 있는 그래프를 가중치 그래프(Weighted Graph)라고 한다.
• 순환은 특정 꼭짓점에서 시작해 간선을 따라 다시 돌아오는 경로가 있는 것을 말한다.
• 순환이 존재하는 그래프를 순환 그래프(Cycle Graph)라고 한다.
• 순환이 존재하지 않는 그래프를 비순환 그래프(Acyclic Graph)라고 한다.

그래프의 표현 : 배열

• 인접 행렬 (adjacent matrix)
  • 간선 (i, j) 가 존재하면 M[i][j] = 1 그 외에는 M[i][j] = 0
  • 무방향 그래프의 인접 행렬은 대각선이 0이고 대칭이다

그래프의 표현 : 인접 리스트

• 정점에서 인접한 정점들을 연결리스트로 표시

탐색

깊이 우선 탐색 (DFS)

• 깊이 우선 탐색은 스택을 활용하여 구현한다.
• 시작 꼭짓점부터 탐색을 시작하여 간선을 따라 최대한 깊은 꼭짓점까지 이동하며 차례대로 방문하는 방식의 알고리즘이다.
• 한 방향으로 계속 진행하다가 더 이상 진행이 불가능할 때 최근 갈림길로 돌아와 다른 방향으로 탐색 진행

depth_first_search(v)
	v를 방문되었다고 표시;
	for all u ∈ (v에 인접한 정점) do 
		if (u가 아직 방문되지 않았으면)then depth_first_search(u)

너비 우선 탐색 (BFS)

• 너비 우선 탐색은 큐를 활용하여 구현한다.
• 시작 꼭짓점과 거리가 가장 가까운 꼭짓점을 우선하여 차례대로 방문하는 방식의 알고리즘이다.
• 시작점에서 가까운 정점을 먼저 방문하고, 멀리 있는 정점을 나중에 방문

breadth_first_search(v)
v를 방문되었다고 표시;
큐 Q에 정점 v를 삽입;
while (not is_empty(Q)) do 
	큐 Q에서 정점 w를 삭제;
	for all u ∈ (w에 인접한 정점) do 
			if (u가 아직 방문되지 않았으면) then //u를 큐 Q에 삽입;
																				 //u를 방문되었다고 표시;