그래프 - 인접 리스트 & 인접 행렬

 

 

 

그래프

비선형 자료구조 그래프는 정점(V)와  간선(Eege)로 이루어진 자료구조이다. G(V,E)   - 정점(Vertex)는 노드(node)로 표현될 수 있다.

 

충처: https://www.geeksforgeeks.org/introduction-to-graphs-data-structure-and-algorithm-tutorials/

 

---

그래프 관련 용어 

 

- 정점의 차수 (Degree)

   -> 정점에 연결된 간선의 수 

 

- outDegree / inDegree

  -> 정점으로부터 나가는 간선을 outdegree, 정점으로 들어오는 간선을 indegree라고 한다. 

 

- 가중치 그래프(Weighted Graph) 

   -> 간선에 자중치 혹은 비용이 할당된 그래프 

        연결된 정점들 간 탐색에 드는 비용이나, 연결 강도를 표현한다.

        *가중치 그래프 구현시 객체로 묶어서 표현하면 가독성 좋은 코드를 작성할 수 있다.

 

- 경로 (path)

   -> 정점에 연결된 간선을 따라 탐색하는 순서대로 나타낸 것  

   **  거리: 간선의 가중치

        경로: 탐색 순서에 따라 정점 나열

 

- 사이클(Cycle)

   -> 간선의 경로 중 시작 정점과 끝 정점이 동일한 경로 

   ** 트리는 사이클이 없는 그래프! 

 

 

가중치 노드 예시)

class Node{
 int node;
 int cost;
 
 public Node(int node, int cost){
   this.node = node;
   this.cost = cost;
 }
 
}

---

 

그래프의 종류 

 

- Null 그래프 

 -> 간선이 없는 그래프 

 

- Trivial 그래프 

 -> 정점이 1개인 그래프이자 가장 작은 그래프이다.

 

- 무방향 그래프(Undirected Graph)

  -> 간선에 방향이 없는 그래프 5와 4을 연결할 때 5 -> 4임과 동시에 5 -> 4 이다. (노드 사이 관계가 양방향)

 

- 방향 그래프(Directed Graph)

 -> 간선에 방향이 있는 그래프이다. (노드 사이의 관계가 일방향)

 

 

- 연결 그래프 (Connected Graph) 

 -> 모든 정점이 연결되어 있다. 하나의 정점에서 간선을 따라 모든 정점을 방문할 수 있다.

-

비연결 그래프 (Disconnected Graph) 

 -> 연결 그래프와는 다르게 하나의 정점이라도 연결되어 있지 않아서, 간선을 따라 모든 정점을 방문할 수 없다면 비연결 그래프 이다.

 

- 정규 그래프(Regular Graph)

 -> 모든 정점이 동일한 차수를 가지는 그래프이다.

 

- 완전 그래프(Complete Graph)

 -> 모든 노드가 서로 연결된 그래프이다. 노드 수가 n일 때, 간선의 수는 n(n-1).2이다. (n은 노드의 수)

 -> 완전 그래프는 항상 연결 그래프를 포함한다.

 

. - 사이클 그래프(Cycle Graph)

   -> 그래프 자체가 순환인 그래프이다. 각 정점의 차수는 2

 

- 순환 그래프(Cyclic Graph)

   -> 하나 이상의 주기를 가진 그래프이다.

 

- 방향이 있는 비순환 그래프 (Directed Acyclic Graph)

 ->  순환을 포함하지 않는 방향성 그래프 

 

- 이분 그래프(Bipartile Graph)

 -> 무방향 그래프의 그룹을 나누었을 때 각 그룹 간 연결이 없고, 다른 그룹 간에만 연결되는 그래프 

 

- 가중치 그래프 ( Weighted Graph)

 -> 간선에 가중치 혹은 비용이 할당되어 있다. 

 

---

 

  대표적인 그래프의 표현 방법 

 

1. 인접 행렬 

 

•  일반적으로 2차원 배열을 이용해서 표현한다.
  • adj[r][c] = 연결여부 (혹은 가중치)  
• 공간 복잡도 
  •   V개의 정점이 있다면, V*V 만큼의 공간을 차지한다. 
• 시간 복잡도 
  •  연결 관계(혹은 가중치) 조회 및 저장 : O(1)
  •  점정에 연결된 모든 간선 조회: O(V) 

 

 

출처: 패스트 캠퍼스 - Java 알고리즘

// 정점과 간선의 갯수를 입력한다.
int v = 10;
int e = 10;
int[][] adj = new int[v+1][e+1];

//연결 정보를 입력 받는다.
 for(int i=0; i<e; i++){
    int src = Integer.parseInt(br.readLine());
    int dst = Integer.parseInt(br.readLine());
    adj[src][dst] = 1;
    // adj[dst][src] = 1; 무방향 그래프라면, 반대 방향도 초기화
 }

 

 

2. 인접 리스트

 

 - 간선의 정보를 리스트를 기반으로 저장하는 방법이다.

 

• 보통 List<Node>[] graph의 형태로 선언한다. (List<Integer>[] graph)
  • 배열안에 정점의 정보
  • 리스트 안에 각 정점의 간선 정보를 저장한다.
  • graph[r] = new ArrayList<Node>();
•    공간 복잡도 
  • V개의 정점, E개의 간선이 있다면, V+E만큼 공간을 차지한다.
• 시간 복잡도 
  • 연견관계(가중치) 조회 및 저장 : O(Outdegree(V))
  • 정점에 연결된 모든 간선 조회: O(Outdegree(V))
  • 시간 복잡도는 각 정점에 리스트의 크기에 달려있다.

 

 

출처: 패스트 캠퍼스 - Java 알고리즘

 

int v = 10;

List<Integer>[] graph = new List<v+1];

for(int i=0; i<=v; i++){
 graph[i] = new ArrayList<>();
}

for(int i=0; i<e; i++){
   int src = sc.nextInt();
   int dst = sc.nxtInt();
   graph[src].add(dst);
   //graph[dst].add(src); //무방향 그래프 시 추가
}

 

 

3. 인접 행렬과 인접 리스트 비교 

 

정점:V 간선:E	인접 행렬	인접 리스트
간선 조회 및 저장	O(1)	O(outDegree(V))
정점의 차수 계산	O(V)	O(outDegree(V))
전체 노드 탐색	O(V^2)	O(E)
메모리	V*V	V+E

 

 

 

 

---

참고자료

https://velog.io/@kwontae1313/%ED%8A%B8%EB%A6%AC%EC%99%80-%EA%B7%B8%EB%9E%98%ED%94%84%EC%97%90-%EB%8C%80%ED%95%B4-%EC%95%8C%EC%95%84%EB%B3%B4%EC%9E%90

그래프(Graph)에 대해 알아보자

https://www.geeksforgeeks.org/introduction-to-graphs-data-structure-and-algorithm-tutorials/

Introduction to Graphs - Data Structure and Algorithm Tutorials - GeeksforGeeks

https://fastcampus.co.kr/dev_online_codingtest

핵심유형 20개로 한 번에 끝내는 알고리즘 코딩테스트 with Java 초격차 패키지 Online. | 패스트캠퍼