목록BFS (1)
로빈의 개발로그
내멋대로 자료구조 - 그래프, DFS, BFS
1. 그래프란? - 자료구조 중 연결되어 있는 정점(Vertex, Node)과 정점간의 관계(Edge)를 표현할 수 있는 자료구조 - 그래프는 유방향(Directed)과 무방향(Undirected)로 이루어진다 2. 그래프를 표현하는 방법 - 인접 행렬 (Adjacency Matrix) : 2차원 배열로 그래프의 연결 관계를 표현 GOOD : 연결여부를 바로 알 수 있다. BAD : 모든 조합의 연결여부를 저장해야 하기 때문에 O(n^2) - 인접 리스트(Adjacency List): 링크드 리스트로 그래프의 연결 관계를 표현 GOOD : 모든 조합의 연결여부를 저장할 필요 X. O(노드+간선)만큼의 공간 사용 BAD : 각 리스트를 돌아야 연결되었는지 여부가 정확하게 알 수 있음 3. DFS (Dept..
자료구조 & 알고리즘
2022. 1. 30. 23:43