본문 바로가기

전체 글

 (55)
9-1. 그래프 (Graph) - 깊이 우선 탐색 (Depth First Search, DFS) void Graph::DFS(){ // Driver visited = new bool[n]; for (int i=0; i
깊이 우선 탐색 (Depth First Search, DFS) 깊이 우선 탐색 (DFS) - 연결 graph, 무방향 graph - stack 사용 단계 ① 출발 정점 v 방문 ② v에 인접하고 방문하지 않은 한 정점 w 선택 ③ w를 시작점으로 다시 깊이 우선 탐색 ④ 모든 인접 정점을 방문한 정점 u에 도달시, u를 방문하기 위해 사용된 간선 (w, u) 상의 정점 w로 되돌아감 ⑤ 정점 w로부터 다시 깊이 우선 탐색 ⑥ 방문 안된 정점으로 더 이상 갈 수 없을 때 종료 ex) 0 – 1 – 3 – 7 – 4 – 5 – 2 – 6 순으로 방문 분석 ① 인접 리스트 사용 리스트 node 수 2e개 만큼 조사 → O(e) 소요 ② 인접 행렬 사용 한 정점에 인접한 정점들 조사하는데에 O(n) 소요 ∴ 전체 원소 조사 → O($n^2$) 소요
9. 그래프 (Graph) 인접 리스트로 구현 - class 선언 typedef ChainNode* ChainNodePointer; class Graph { private: ChainNodePointer *HeadNodes;// first들의 배열 선언 int n;// 정점 수 bool* visited;// 방문 여부 public: Graph (const int vertices = 0) : n(vertices) { HeadNodes = new ChainNodePointer[n]; }; } 연결 요소 인접 리스트 : 모든 node 1번씩 방문, O(e) + for 반복문, O(n) = O(n+e) 소요 인접 행렬 : O($n^2$) 소요 void Graph::Components(){ // graph의 연결 요소들 결정 visited..
그래프 (Graph) 정의 G=(V, E) [ V = 공집합이 아닌 정점(vertex)들의 유한집합 ] [ E = 정점들의 쌍인 간선(edge)들의 집합 ] 무방향 그래프 (Undirected Graph) 방향 그래프 (Directed Graph) V(G1) = {0, 1, 2, 3} E(G1) = {(0,1), (0,2), (0,3), (1,2), (1,3), 2,3)} V(G3) = {0, 1, 2} E(G3) = {, , } = E(G)의 간선 (u, v)에 대해 u와 v는 인접한다(adjacent)라고 하며 간선 (u, v)는 정점 u와 v에 부속된다(incident)고 한다. 완전 그래프 (Complete Graph) n개의 정점을 갖는 무방향 그래프 간선 최대수 = n(n-1)/2 부분 그래프 (Sub Graph)..
8. 이진 탐색 트리 (Binary Search Tree, BST) dyeoma.tistory.com/20 이진 탐색 트리 (Binary Search Tree) 정의 모든 원소는 키를 가지며 동일한 키가 없음 왼쪽 sub tree에 있는 key 값 LeftChild; else if(x.key > t->data.key) t = t->rightChild; else return t..
이진 탐색 트리 (Binary Search Tree, BST) 정의 모든 원소는 키를 가지며 동일한 키가 없음 왼쪽 sub tree에 있는 key 값 root : 오른쪽 sub tree 탐색 key == root : 탐색 완료 BST 삽입 동일한 key값 가진 원소 있는지 확인 후, 없으면 그 지점에 삽입 BST 삭제 leaf node 삭제 1개 child 갖는 non-terminal node 삭제 2개 child ..
7. 최대 히프 (Max Heap) dyeoma.tistory.com/18 최대 히프 우선 순위 Queue 삽입은 일반적인 queue와 같으나, 삭제는 우선 순위가 가장 높은 것이 먼저 삭제 최대(최소) Heap는 최대(최소) 우선 순위 Queue를 구현하는데 사용 Heap 완전이진트리 → 1차원 배열 사 dyeoma.tistory.com 최대 히프 class class MaxHeap { ... private: Element *heap; int n;// 히프 현재 크기 int MaxSize;// 히프 최대 크기 } 최대 히프 생성자 MaxHeap::MaxHeap (int size=DefaultSize){ MaxSize = size; n=0; heap = new Element[MaxSize + 1];// heap[0]은 미사용 } 최대 히프..
최대 히프 우선 순위 Queue 삽입은 일반적인 queue와 같으나, 삭제는 우선 순위가 가장 높은 것이 먼저 삭제 최대(최소) Heap는 최대(최소) 우선 순위 Queue를 구현하는데 사용 Heap 완전이진트리 → 1차원 배열 사용 기본 연산 : 공백 Heap 생성, 원소 삽입, 원소 삭제 최대히프 삽입 삽입 전 삽입 위치 5 삽입 21 삽입 최대히프 삭제 root 21 삭제 삭제 후 조정 후

티스토리툴바