# [C언어로 쉽게 풀어쓴 자료구조(천인국)]를 공부하고 주요 내용을 정리하고자 작성하는 글입니다. # 해당 게시글에 대한 모든 피드백 환영합니다. 신장트리 Spanning Tree 그래프 내의 모든 정점을 포함하는 트리 단, 아래의 3가지 조건을 모두 만족해야 한다. 모든 정점들이 연결되어 있어야 한다. 사이클 cycle 을 포함하면 안된다. 그래프에 있는 n개의 정점을 정확히 (n-1)개의 간선으로 연결한다. 신장트리는 깊이우선 탐색 또는 너비우선 탐색을 하면서 사용된 간선만 모으면 만들 수 있다. 즉, 신장트리는 그래프의 최소 연결 부분 그래프가 된다. 이러한 신장트리는 통신망 네트워크 구축 등에 사용된다. 통신망, 도로망, 유통망 등은 간선에 가중치가 부여된 네트워크이다. 이를 가장 적은 비용으로..

# [C언어로 쉽게 풀어쓴 자료구조(천인국)]를 공부하고 주요 내용을 정리하고자 작성하는 글입니다. # 해당 게시글에 대한 모든 피드백 환영합니다. 너비우선탐색 Breath First Search : BFS 시작 정점으로부터 가장 가까운 정점을 먼저 방문하고 차차 멀리 떨어져있는 정점을 방문한다. 다시 말해서, 가까운 거리에 있는 정점들을 차례로 저장한 후 넣은 순서대로 꺼내서 방문하는 방식이다. 이를 위해서, 자료구조 Queue 큐를 사용한다. #알고리즘 breath_first_search(v): v를 방문했다고 표시 큐 Queue에 정점 v를 삽입 while (Queue가 공백이 아니면) do w front = q->rear = 0; } // 공백 상태 검출 함수 int is_empty(QueueTy..

# [C언어로 쉽게 풀어쓴 자료구조(천인국)]를 공부하고 주요 내용을 정리하고자 작성하는 글입니다. # 해당 게시글에 대한 모든 피드백 환영합니다. 깊이우선 탐색 Depth First Search: DFS 시작 정점에서 한 방향으로 직진하다가 더 이상 갈 수 없게 되면 다시 가장 가까운 갈림길로 돌아와서 다른 방향으로 다시 탐색을 진행하는 것 0. 알고리즘 그래프의 시작 정점에서 출발 ==> 시작정점 = v 정점 v 방문했다고 표시 정점 v의 인접정점 집합에 대해서 ( u ∈ 인접정점 집합 ) 정점 u를 아직 방문안했으면 시작정점을 u로 설정해서 위의 과정 다시 수행 만약 인접정점 집합이 공집합이면 리턴 depth_first_search(v): v를 방문했다고 표시 for all u in (v의 인접정점..

# [C언어로 쉽게 풀어쓴 자료구조(천인국)]를 공부하고 주요 내용을 정리하고자 작성하는 글입니다. # 해당 게시글에 대한 모든 피드백 환영합니다. 1. 인접행렬 adjacency matrix # 개념, 특징 1) 2차원 배열 사용 2) 자체 간선 허용 X ==> 대각선 성분 = 0 3) 정점 i, j 에 대해 간선 (i,j) or 가 존재하면 - 무방향 그래프: Matrix[i][j] = Matrix[j][i] = 1 - 방향 그래프: Matrix[i][j] = 1 4) 2차원 배열은 - 무방향 그래프: 대칭 행렬 ==> 배열의 상위 삼각/하위 삼각만 저장하면 메모리 절약 가능 - 방향 그래프: 비대칭 행렬 5) 정점의 개수 = n 인 경우 간선의 개수와 무관, n*n개의 메모리 공간이 필요함 ==> ..

# [C언어로 쉽게 풀어쓴 자료구조(천인국)]를 공부하고 주요 내용을 정리하고자 작성하는 글입니다. # 해당 게시글에 대한 모든 피드백 환영합니다. 1. 그래프의 정의 : 객체 사이의 연결 관계를 표현하는 자료구조 ex. 지하철 노선도, 전기회로, 운영체제 프로세스와 자원 그래프, 트리 2. 그래프의 구조 그래프(G; graph) = 정점(V; vertex) + 간선(E; edge) G = (V,E) - V(G): 그래프 G의 정점들의 집합 - E(G): 그래프 G의 간선들의 집합 - 정점 = vertex = node - 간선 = edge = link 3. 그래프의 종류 1) 무방향 그래프 undirected graph - 간선을 통해서 양쪽 방향으로 갈 수 있음. - 정점 A,B 연결하는 간선 ==> ..