[자료구조] Graph

Grahp

• 여러 개의 점들이 서로 복잡하게 연결되어 있는 관계를 표현한 자료구조
• x축과 y축이 있는 수학에서의 그래프와 달리 거미줄처럼 여러개의 점과 선으로 이루어진 복잡한 네트워크 모양을 하고 있다.

 

그래프 모양

Graph의 구조

• 직접적인 관계가 있는 경우 두점이 직접적인 선으로 이어진다.
• 간접적인 관계인 경우 몇개의 점과 선에 걸쳐 이어진다,
• 그래프에서 하나의 점을 정점(vertex), 하나의 선은 간선(edge)라고 합니다. 

 

Graph의 표현 방식

 

인접 행렬

• 두 정점을 바로 이어주는 간선이 있다면 두 정점은 인접한다 라고 한다.
• 서로 다른 정점들이 인접한 상태인지를 2차원 배열의 형태로 나타낸다.
• A라는 정점과 B라는 정점이 이어져 있다면 1(true), 이어져 있지 않다면 0(false)로 표시한다.
• 가중치 그래프라면 1대신 관계에서 의미 있는 값을 저장한다. (ex. 네비게이션이라면 거리를 입력)

예시

• A(0)의 진출차수는 2개 (A->B), (A->C)
  • [0][1] = 1
  • [0][2] = 1
• B(1)의 진출차수는 1개 (B->C)
  • [1][2] = 1
• C(2)의 진출차수는 1개 (C->B)
  • [2][1] = 1
• 인접 행렬을 사용 하는 경우
  • 한 개의 큰 표와 같은 모습을 한 인접 행렬은 두 정점 사이에 관계가 있는지, 없는지 확인하기에 용이하다.
    • A에서 B로 진출하는 간선이 있는지 확인할때  [0][1]의 값을 확인 하면된다.
  • 가장 빠른 경로(shortest)를 찾고자 할 때 주로 사용된다.

 

인접리스트

• 각 정점이 어떤 정점과 인접하는지를 리스트의 형태로 표현
• 각 정점마다 하나의 리스트를 가지고 있고, 이리스트는 자신과 인접한 다른 정점을 담고 있다.

인접 리스트

• 간선이 두 개가 있는 경우 (A), 인접한 점들을 나열하는데 순서는 보통 중요하지 않다. 
• 우선 순위를 고려하여 구현할 수 있으나, 우선 순위를 다뤄야 한다면 더 적합한 자료 구조 (queue, stack)등을 사용하는것이 좋다. (예외는 있다.)
• 인접 리스트를 사용 하는 경우
  • 메모리를 효율적으로 사용하고 싶을때 인접 리스트를 사용 한다.
    • 인접 행렬은 인접 가능한 모든 경우의 수를 저장하기 때문에 상대적으로 메모리를 많이 차지한다. (인접하지 않으면 0(false)을 저장해야함)

Graph의 실사용 예제

• 포털 사이트의 검색 엔진, 내비게이션, SNS에서 친구 관계등
• 내비게이션을 입력할때 도착지를 가는 도중에 경유해서 가야하는곳이 있다면 (서울에서 부산을 갈때 대전을 경유한다면) 
  • 정점 : 서울, 대전, 부산
  • 간선 : 서울-대전, 대전-부산, 부산-서울
• 위와 같이 간선으로 이동할수 있음(연결 유무)을 나타내기만 한다면 비가중치 그래프
• 간선으로 이동해야하는 거리까지의 정보등을 포함한다면 가중치 그래프
  • 서울-140km-대전, 대전-200km-부산, 부산-325km-서울

 

추가적인 용어

• 무(방)향 그래프(undirected graph): 정점간 간선으로 연결되어있을때 방향이 없는 그래프 (서로 이동이 가능한 그래프),  정점간 단방향(A에서 B는 갈수 있으나 B에서 A는 못가는 경우)이 아닌 경우
• 진입차수(in-degree), 진출차수(out-degree) = 한 정점에 진입(들어오는 간선), 진출(나가는 간선)하는 간선이 몇 개인지를 나타낸다.
• 자기루프(self loop) : 정점에서 진출하는 간선이 곧바로 자기 자신에게 진입하는 경우 자기 루프를 가졌다라고 한다. - 다른 정점을 거치지 않는다.
• 사이클(cycle) : 한 정점에서 출발하여 다시 해당 정점으로 돌아갈 수 있다면 사이클이 있다라고 표현 한다.

 

JAVA로 인접 행렬 그래프 구현

import java.util.*;

public class ArrayGreph { 
	private int[][] graph;

  public void setGraph(int size) {
    graph = new int[size][size];

    for(int i = 0; i < size; i++) {
      for(int j = 0; j < size; j++) {
        graph[i][j] = 0;
      }
    }
  }

  public int[][] getGraph() {
    return graph;
  }

  public void addEdge(int from, int to) {
    if(from >= graph.length || to >= graph.length) return;
    graph[from][to] = 1;
  }

  public boolean hasEdge(int from, int to) {
    if(from >= graph.length || to >= graph.length) return false;
    else if(graph[from][to] == 1) return true;
    else return false;
  }

  public void removeEdge(int from, int to) {
    if(from >= graph.length || to >= graph.length) return;
    graph[from][to] = 0;
  }
}

• setGraph(size): 그래프에 size만큼의 버텍스를 추가
• getGraph(): 인접 행렬 정보가 담긴 배열을 반환
• addEdge(from, to): from(Vertex)와 to(Vertex) 사이의 간선을 추가
• hasEdge(from, to): from(Vertex)와 to(Vertex) 사이의 간선이 존재하는지 여부를 Boolean으로 반환
• removeEdge(from, to): from(Vertex)와 to(Vertex) 사이의 간선을 삭제

 

JAVA로 인접리스트 그래프 구현

import java.util.*;

public class ListGreph { 
  private ArrayList<ArrayList<Integer>> graph;

  public ListGreph() {
    graph = new ArrayList<>();
  }

  public void setGraph(int size){
    for(int i = 0; i < size; i++) {
      graph.add(new ArrayList<Integer>());
    }
  }

  public ArrayList<ArrayList<Integer>> getGraph() {
    return graph;
  }

  public void addEdge(int from, Integer to) {
    if(from < 0 || to < 0 || from >= graph.size() || to >= graph.size()) return;
    graph.get(from).add(to);
	graph.get(to).add(from);
  }

  public boolean hasEdge(int from, int to) {
    if(from < 0 || to < 0 || from >= graph.size() || to >= graph.size()) return false;
    else return graph.get(from).contains(to);
  }

  public void removeEdge(int from, int to) {
    if( from < 0 || to < 0 || from >= graph.size() || to >= graph.size()) return;
    
    if(graph.get(from).contains(to)) {
      graph.get(from).remove((Integer) to);
    }

    if(graph.get(to).contains(from)) {
      graph.get(to).remove((Integer) from);
    }
  }
}

• setGraph(size): 그래프에 size 만큼의 버텍스를 추가
• addEdge(fromVertex, toVertex): from(Vertex)와 to(Vertex) 사이의 간선을 추가
• hasEdge(fromvertex, toVertex): from(Vertex)와 to(Vertex) 사이의 간선이 존재하는지 여부를 Boolean으로 반환
• removeEdge(fromVertex, toVertex): from(Vertex)와 to(Vertex) 사이의 간선을 삭제