그래프 (Graph)

출처 : https://gamedevlog.tistory.com/15

 

개체 간의 관계를 표현하는 자료 구조

 

• 무방향 그래프 (Undirected Graph)
  간선(Edge)이 방향을 가지지 않는 그래프
  간선은 두 노드 사이의 연결을 나타냅

package datastructure.nonlinear;

import java.util.*;

class UndirectedGraphTest {
    private int V; // 노드 수
    private LinkedList<Integer> adjacencyList[]; // 인접 리스트

    UndirectedGraphTest(int v) {
        V = v;
        adjacencyList = new LinkedList[v];
        for (int i = 0; i < v; ++i)
            adjacencyList[i] = new LinkedList<>();
    }

    // 노드와 연결된 간선 추가
    void addEdge(int v, int w) {
        adjacencyList[v].add(w);
        adjacencyList[w].add(v);
    }

    // 무방향 그래프 순회
    void traverse(int v) {
        for (Integer node : adjacencyList[v]) {
            System.out.print(node + " ");
        }
    }
}

 

• 방향 그래프 (Directed Graph)
  간선이 방향을 가지며 한 노드에서 다른 노드로 이동하는 방향이 정해진 그래프

package datastructure.nonlinear;

import java.util.*;

class DirectedGraphTest {
    private int V; // 노드 수
    private LinkedList<Integer> adjacencyList[]; // 인접 리스트

    DirectedGraphTest(int v) {
        V = v;
        adjacencyList = new LinkedList[v];
        for (int i = 0; i < v; ++i)
            adjacencyList[i] = new LinkedList<>();
    }

    // 방향 그래프에서 간선 추가
    void addEdge(int v, int w) {
        adjacencyList[v].add(w);
    }

    // 방향 그래프 순회
    void traverse(int v) {
        for (Integer node : adjacencyList[v]) {
            System.out.print(node + " ");
        }
    }
}