표현
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에 이제 아무것도 안남을 때까지 한다 (시작 정점이 당연히 마지막으로 진행된다 ! )
= 검사 더할 친구를 스택에 하나씩 쌓아두고, 끝까지 간 후 하나씩 돌아가면서 더 검사한다