Graph

[자료구조] 그래프(Graph)

그래프?그래프는 정점(Vertext)의 집합과 간선(Edge)의 집합으로 이루어진 자료구조정점의 집합을 V, 간선의 집합을 E, 그래프를 G 라고 했을 때 G = (V,E)이다정점은 위치를 의미, 간선은 정점과 정점을 연결하는 선을 의미그래프 트리 그래프트리방향성방향 그래프 or 무방향 그래프방향 그래프순환성순환 및 비순환비순환루트 노드 존재 여부루트 노드가 없음루트 노드가 존재노드간 관계성부모와 자식 관계 없음부모와 자식 관계모델의 종류네트워크 모델계층 모델그래프 용어 그래프에만 쓰이는 몇 가지 기술 용어가 있다각 노드를 정점(Vertext)정점을 잇는 선도 그래프 용어로 간선이라 부른다간선으로 연결된 정점은 서로 인접하다(Adjacent)인접한 정점을 이웃 = neighbor모든 정점이 서로 연결된 ..

[자료구조] BFS(Breadth-First Search)

그래프 탐색 하나의 정점으로부터 시작하여 차례대로 모든 정점들을 한 번씩 방문하는 것. 그래프는 관계에 특화된 자료 구조로서 데이터가 서로 어떻게 연결되는지 쉽게 이해시켜 준다. SNS 예시로는 한 사람은 한 노드로, 사람 간 친구 관계는 선으로 표현한다. → 방금 가입해 친구가 0명인 회원이 있다면 노드는 존재하지만 연결된 친구가 한 명도 없는 상태이다. 기초 그래프 구현 const friends = new Map([ ["Alice", ["Bob", "Diana", "Fred"]], ["Bob", ["Alice", "Cynthia", "Diana"]], ["Cynthia", ["Bob"]], ["Diana", ["Alice", "Bob", "Fred"]], ["Elise", ["Fred"]], ["Fr..