JAVA_자료구조_(Graph)

Graph

그래프, 그래프는 여러개의 점들이 복잡하게 연결되어 있는 관계를 표현한 자료구조이다. 

우리가 아는 그래프는 X축, Y축 나눠서 선 그리고 함수 그리고 하는거였는데, 컴퓨터에서 그래프는 다른의미를 갖는다. 

마치 거미줄처럼 복잡한 네트워크 망과 같다.

자료구조 그래프 예시(출처 : 코드스테이츠)

Graph의 구조

단순한 그래프의 예시 (출처 : 코드스테이츠)

1. 점(데이터)를 정점 이라고 한다. 
   
   
2. 데이더와 데이터가 직접적인 관계가 있는 경우 두 점 사이를 이어주는 선이 있다. 
   
   
3. 간접적인 관계라면 한번에 연결 안되고 몇 개의 점, 선에 걸쳐 이어진다 (옆자리 사람이 친구의 친구 같은 느낌이다. 몇 다리 건너건너서 아는사람 같은거)

 

Graph의 표현방식

인접 행렬

간단한 그래프 형태(출처 : 코드스테이츠)

앞서 정점(데이터)를 직접 연결하면 직접적인 관계라고 했다.

이 상태를 두 정점이 "인접하다."라고 한다. 

저로 다른 정점들이 인접한 상태인지 나타낸 것을 인접 행렬이라고 한다. (2차원 배열의 형태다)

A, B 가 서로 이어져 있으면 1(true) , 아니면 0(false)로 표시하는 일종의 표다.

여기서 가중치가 붙으면 인접했을때 1을 쓰는게 아니고 가중치에 따라 다른숫자가 들어간다. 

• A의 진출차수는 1개 : A —> C
  • [0][2] == 1
• B의 진출차수는 2개 : B —> A, B —> C
  • [1][0] == 1
  • [1][2] == 1
• C의 진출차수는 1개 : C —> A
  • [2][0] == 1

 

인접 행렬사용 예시 

• 두 정점 사이에 관계가 있는지 없는지 확인에 용이하다.(표만 보면 바로 알 수 있으니까)
  
  
• 가장 빠른경로(shortest path)를 찾을때 사용된다. (직접 연결된게 가장 빠르고, 아니면 간접으로 연결된거 찾아서 가면되니까)

 

인접 리스트

 인접 리스트는 각 정점이 어떤 정점과 인접하는지(연결되어 있는지)를 리스트 형태로 뵤현한 것이다. 

하나의 정점마다 이 리스트를 가진다 리스트에는 자신과 인접한 다른 정점을 가진다.
(예)A정점에서 연결된 애들 줄줄줄 리스트로 표현한다고 보면 됨 ) 

간단한 그래프 형태(출처 : 코드스테이츠)

인접 리스트를 그림으로 표현한 예 (출처 : 코드스테이츠)

위의 그림을 보면 삼각형으로 생긴 그래프를 인접 리스트로 표현 할 때 B - A - C 로 썻는데, 사실 B - C - A로 써도 무방하다고 한다. (순서가 중요하지 않음)

우선순위가 정해지지 않은이상 순서는 상관 하지 않는 편이다.

인접리스트는 메모리를 효과적으로 사용하고싶을때 사용된다. 

인접행렬은 모든 경우의 수를 저장했지만, 만약 나는 A에 관한 인접관련 정보를 알고 싶으면 그냥 A의 인접리스트 하나만 가져오면 된다(인접 행렬의 크기 > 인접 리스트의 크기)

 

Graph의 실사용 예제

그래프는 위에서 계속 인접(연결되어 있다.)를 강조했는데 어디에 써먹을까?

대표적인 예시가 네비게이션이다.

특정 경로를 지나느냐, 안지나느냐 -> 인접하느냐 인접하지 않느냐 로 대응 가능하다.

예를 들어서 서울에서 부산까지 이동한다고 치자, 그 과정에서 특정한 지역(대전)을 한번 거쳐서 가는 것이다.

(서울) - (다른 지역,대전) - (부산) 순으로 말이다.

여기서 정점은 

서울 , 대전 , 부산 이 될 것이고

간선(연결선)은

서울- 대전 / 대전 - 부산 / 부산 -서울 이 될 것이다. 

->연결된 경로를 나타낸다 = 네비게이션에서 이동 가능한 경로를 보여주는것과 같다. 

만약에 뜬금없이 몰디브를 경로에 넣으면 차로는 못가니까 간선이 연결되지 않는다 이를 "관계가 없다." 라고 한다.

지금까지 배운 것을 토대로 그래프로 위의 연결을 나타내면 

/*
	1 == 서울, 2 == 부산, 3 == 대전
	0은 연결되지 않은 상태, 1은 연결된 상태 (간선을 정수로 표현)
*/

[1] = [0, 1, 1] // 서울 - 부산 , 서울 - 대전
[2] = [1, 0, 1] // 부산 - 서울 , 부산 - 대전
[3] = [1, 1, 0] // 대전 - 서울 , 대전 - 부산

위와 같이 될 것이다. 

여기서 서울, 부산, 대전 사이의 거리를 우리가 지정하지 않은 상태로 하였으므로 그냥 연결되어 있다 정도만 알려주도록 0혹은 1으로 채워 넣어져 있다. 

만약, 1대신에 거리를 넣으면 -> 가중치를 넣는것과 같아진다. 

이때 

정점 

서울 , 대전, 부산 

간선 

서울 - 140km - 대전 / 대전 - 200km- 부산 / 부산 - 325km - 서울 로 나타낼 수 있다.(가중치 반영)

 

알아 두어야 할 그래프 용어

• 정점 (vertex): 노드(node)라고도 하며 데이터가 저장되는 그래프의 기본 원소
  
  
• 간선 (edge): 정점 간의 관계를 나타냄 (정점을 이어주는 선)
  
  
• 인접 정점 (adjacent vertex): 하나의 정점에서 간선에 의해 직접 연결되어 있는 정점
  
  
• 가중치 그래프 (weighted Graph): 연결의 강도(추가적인 정보, 위의 예시에서는 서울-부산으로 가는 거리 등)가 얼마나 되는지 적혀져 있는 그래프를 뜻함
  
  
• 비가중치 그래프 (unweighted Graph): 연결의 강도가 적혀져 있지 않는 그래프(0, 1로만 이루어진 그래프).
  
  
• 무(방)향 그래프 (undirected graph): 위의 예제에서 방향성이 있는 그래프, 만약 서울 -> 부산은 가능한데, 부산 -> 서울은 불가능 하면 무방향 그래프가 아니고, 둘이 양쪽으로 왔다갔다 가능하면 무방향 그래프이다.
  
  
• 진입차수 (in-degree) / 진출차수 (out-degree): 한 정점에 진입(들어오는 간선)하고 진출(나가는 간선)하는 간선이 몇 개인지를 나타냄
  
  
• 인접 (adjacency): 두 정점 간에 간선이 직접 이어져 있는 상태.
  
  
• 자기 루프 (self loop): 정점에서 진출하는 간선이 곧바로 자기 자신에게 진입하는 경우 자기 루프를 가졌다 라고 표현. 다른 정점을 거치지 않음, 알고리즘 순서도에서 고리형태로 자신에게 바로 돌아오는 것을 생각하면 됨
  
  
• 사이클 (cycle): 한 정점에서 출발하여 다시 해당 정점으로 돌아갈 수 있다면 사이클이 있다고 표현. 내비게이션 그래프는 서울 —> 대전 —> 부산 —> 서울 로 이동이 가능하므로, 사이클이 존재하는 그래프