[Java] 그래프 표현하기 - 인접 리스트

※ 본문은 혼자 공부한 내용을 기록한 글입니다. 오개념이 있다면 반드시 댓글로 알려주세요!

 

[ 1 ] 그래프

그래프란 연결되어 있는 원소간의 관계를 표현하는 자료구조이다. 그래프는 연결할 객체를 나타내는 정점(Vertex)과 정점들을 연결하는 간선(Edge)의 집합으로 구성된다. 그래프는 다음과 같이 정의할 수 있다.

G = (V, E)

 

 

---

[ 2 ] 인접 리스트로 그래프 표현하기

Java로 그래프를 표현하는 방법에는 대표적으로 세 가지가 있다. 첫 번째는 정수 배열 기반으로 에지 리스트를 나타낼 수 있고, 두 번째로는 2차원 배열을 기반으로 인접 행렬을 나타낼 수도 있다. 

 

주로 사용되는 방법은 ArrayList를 이용해 인접 리스트로 그래프를 표현하는 방법이다.

 

 

(1) 가중치가 없는 무방향 그래프

(단, n은 정점의 개수이며 1~n의 정점이 존재하고, m은 간선의 개수라고 가정하자. s와 e는 간선으로 연결될 정점들이다)

public class Main {

    static ArrayList<Integer>[] graph;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        int n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());

        graph = new ArrayList[n + 1];
        for(int i = 1; i < n+1; i++) {
            graph[i] = new ArrayList<>();
        }

        for(int i = 0; i < m; i++) {
            st = new StringTokenizer(br.readLine());
            int s = Integer.parseInt(st.nextToken());
            int e = Integer.parseInt(st.nextToken());
            graph[s].add(e);
            graph[e].add(s);
        }
        
    }
    
}

무방향 그래프이기 때문에 graph[s].add(e), graph[e].add(s) 처럼 양방향 관계로 각 정점의 관계를 나타내야 한다.

 

 

(2) 가중치가 있는 방향 그래프

class Node {
	int num;
    int weight;
    
    Node(int num, int weight) {
    	this.num;
        this.weight;
    }
}

public class Main {

    static ArrayList<Node>[] graph;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        int n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());

        graph = new ArrayList[n + 1];
        for(int i = 1; i < n+1; i++) {
            graph[i] = new ArrayList<Node>();
        }

        for(int i = 0; i < m; i++) {
            st = new StringTokenizer(br.readLine());
            int s = Integer.parseInt(st.nextToken());
            int e = Integer.parseInt(st.nextToken());
            int w = Integer.parseInt(st.nextToken());
            graph[s].add(new Node(e, w));
        }
        
    }
    
}

무방향이며 가중치가 없는 그래프와 달리 방향 그래프이기에 s → e 방향으로만 정점 간의 관계를 나타내면 되고, 가중치를 저장해야 하기에 Node 클래스를 따로 정의해야 한다.

 

Node 클래스의 필드에는 간선이 가리키는 e 노드와 해당 간선의 가중치 w 가 있다.