[자료구조] 그래프 -1

본문과 관련하여 실습한 전체코드는 리파지토리에 별도 작성하였습니다.

https://github.com/ejImDev/data_structure_study.git

용어

• 그래프 : 정점(Vertex)과 간선(Edge)의 집합으로 하나의 간선은 두 개의 정점을 연결
  
• 그래프는 G=(V, E)로 표현
  
  • V=정점의 집합, E=간선의 집합
    
• 방향 그래프 : 간선에 방향이 있는 그래프
  

• 무방향 그래프 : 간선에 방향이 없는 그래프
  
  

• (a, b) : 정점 a와 b를 연결하는 간선
  

• <a, b> : 방향 그래프에서 정점 a에서 b로 이동하는 경우 간선의 표현
  
  

• 차수(Degree) : 정점에 인접한 간선의 수
  
• 진입차수(In-degree) : 방향그래프에서 들어오는 간선의 수
  

• 진출차수(Out-degree) : 방향그래프에서 나가는 간선의 수
  
  

• 경로(Path) : 시작 정점 u부터 도착점 v까지의 정점들을 나열하여 표현
  
  • ex) [a, c, b, e] : 정점 a로부터 도착점 e까지의 경로를 나타낸 것
    
• 단순경로(Simple) : 경로 상의 정점들이 모두 다른 경로
  
• 일반적인 경로 : 동일한 정점을 중복하여 방문하는 경우를 포함
  
  • ex) [a, b, c, b, e] 와 같이 b를 두번 방문
    
• 싸이클(Cycle) : 시작정점과 도착정점이 동일한 단순경로
  
  • ex) [a, b, e, d, c, a] 와같이 시작과 끝이 같고 중복이 없이 루프를 형성
    
• 연결성분 : 그래프에서 정점들이 서로 연결되어 있는 부분
  
  • 하나의 정점만 있는것도 연결성분이라고 함
    
    
• 가중치(Weighted) 그래프 : 간선에 가중치가 부여된 그래프
  
  • 가중치 : 두 정점 사이의 거리, 지나는 시간이 될 수도 있음. 음수인 경우도 존재
    
• 부분 그래프(Subgraph) : 주어진 그래프의 정점과 간선의 일부분(집합)으로 이루어진 그래프
  
  • 부분그래프는 원래의 그래프에 없는 정점이나 간선을 포함하지 않음
    
• 트리(Tree) : 싸이클이 없는 그래프
  
• 신장트리(Spanning Tree) : 주어진 그래프가 하나의 연결성분으로 구성되어 있을 때, 그래프의 모든 정점들을 싸이클 없이 연결하는 부분 그래프
  
  

그래프 자료구조

• 그래프를 자료구조로서 저장하는 방법
  
  1. 인접행렬(Adjacency Matrix)
     
  2. 인접리스트(Adjacency List)
     
     

1. 인접행렬
   
   • N개의 정점을 가진 그래프의 인접행렬은 2차원 NxN 배열에 저장
     
   • 배열이 a라면, 정점들을 0, 1, 2, …, N-1로 하여 정점 i 와 j 사이에 간선이 없으면 a[i][j]=0, 간선이 있으면 a[i][j]=1로 표현
     
   • 대칭행렬이 특징
     
   • 가중치그래프는 1 대신 가중치 저장
     
     
2. 인접리스트
   
   • 각 정점마다 1개의 단순연결리스트를 이용하여 인접한 각 정점을 노드에 저장
     
     

참고 자료 : ‘경기대학교 소프트웨어중심대학사업단 - JAVA 자료구조’ https://youtu.be/-t8EjJTazRM