[자료구조] 그래프(Graph) 개념

그래프(Graph)

그래프는 아이템(사물 또는 추상적 개념)들과 이들 사이의 연결관계를 표현한다.
단순히 정점,노드(N, node)와 그 노드를 연결하는 간선(E, edge)을 하나로 모아 놓은 자료 구조라고 할 수 있다.
Ex) 지도, 지하철 노선도의 최단 경로, 전기 회로의 소자들, 도로(교차점과 일방 통행길), 선수 과목 등

그래프와 트리의 차이점

• 오일러 경로
  • 그래프에 존재하는 모든 간선(edge)을 한번만 통과하면 다시 정점(vertex)으로 돌아오는 그래프를 말한다.
  • 그래프에 존재하는 모든 정점에 연결된 간선의 갯수가 짝수일때만 오일러 경로가 존재한다.

그래프(Graph)와 관련된 용어

• 정점(Vertex): 위치라는 개념. 노드(node)라고도 부름
• 간선(edge): 위치 간의 관계. 즉, 노드를 연결하는 선
• 인접 정점(adjacent vertex): 간선에 의해 직접 연결된 정점
• 정점의 차수(degree): 무방향 그래프에서 하나의 정점에 인접한 정점의 수
  • 무방향 그래프에 존재하는 정점의 모든 차수의 합 그래프의 간선 수의 2배
• 진입 차수(in-degree): 방향 그래프에서 외부에서 오는 간선의 수
• 진출 차수(out-degree): 방향 그래프에서 외부로 향하는 간선의 수
• 경로 길이(path length): 경로를 구성하는데 사용도니 간선의 수
• 단순 경로(simple path): 경로 중에서 반복되는 정점이 없는 경우
• 사이클(cycle): 단순 경로의 시작 정점과 종료 정점이 동일한 경우

그래프(Graph)의 특징

• 그래프는 네트워크 모델이다.
• 2개 이상의 경로가 가능하다. -> 노드들 사이에 무방향/방향에서 양방향 경로를 가질 수 있다.
• self-loop뿐 아니라 loop/circuit 모두 가능하다
• 루트 노드라는 개념이 없다.
• 부모-자식의 관계가 아니다
• 순회는 DFS(깊이우선탐색)나 BFS(너비우선탐색)로 이루어진다.
• 그래프는 순환 혹은 비순환이다.
• 그래프는 크게 방향 그래프와 무방향 그래프가 있다.
• 간선의 유무는 그래프에 따라 다르다.

---

그래프의 유형

무방향그래프(Undirected Graph)

• 서로 대칭적인 관계를 연결해서 나타낸 그래프
• 간선에 방향이 없는 그래프, 무방향 그래프의 간선은 간선을 통해서 양 방향으로 갈수 있다.
• 정점 A와 B를 연결하는 간선은 (A,B)와 같이 표현한다.
• 무방향그래프에서는 (A,B) == (B,A) 이다.
• ex) 양방향 통행 도로

방향그래프(Directed Graph)

• 간선을 화살표로 표현. 간선에 방향성이 존재하는 그래프이다.
• A -> B 로 갈 수 있는 간선은 <A,B>로 표시한다.
• <A,B> 와 <B,A>는 다르다.
• ex) 일방 통행

가중치그래프(Weighted Graph)

• 간선에 비용이나 가중치가 부여된 그래프이다.
• 가중치는 두 정점 사이의 거리, 지나는 시간, 금액등이 될수 있으며 또한 음수인 경우도 존재한다.
• 두 정점 간의 이동방향이 다를경우 가중치가 다를 수 있다.
• ex) 도시-도시의 연결, 도로의 길이, 회로 소자의 용량, 통신망의 사용료 등

연결 그래프

• 무방향 그래프에 있는 모든 정점쌍에 대해서 항상 경로가 존재하는 경우
• ex) 트리: 사이클을 가지지 않는 연결 그래프

비연결 그래프

• 무방향 그래프에서 특정 정점쌍 사이에 경로가 존재하지 않는 경우

순환(사이클) 그래프

• 단순 경로의 시작 정점과 종료 정점이 동일한 경우

비순환 그래프

• 사이클이 없는 그래프

완전 그래프

• 그래프에 속해잇는 모든 정점이 서로 연결되어 있는 그래프
• 무방향 완전 그래프
  • 정점 수N개 이면 간선의 수 N*(N-1)/2

---

그래프의 표현2가지

그래프는 주로 2가지 방법을 이용하여 표현한다. 인접행령, 인접리스트
메모리나 성능을 고려해서 결정해야 한다.

1. 인접행렬

