그래프 그래프는 점(객체) 와 간선(관계) 으로 이루어진 존재다. 정점(Vertex) = 동그라미, 객체 하나하나. 간선(Edge) = 선, 두 객체 사이의 관계 정점 V = {A, B, C, D, E} (5개) 간선 E = {A-B, A-C, B-D, C-D, D-E} (5개) 수학에서는 이 둘을 묶어 G = (V, E) 라고 쓴다. 그래프의 구성요소 그래프는 세 가지 축 으로 나뉜다. 무방향: 선이 양방향 (친구, 양방향 도로) 방향: 선에 화살표 (팔로우, 일방통행) 가중치: 선에 값 (거리, 시간 비용) 세 축은 서로 조합된다. 무방향 + 비가중치 : 가장 단순한 그물망 : DFS · BFS 의 기본 무대 방향 + 가중치 : 비용이 붙은 지도 : 다익스트라 의 무대 컴퓨터가 보는 세계 인간: 점과 선이 한눈에, "A랑 B가 이어져 있네" 컴퓨터: '그림'이란 게 없음. 저장할 수 있는 건 숫자와 목록 뿐. 따라서 그림속 "무엇이 무엇과 연결됐는가" 를 숫자 데이터로 옮겨 적어야 한다. ★ 이 데이터가 답해야 할 질문 질문1) "둘이 연결됐는가?" - A와 B는 친구인가? - 이 역에서 저 역으로 바로 가나? 질문2) "이웃은 누구인가?" - A의 친구를 전부 알려달라. - 이 역에서 갈 수 있는 다음 역들은? ※ 앞으로 배울 모든 탐색·길찾기가 이 두 질문을 수없이 반복 한다. ★ 질문에 대답하기 위한 전략 전략1) 모든 쌍의 체크표를 만든다. 점이 N개 면 N×N 칸 의 표. 이 표의 이름이 인접 행렬(Adjacency Matrix) 이다. 학급의 "짝꿍 여부 체크표" 처럼, 가능한 모든 (점, 점) 쌍 에 대해 "선이 있으면 1, 없으면 0"을 적어둔다. 세 간선의 인접부분을 모두 표에 적으면 대칭이 보인다. 단점: 표의 대부분이 0 이다. : 점이 10만개면 100억 칸, 그마저 대부분 0임. ...