그래프

표현

1. 인접 리스트

 

점개수만큼 길이의 배열잇음

(배열의 인덱스 = 정점)

이 배열의 각 요소는 각 해당 정점의 연결리스트를 담고잇음

연결리스트 = 그 정점의 인접한 정점의 집합

 

예를들어 정점1이 2,3과 연결되어잇으면

배열의 인덱스1의 요소로는 [2,3]이 있는거

 

(각 정점이 연결된 점의리스트를 배열로담고있다. 이때 인덱스가 해당 정점이다)

 

 

모든 노드 탐색하기 ! 

1. 너비 우선 탐색 BFS <- 큐 기반

출발점 -> 출발점과 인접한 정점들 모두 방문 -> 그 정점과 인접한 정점 모두 방문

큐에 넣엇다가 하나씩 빼서쓰는 형식으로 !!

 

2. 깊이 우선 탐색 DFS <-스택 기반

: 시작 정점에서 한 방향을 정하고 그 방향으로 쭉 따라나감 -> 갈곳 없어지면 하나 전 정점으로해서 쭉 감!

시작 정점으로 돌아온 후 더이상 갈 곳 없어야만 실행 종료됨

 

1 ) 재귀함수 -> 스택프레임 쌓이는 걸 이용하기

함수가 하나씩 불린다 = 스텍 프레임이 쌓인다

마지막 함수가 처리된다 -> 스텍 프레임에서 사라진 후 다음 스택에 잇는애가 실행된다

(for문이 있는데 그 안에서 다른 함수를 호출하면, 당연히 다른함수 호출먼저하고 그거 다 처리한 뒤에 다음 for문을 돌린다)

 

2 ) 스택 자료구조로 구현하기 !

stack에는 내가 검사할 애들을 하나로 차례씩 넣는다

 

그 스택의 peek에 있는 친구의 인접을 구한다-이게 한번도 방문되지 않았던애면 탐색 성공! break 포문  -> 그친구를 스택에 추가한다

그리고 다시 스택의 peek(그친구)의 인접을 구한다- 방문X친구 방문하면 탐색성공! break 후 -> 그 새친구를 스택에 추가한다

이렇게 계속 쭉쭉가다가

peek친구가 더이상 인접에 방문x엿던 새친구가 없음 ! -> 그친구 pop해버림

그리고 그 전친구, 이제는 peek인 걔가 계속 탐색 -> 없으면 pop해버림

 

이과정을 stack에 이제 아무것도 안남을 때까지 한다 (시작 정점이 당연히 마지막으로 진행된다 ! )

 

= 검사 더할 친구를 스택에 하나씩 쌓아두고, 끝까지 간 후 하나씩 돌아가면서 더 검사한다