인접 행렬은 N x N Boolean 행렬로서 matrix[i][j]가 true 라면 i->j로의 간선이 있다는 뜻이다.

if(간선(i,j)가 존재한다면)
    matrix[i][j] = 1;
else
    matrix[i][j] = 0;

a[i][j] = 0 이면 간선이 없다, a[i][j] = 1 이면 간선이 있다.
N개의 정점을 가진 그래프라면 NxN배열에 저장하여 표현한다. -> 간선의 수와 무관하게 항상 N^2개의 메모리 공간이 필요하다.
무방향 그래프를 인접행렬로 표현한다면 이 행렬은 대칭 행렬이 된다.
인접 행렬에서도 너비우선탐색이 가능하다. 단, 효율성이 떨어진다. 인접한 노드를 찾기 위해서는 모든 노드를 전부 순회해야 하기 때문이다.

단점
정점의 개수 N이 커지면 필요한 메모리크기는 N^2에 비례하여 커짐, 어떤 정점의 인접정점을 찾을때마다 N개의 정점을 탐색해야한다. 정점의 개수에 비례하여 시간도 증가한다.

2. 인접 리스트(Adjacency List)

인접 리스트(Adjacency List)로 그래프를 표현하는 것이 가장 일반적인 방법이다.

• 모든 정점을 인접리스트에 저장한다. 즉, 각각의 정점에 인접한 장점들을 리스트로 표시한 것이다.

  • 배열(혹은 해시테이블)과 배열의 각 인덱스마다 존재하는 또 다른 리스트를 이용해서 인접 리스트를 표현

• 무방향 그래프에서 (a,b) 간선은 두번 저장된다.

  • 한 번은 a정점에 인접한 간선을 저장하고 다른 한 번은 b에 인접한 간선을 저장한다.
  • 정점의 수:N, 간선의 수: E인 무방향 그래프의 경우 -> N개의 리스트, N개의 배열, 2E개의 노드가 필요

• 트리에선 특정 노드 하나(루트 노드)에서 다른 모든 노드로 접근이 가능 -> Tree클래스 불필요

  • 그래프에선 특정 노드에서 다른 모든 노드로 접근이 가능하지는 않음 -> Graph 클래스 필요

    class Graph { public Node[] nodes; }
    
    class Node {
      public String name;
      public Node[] children;
    }

• 경로에 관한 정보가 아니다. 가중치 정보를 표시하려면 노드에 가중치 필드를 추가하여 표현해야 한다.

3. 인접리스트와 인접 행렬 선택 방법

• 인접리스트
  • 그래프 내에 적은 숫자의 간선만을 가지는 희소 그래프(Sparse Graph)의 경우 -> 인접 행렬로 표현하면 공간낭비가 심함
  • 장점
    • 어떤 노드에 인접한 노드들을 쉽게 찾을 수 있다.
    • 그래프에 존재하는 모든 간선의 수는 O(N+E) 안에 알수 있다. -> 인접 리스트 전체를 조사한다.
  • 단점
    • 간선의 존재 여부와 정점의 차수: 정점 i의 리스트에 있는 노드의 수 즉, 정점 차수만큼의 시간이 필요
• 인접 행령
  • 그래프에 간선이 많이 존재하는 밀집 그래프(Dense Graph)의 경우
  • 장점
    • 두 정점을 연결하는 간선의 존재여부를 O(1)안에 즉시 알수 있다.(M[i][j] == 1 인지 아닌지 보면 됨)
    • 정점의 차수는 O(N)안에 알 수 있다. : 인접 배열의 i번 째 행 또는 열을 모두 더한다.
  • 단점
    • 어떤 노드에 인접한 노드들을 찾기 위해서는 모든 노드를 전부 순회해야 한다.
    • 그래프에 존재하는 모든 간선의 수는 O(N^2)안에 알 수 있다. : 인접 행렬 전체를 조사한다.

---

그래프 탐색

일반적인 방법은 2가지가 있다. 깊이 우선 탐색(Depth-First Search), 너비 우선 탐색(Breadth-First Search)

깊이 우선 탐색(DFS, Depth-First Search)

루트 노드(혹은 다른 임의의 노드)에서 시작해서 다음 분기(branch)로 넘어가기 전에 해당 분기를 완벽하게 탐색하는 방법

