[graph] 인접 리스트로 무방향 그래프 구현하기

★ 정점의 개수 n개 ,  모서리의 개수 m개 ★

 

각 정점에 대한 인접 정점들을 연결 리스트로 만드는 것

리스트의 각 노드는 정점을 저장하는 필드와 다음 인접 정점을 연결하는 링크 필드로 구성된다.

어떤 정점의 연결 리스트는 그 정점에 인접한 정점의 수(= 정점의 차수)만큼 노드가 연결되어 있다.

 

예시 무방향 그래프

인접 리스트로 표현

정점 i의 차수 = i에 연결되어 있는 노드 수

ex) 정점 2의 차수 = 3

 

---

JAVA  자료구조 구현 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.Comparator;
import java.util.StringTokenizer;

class Node {
    int vertex; //현재 정점
    Node link; //다음 연결되어 있는 정점
}

class graphList {
    private Node head[]; //정점의 리스트
    private int v; //현재 정점의 개수(=정점 중 가장 큰 수)
    public graphList(int n) {
        //정점은 1부터 시작한다.
        head = new Node[n+1];
        v = n;
    }
    public void insertEdge(int v1, int v2) {
        if(v1 > v || v1 < 1 || v2 > v || v2 < 1){
            System.out.println("없는 정점입니다.");
        }
        else { //v1 -> v2
            Node gNode = new Node();
            gNode.vertex = v2;
            gNode.link = head[v1];
            head[v1] = gNode;
        }
    }
    public void printGraph() {
        Node gNode = new Node();
        for(int i = 1; i <= v; i++) {
            System.out.printf("\n정점 %d의 인접 리스트 ", i);
            gNode = head[i];
            while(gNode != null) {
                System.out.printf("-> %d", gNode.vertex);
                gNode = gNode.link;
            }
        }
    }
}

public class graph_link {
    public static void main(String[] args) throws IOException {
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));

        int N = Integer.parseInt(bf.readLine()); //정점의 수
        int M = Integer.parseInt(bf.readLine()); //간선의 수

        graphList g = new graphList(N);
        StringTokenizer st;
        int tmp[][] = new int[M*2][2];
        for(int i = 0; i < M*2; i += 2){
            st = new StringTokenizer(bf.readLine());
            int x = Integer.parseInt(st.nextToken());
            int y = Integer.parseInt(st.nextToken());
            //후에 정렬을 위해 임시 저장
            //무방향 그래프 이므로 양쪽 방향 저장
            tmp[i][0] = x;
            tmp[i][1] = y;
            tmp[i+1][0] = y;
            tmp[i+1][1] = x;
        }
        //인접 리스트를 오름차순으로 표현하기 위해
        //입력시 v2(=tmp[][1])를 내림차순으로 정렬한다.
        Arrays.sort(tmp, new Comparator<int[]>() {
            @Override
            public int compare(int[] o1, int[] o2) {
                if(o1[0] == o2[0]){
                    return o2[1] - o1[1]; //내림차순 정렬
                }
                else {
                    return o1[0] - o2[0];
                }
            }
        });
        for(int i = 0; i < M*2; i++) {
            g.insertEdge(tmp[i][0],tmp[i][1]);
        }
        g.printGraph();
    }
}

입력

출력

---

n개의 정점과 m개의 간선을 가진 무방향 그래프는

크기가 n인 head 배열과 2m개의 노드가 필요하다.

 

---

ArrayList로 구현한 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Comparator;
import java.util.StringTokenizer;

public class graph_array {
    public static void main(String[] args) throws IOException {
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));

        int N = Integer.parseInt(bf.readLine()); //정점의 수
        int M = Integer.parseInt(bf.readLine()); //간선의 수

        ArrayList<ArrayList<Integer>> graph = new ArrayList<>();
        for(int i = 0; i <= N; i++) { //정점의 수 만큼 리스트 생성해준다. - 0번은 사용 안함
            graph.add(new ArrayList<>());
        }
        StringTokenizer st;
        for(int i = 0; i < M; i++){
            st = new StringTokenizer(bf.readLine());
            int x = Integer.parseInt(st.nextToken());
            int y = Integer.parseInt(st.nextToken());
            graph.get(x).add(y);
            graph.get(y).add(x);
        }

        for(int i = 1; i <= N; i++){
            graph.get(i).sort(Comparator.naturalOrder()); //오름차순 정렬
            System.out.println("정점"+i+" : "+graph.get(i).toString());
        }
    }
}

결과

장점	간선이 희소한 그래프를 효율적으로 표현할 수 있다. 포인터를 사용할 줄 알면 까다롭지 않게 사용할 수 있다.
단점	어떤 간선이 그래프에 포함되어 있는지 확인하기 어렵다. 즉, 리스트를 전체 탐색하며 찾아야 한다.