[자료구조] Graph

1. Graph 란?

• 비선형 다대다 자료구조 입니다.
  • vertex와 edge로 객체간의 관계를 표현합니다.
  • 계층적 또는 네트워크 형식으로 연결되어 있습니다.
    • 명확한 부모-자식 관계가 존재 X
    • 1:n or n:n
• 현실세계의 다양한 문제를 효과적으로 모델링하기에 적합합니다.

 

용어

Vertex(정점)	정점
Edge(간선)	정점과 정점을 연결하는 간선을 의미합니다.
Adjacent(인접)	두 정점이 간선으로 연결되어 있을 경우, 두 정점은 "인접하다" 표현합니다.
Incident(부속)	정점간의 연결을 담당하는 간선을 "부속되었다" 표현합니다.
Degree(차수)	한 정점에 부속된 간선의 개수를 그 정점의 "차수"라 표현합니다.
Path(경로)	출발지에서 목적지로 이어지는 일련의 간선들을 의미합니다.
Cycle(사이클)	시작노드와 종료노드가 동일한 경로를 의미합니다. (경로 상의 노드는 중복 허용 X)
Loop(루프)	자기 자신을 가리키는 간선입니다.

 

   A----B----C
   |    |
   |    |
   |    |
   D----E
   |
   F

• 인접 : A와 B는 인접합니다.
• 부속 : 간선 DE는 D와 E에 부속되어 있습니다.
• 차수 : 노드 D의 차수는 3이다 (AD, DE, DF).
• 경로(A-E) : A-D-E 또는 A-B-E가 있습니다.
• 사이클 : A-D-E-B-A
• 루프 : 위 그래프에서는 루프가 없습니다.

 

2. 종류

무방향 그래프 vs  방향 그래프

• 간선의 방향이 있는지의 여부에 따라 나뉩니다.

 

무방향 그래프

   A-----B
   |     |
   |     |
   C-----D

• 양방향으로 연결이 가능합니다.

 

방향 그래프

   A---->B
   ^     |
   |     v
   C<----D

• 특정 방향으로만 연결이 가능합니다.

 

비가중 그래프 vs 가중 그래프

• 간선에 가중치를 가지는지의 여부로 나뉩니다.

 

비가중 그래프

   A-----B
   |     |
   |     |
   C-----D

• 가중치가 없거나 필요하지 않은 경우에 사용됩니다.

 

가중 그래프

   A--5--B
   |     |
   3     2
   |     |
   C--1--D

• 간선에 가중치를 가지는 그래프입니다.
• 간선의 가중치는 다양한 것을 나타낼 수 있습니다. (비용, 거리 등)

 

비순환 그래프 vs 순환 그래프

• 그래프 내에 사이클이 존재하는지의 여부에 따라 나뉩니다.

 

비순환 그래프

   A---->B---->C
   |
   v
   D

• 그래프 내에 어떠한 사이클도 포함되지 않는 그래프

 

순환 그래프

   A---->B---->C
   ^           |
   |           v
   D<----------E

• 그래프 내에 하나 이상의 사이클이 존재하는 그래프
• 소셜 네트워크, 통신 네트워크

 

3. 표현

인접 행렬

A-----B
|     |
|     |
D-----C

	A	B	C	D
A	0	1	0	1
B	1	0	1	0
C	0	1	0	1
D	1	0	1	0

• 정점들간의 연결 관계를 2차원 배열로 표현하는 방식입니다.
• 정접 i와 j가 연결되어 있으면 1, 그렇지 않으면 0으로 표기합니다.

 

장점

• 간선의 존재 여부를 빠르게 파악할 수 있습니다.
• 구현이 간단합니다.
• 밀집 그래프일 경우, 효율적인 메모리 사용이 가능합니다.

 

단점

• 항상 $V^2$의 공간을 필요로 합니다.
• 희소 그래프일 경우, 메모리 낭비가 심하게 발생할 수 있습니다.

 

코드

public class UDGWithMatrix {
    private final int vCnt;
    private BitSet[] adjacency;
        
    UDGWithMatrix(int size) {
        this.size = size;

        for (int i = 0; i < size; i++) this.adjacency[i] = new BitSet(size);
    }

    public void addEdge(int src, int dest) {
        adjacency[src].set(dest);
        adjacency[dest].set(src);
    }

    public boolean hasEdge(int src, int dest) {
        return adjacency[src].get(dest);
    }