• 넓게 탐색하기 전에 깊게(deep) 탐색하는 것이다
• 사용하는 경우: 모든 노드를 방문 하고자 하는 경우에 이 방법을 선택한다.(깊이 우선 탐색이 너비 우선 탐색보다 좀 더 간단하다

import java.util.Iterator;
import java.util.LinkedList;

public class Graph {
    private int v;    //노드의 개수
    private LinkedList<Integer> adj[];    //인접리스트

    //생성자
    Graph(int v){
        this.v = v;
        adj = new LinkedList[v];
        for(int i=0; i<v ;i++) {
            adj[i] = new LinkedList();
        }
    }

    //노드를 연결
    void addEdge(int v, int w) {
        adj[v].add(w);    //v노드와 w노드 사이에 간선이 있다는 뜻
    }

    //DFS에 의해 사용되는 함수
    void DFSUtil(int v, boolean visited[]) {
        //현재 노드를 방문한 것으로 표시하고 값을 출력
        visited[v] = true;
        System.out.print(v+" ");

        //방문한 노드의 인접 노드들을 다 가져온다.
        Iterator<Integer> i = adj[v].listIterator();
        while(i.hasNext()) {
            int n = i.next();
            //방문하지 않은 노드면 해당 노드를 시작 노드로 다시 DFSUtil 호출
            if(!visited[n]) {
                DFSUtil(n, visited);
            }
        }
    }

    //주어진 노드를 시작 노드로 DFS탐색
    void DFS(int v) {
        //노드 방문 여부 판단, 초깃값: false
        boolean visited[] = new boolean[this.v];

        //v를 시작노드로 DFSUtil 순환 호출
        DFSUtil(v,visited);
    }

    //모든 노드에서 DFS탐색
    void DFS() {
        //노드 방문 여부 판단, 초깃값: false
        boolean visited[] = new boolean[this.v];

        //비연결형 그래프의 경우, 모든 정점을 하나씩 방문
        for(int i=0; i<this.v ;i++) {
            if(visited[i] == false)
                DFSUtil(i, visited);
        }
    }
}

public class Main {
    public static void main(String[] args) throws IOException{    
        Graph g = new Graph(4);

        g.addEdge(0, 1);
        g.addEdge(0, 2);
        g.addEdge(1, 2);
        g.addEdge(2, 0);
        g.addEdge(2, 3);
        g.addEdge(3, 3);

        System.out.println("DFS - 2");
        g.DFS(2);
        System.out.println("DFS ");
        g.DFS();
    }
}

너비 우선 탐색(BFS, Breadth-First Search)

루트 노드(혹은 다른 임의의 노드)에서 시작해서 인접한 노드를 먼저 탐색하는 방법

• 깊게 탐색하기 전에 넓게(wide) 탐색하는 것이다.
• 사용하는 경우: 두 노드 사이의 최단 경로 혹은 임의의 경로를 찾고 싶을 때 이 방법을 선택한다.

  import java.util.Iterator;
  import java.util.LinkedList;
  import java.util.Queue;
  

public class Graph {
private int v; //노드의 개수
private LinkedList adj[]; //인접리스트

//생성자
Graph(int v){
    this.v = v;
    adj = new LinkedList[v];
    for(int i=0; i< this.v ; i++) {
        adj[i] = new LinkedList();
    }
}

//노드를 연결
void addEdge(int v, int w) {
    adj[v].add(w);
}

//s를 시작노드로 한 BFS로 탐색하면서 탐색한 노드들을 출력
void BFS(int s) {
    //노드의 방문 여부 판단 초깃값 false
    boolean visited[] = new boolean[this.v];
    //BFS구현을 위한 큐 생성
    Queue<Integer> queue = new LinkedList<Integer>();

    //현재 노드를 방문한 것으로 표시하고 큐에 삽입
    visited[s]=true;
    queue.add(s);

    //큐가 빌때 까지 반복
    while(!queue.isEmpty()) {
        s = queue.poll();
        System.out.print(s + " ");

        //방문한 노드와 인접한 모든 노드를 가져온다.
        Iterator<Integer> i = adj[s].listIterator();
        while(i.hasNext()) {
            int n = i.next();
            //방문하지 않은 노드면 방문한것으로 표시하고 큐에 삽입
            if(!visited[n]) {
                visited[n] = true;
                queue.add(n);
            }
        }
    }
}

}

```java
public class Main {
    public static void main(String[] args) throws IOException{
        Graph g = new Graph(4);

        g.addEdge(0, 1);
        g.addEdge(0, 2);
        g.addEdge(1, 2);
        g.addEdge(2, 0);
        g.addEdge(2, 3);
        g.addEdge(3, 3);

        g.BFS(2);
    }
}

---

참고

https://gmlwjd9405.github.io/2018/08/13/data-structure-graph.html

https://herong.tistory.com/entry/Data-Structure-%EA%B7%B8%EB%9E%98%ED%94%84Graph