cs 전공지식 #03 비선형자료구조 -그래프

2022/11/13

• 학습내용

 

비선형 자료 구조

일렬로 나열하지 않고 자료 순서나 관계가 복잡한 구조를 말한다.

 

그래프(Graph)

그래프는 Node(정점)와 Edge(간선)로 이루어진 자료 구조이다.

ex) Node는 도착점이고, Edge는 도착점으로 가는 길이다.

 

트리(Tree)는 루트가 하나이고 사이클이 아래로만 흐르는 방향 그래프이다.

 

1. 방향

1) 방향 그래프(Directed Graph)

Edge(간선)에 방향성이 존재하는 그래프

Edge의 방향으로만 이동할 수 있다.

 

셀프 엣지 : 자기 자신을 가르키는 방향

 

2) 무방향 그래프(Undirected Graph)

두 Node(정점)을 연결하는 Edge(간선)에 방향성이 없는 그래프

 

 

2. 사이클(Cycle)

1). 사이클(Cycle)
그래프 내에 Node(정점)들이 서로 서클을 만들어서 하나의 서클 이상이 있는 그래프
단순 경로의 시작 정점과 종료 정점이 동일한 경우

2). 비순환 그래프(Acyclic Graph)

사이클이 없는 그래프

3. 완전 그래프(Complete Graph)

그래프에 속해 있는 모든 정점이 서로 연결되어 있는 그래프

무방향 완전 그래프

+가중치 그래프

 

 

※ 그래프를 표현하는 방법

1. 인접행렬(Adjacency Matrix)

서로 연결되면 1
연결이 안되면 0

 

정점의 개수가 N인 그래프를 인접행렬로 표현한 것이다.

무방향 그래프르르 인접 행렬로 표현한다면 이 행렬은 대칭 행렬(Symmetric Matrix)이 된다.

2. 인접 리스트(Adjacency List )

그래프를 표현할 때 가장 일반적인 방법

배열에 노드들을 나열하고 관계를 연결 리스트로 표현하는 방법

 

모든 정접을 인접 리스트에 저장한다.

각각의 정점에 인접한 정점들을 리스트로 표시한 것이다.

 

 

 

 

면접에서 나올 수 있는 질문

• 인접행렬과 인접리스트의 차이점과 각각의 장단점에 대해 이야기 해보세요
• 연결그래프와 완전그래프의 차이점에 대해 이야기 해보세요
• (원래 그래프의 그림을 주고) 이 그래프로 신장 트리 N개를 만들어 보세요
• 최소신장트리를 찾을 수 있는 알고리즘에 대해 설명