그래프

Sundae·2023년 12월 7일

자료구조와 알고리즘

목록 보기

17/19

그래프

그래프(graph)는 관계에 특화된 자료구조로서 데이터가 어떻게 연결되어있는지 쉽게 파악할 수 있다.

그래프는 정점(vertex)과 간선(edge)들로 구성된다. 흔히 각각의 데이터를 노드라고 부르지만 그래프에서는 각 노드를 정점이라 부르며, 그 정점을 잇는 선을 간선이라 부른다. 간선으로 연결된 정점은 서로 인접(adjacent)한다고 한다.

아래의 이미지는 친구 관계를 나타내는 그래프이다. 그래프 용어로 나타내면 앨리스와 밥이라는 두 정점은 한 간선을 공유하고 서로 인접한다고 할 수 있다.

- 비연결 그래프

무방향 그래프에 있는 모든 정점에 대해서 항상 경로가 존재하는 경우 연결 그래프라고 하며, 정점에 경로가 존재하지 않는 경우 비연결 그래프라고 한다.

- 방향 그래프(directed graph)

우리가 흔히 사용하는 인스타그램 같은 소셜 SNS에선 팔로우라는 기능을 사용할 수 있다. 이때, 방향 그래프(directed graph)를 매우 유용하게 사용할 수 있다.
예를 들어, 아래 이미지처럼 앨리스는 밥을 팔로우하는데, 밥은 앨리스를 팔로우하지 않는 경우도 있을 것이다. 또한, 신시아와 밥은 서로를 팔로우한다.

이러한 데이터를 해시 맵과 리스트로 간단히 저장할 수 있다.

"Alice" : ["Bob", "Cynthia"],
"Bob" : ["Cynthia"],
"Cynthia" : ["Bob"]

- 무방향 그래프(undirected graph)

두 정점을 연결하는 간선에 방향이 없는 그래프이며, 양 방향으로 이동이 가능하다. 만약 모든 친구 관계가 상호적인 소셜 SNS를 만든다면 무방향 그래프를 고려할 수 있다.

그래프 - 인접 리스트 구현

위에서 해시 맵으로 간단히 그래프를 구현할 수 있었다. 이제 그래프를 객체 지향, 클래스로 구현해보자.

다음은 무방향 그래프이자, 하나의 정점을 표현하기 위한 클래스이다.

/*
*  인접 리스트
* */
public class Vertex {

    private String value;
    private List<Vertex> adjacentVertices;

    public Vertex(String value){
        this.value = value;
        this.adjacentVertices = new ArrayList<>();
    }
    public String getValue(){return value;}
    public List<Vertex> getAdjacentVertices(){return adjacentVertices;}

    // 정점 추가
    public void addAdjacentVertex( Vertex vertex ){
        if( vertex.getAdjacentVertices().contains( vertex ) ) return;
        adjacentVertices.add(vertex);
        vertex.addAdjacentVertex(this);
    }

필드 value는 사람 이름을 포함한 문자열이며 adjacentVertices는 해당 정잠과 연결되는 모든 정점을 포함한다.

addAdjacentVertex() 메서드로 인접한 정점을 추가할 수 있어 누가 누구를 팔로우 했는지 쉽게 알 수 있다. addAdjacentVertex 메서드에서 adjacentVertices.add(vertex)로 밥을 앨리스의 리스트(adjacentVertices)에 추가한다. 그리고 밥의 정점에 vertex.addAdjacentVertex(this);를 호출한다. 무한 루프가 발생할 수 있기 때문에
if( vertex.getAdjacentVertices().contains( vertex ) ) return;를 추가한다. 이렇게 상호 관계를 만들 수 있다.