    public void removeEdge(int src, int dest) {
        adjacency[src].clear(dest);
        adjacency[dest].clear(src);
    }

    public int[] getAdjVertices(int v) {
        return IntStream.range(0, size).filter(i -> adjacency[v].get(i)).toArray();
    }

    public int getDegree(int v) {
        return adjacency[v].cardinality();
    }
}

 

인접 리스트

• 인접하고 있는 정점을 연결 리스트로 표현합니다.
• 인접 노드를 동적으로 추가하는 경우에 적절합니다.

 

장점

• 희소 그래프일 경우, 효율적인 메모리 사용에 적절합니다.

 

단점

• (비효율성) 특정 간선의 존재 여부
  • 두 정점 사이에 간선이 존재하는지 확인하기 위해, 정점의 인접 리스트를 전체 순회해야 합니다.
• (비효율성) 간선 삭제
  • 삭제하려는 간선을 찾기 위해 인접 리스트를 전체 순회해야 하며, 추가적인 연산이 요구됩니다.
  • 무방향 그래프일 경우, 두 정점의 인접리스트 모두에서 상대 정점을 찾아 삭제해야 합니다.

 

코드

public class UGWithLinkedList {
    private final Scanner sc;
    private final Node[] adjList;
    private final Queue<Integer> queue;
    private final BitSet visited;

    public static void main(String[] args) {
        UGWithLinkedList ugWithLinkedList = new UGWithLinkedList();
        ugWithLinkedList.bfs(0);
    }

    public UGWithLinkedList() {
        sc = new Scanner(System.in);
        adjList = init();
        queue = new ArrayDeque<>();
        visited = new BitSet();
    }

    public void bfs(int start) {
        queue.clear();
        visited.clear();

        queue.offer(start);
        visited.set(start);

        while (!queue.isEmpty()) {
            int val = queue.poll();

            System.out.println((char) (val + 65));

            for (Node cur = adjList[val]; cur != null; cur = cur.next) {
                if (visited.get(cur.val)) continue;

                visited.set(cur.val);
                queue.offer(cur.val);
            }
        }
    }

    private Node[] init() {
        int vCnt = sc.nextInt();
        int eCnt = sc.nextInt();

        Node[] adjList = new Node[vCnt];
        for (int i = 0; i < eCnt; i++) {
            int src = sc.nextInt();
            int dest = sc.nextInt();

            adjList[src] = new Node(dest, adjList[src]);
            adjList[dest] = new Node(src, adjList[dest]);
        }

        return adjList;
    }

    class Node {
        final int val;
        final Node next;

        public Node(int val, Node next) {
            this.val = val;
            this.next = next;
        }
    }
}

 

간선 리스트

• 그래프의 모든 간선을 리스트에 저장합니다.
• 각 간선은 시작 정점과 끝 정점의 쌍으로 표현됩니다.

 

장점

• 희소 그래프일 경우, 효율적인 메모리 사용에 적절합니다.
• 주로 최소 스패닝 트리를 구현하는데 쓰입니다.

 

단점

• (비효율성) 인접 정점 탐색: 특정 정점에 인접한 모든 간선을 찾으려면, 전체 간선 리스트를 순회해야 합니다.

 

코드

public class UGWithEdges {
    int vCnt;
    List<Edge> edges;

    public UGWithEdges(int vCnt) {
        this.vCnt = vCnt;
        edges = new ArrayList<>();
    }

    public void addEdge(int src, int dest) {
        if (hasEdge(src, dest)) return;

        edges.add(new Edge(src, dest));
    }

    public boolean hasEdge(int src, int dest) {
        return edges.stream()
                .anyMatch(e -> (e.src == src && e.dest == dest) || (e.src == dest && e.dest == src));
    }

    public List<Integer> getAdjVertices(int vertex) {
        return edges.stream()
                .filter(e -> e.isAdjVertex(vertex))
                .map(e -> e.getAdjVertex(vertex))
                .toList();
    }

    class Edge {
        final int src, dest;

        public Edge(int src, int dest) {
            this.src = src;
            this.dest = dest;
        }

        public boolean isAdjVertex(int vertex) {
            return src == vertex || dest == vertex;
        }

        public int getAdjVertex(int vertex) {
            return src == vertex ? dest : src;
        }
    }
}

 

 

출처

• Wiki - Graph