목록그래프 (1)

RB의 iOS 개발 이야기

그래프(Graph), 트리(Tree), BFS/DFS 정리

오늘은 자료구와 알고리즘에서 자주 빈출되는 그래프, 트리, BFS, DFS에 관하여 간단하게 정리해보려고 합니다! 그래프 그래프란? 노드와 간선으로 구성된 자료구조로 이를 통해 연결된 노드간의 관계를 표현할 수 있다. 노드(node)란 정점(vertex)라고도 하며 그래프를 구성하는 기본 원소 (점) 간선(edge)이란 정점간의 관계로 노드를 연결하는 선 인접행렬 노드와 노드가 연결되어 있는지 나타내는 정사각행렬(이차원 배열) 장점: 구현이 쉽고 직관적이다. i와 j 노드의 연결상태를 바로 알 수 있다. 단점: 노드의 개수가 N이라고 하면 이 배열의 크기는 N*N이 된다. 특정 노드에 연결된 노드를 찾으려면 N번 만큼 확인해줘야한다. 인접리스트 노드별로 연결된 노드를 기록 장점: 실제로 연결된 노드의 정..
iOS/Swift 2023. 10. 13. 11:35
이전 Prev 1 Next 다음