그래프2 그래프 탐색 -BFS, DFS 그래프 탐색 (그래프 순회) 하나의 시작점 노드에서 연결된 노드들을 모두 찾는 것 BFS 너비 우선 탐색 시작 노드를 방문 표시 후 큐에 넣음 큐에 아무노드가 없을때까지: 큐 가장 앞 노드를 꺼낸다. 꺼낸노드에 인접한 노드들을 모두 보면서: 처음 방문한 노드면: 방문한 노드 표시를 해준다 큐에 넣어준다. BFS 알고리즘 시간 복잡도 BFS 노드 전처리 → O(V) 큐에 노드를 넣고 빼는데 걸리는 시간 → O(V) 큐에서뺀 노드의 인접한 노드들을 도는데 걸리는 시간 →O(E) ⇒총 O(2V+E) ⇒ O(V+E) DFS 깊이 우선 탐색 시작 노드를 옅은 회색 표시후, 스택에 넣음 스택에 아무 노드가 없을때까지 : 스택 가장 위노드를 꺼낸다. 노드를 방문 표시를 한다. 인접한 노드들을 모두 보면서: 처음 방문.. 2024. 1. 23. 그래프 연결 데이터를 저장 할 수 있는 자료구조 세상에는 다양한 연결 관계가 존재하기 때문에 그래프 자료구조는 이를 저장하기 유용하다. 그래프 용어 정리 노드 : 그래프에서 하나의 데이터 단위를 나타내는 객체 엣지: 그래프에서 두노드의 직접적인 연결 관계 데이터 엣지가 방향을 가지면 → 방향그래프 엣지가 어떤 정보를 나타내는 수치를 가지면 → 가중치그래프 차수 : 하나의 노드에 연결된 엣지들의 수 무방향 그래프 → 하나의 노드에 연결된 엣지들의 수를 나타낸다. 방향 그래프 → 노드를 떠나는 엣지의 수를 출력 차수 노드에 들어오는 엣지의수를 입력 차수로 부른다. 경로 : 한 노드에서 다른 노드까지 가는길 경로의 거리 비가중치 그래프 → 엣지의 수 가중치 그래프 → 엣지의 가중치 합 최단 경로 : 두노드 사이의 경.. 2024. 1. 22. 이전 1 다음
