BFS - 너비 우선 탐색 - 원형큐로 구현 - 인접 행렬 : O(n²) (정점 n개) - 인접 리스트 : O(n+e) (정점 n개, 간선 e개) 시작 정점으로부터 거리가 d인 정점들을 모두 방문 (d=1) 그 다음에 거리가 d+1인 정점들을 모두 방문 d+2 / d+3,.... 정점들을 차례대로 방문 거리가 0인 시작 정점(v)을 방문 v로부터 거리가 1인 정점 모두 방문 v로부터 거리가 2인 정점 모두 방문 마지막 정점 방문할 때 까지.,.... 인접 행렬로 구현한 BFS Queue : bfs_mat_queue(graph* g, int v) 큐 생성 v 방문완료 표시 v를 큐에 enqueue 큐에서 dequeue (정점 v dequeue) -- (1) dequeue된 정점 v의 인접 정점(w)들을 방..

연결리스트 큐 - front : 삭제(delete) - rear : 삽입(insert) - rear의 link 필드는 NULL로 설정해야 한다 - 초기 상태 : front == rear == NULL - 공백 상태 : front == NULL [코드 - C] #include #include // 연결리스트를 이용한 큐 typedef int element; typedef struct qnode { element data; struct qnode* link; }qnode; qnode* front = NULL; // 큐의 front(삭제와 관련) qnode* rear = NULL; // 큐의 rear(삽입과 관련) int is_empty() { return front == NULL; // 공백 상태이면 fro..

선형큐 문제점 가득 차지 않았지만, rear가 마지막 인덱스를 가리키고 있을 경우 -> euqueue하기 위한 공간을 마련해야 하기 때문에 전체 데이터를 이동 -> 비효율적인 작업 발생 -> 해결 : 원형큐 원형큐 (Circular Queue) - 배열의 끝 (MAX_QUEUE_SIZE -1)에 도달하면 다음 증가되는 값 = 0 - 초기화 상태 : front = rear = 0 - front : 항상 큐의 첫 번째 요소에서 하나 전 - rear : 마지막 item의 인덱스 공백 상태/포화 상태를 구분하기 위해 항상 1칸은 비워둔다 공백 상태 : front == rear 포화 상태 : front가 rear보다 하나 다음 ※ Example (enqueue / dequeue 반복을 통한 인덱스 변화) - MA..

큐 (Queue) - FIFO(First in - First out) 선입 선출 구조 - 전단(front) : 삭제가 일어나는 곳 - 후단(rear) : 삽입이 일어나는 곳 큐 ADT (추상 자료형) - 0개 이상의 요소들로 구성된 선형 리스트 void init_queue(queue *q) 큐 초기화 int is_full(queue *q) 포화 상태 검출 함수 int is_empty(queue *q) 공백 상태 검출 함수 void enqueue(queue *q, element item) 큐의 후단(rear)에 item 삽입 element dequeue(queue *q) 큐의 전단(front)에서 item 리턴 후 삭제 element peek(queue *q) 큐의 전단(front)에서 item 선택 선형..