Graph (그래프)

그래프(Graph)는 정점(Vertex)과 간선(Edge)으로 구성된 자료 구조로, 여러 데이터 요소들 간의 연결 관계를 표현하는 데 매우 유용합니다. 이를 통해 연결된 데이터를 효율적으로 관리하거나 탐색할 수 있습니다. 그래프는 여러 분야에서 응용되며, 특히 네트워크, 지도, 소셜 미디어 등에서 흔히 사용됩니다.

1. 그래프의 기본 용어

• 정점(Vertex): 그래프에서 데이터를 담고 있는 개체입니다. 정점은 보통 노드(Node)라고도 부릅니다.
• 간선(Edge): 정점 간의 연결을 나타내는 선입니다. 간선은 방향이 있는지에 따라 유향 그래프(Directed Graph)와 무향 그래프(Undirected Graph)로 나뉩니다.
• 인접 리스트(Adjacency List): 정점마다 연결된 정점들을 리스트로 표현하는 방식입니다.
• 인접 행렬(Adjacency Matrix): 정점 간의 연결 관계를 2차원 배열로 표현하는 방식입니다.

2. 그래프의 종류

• 무향 그래프(Undirected Graph): 간선에 방향이 없으며, 양방향으로 연결된 그래프입니다.
• 유향 그래프(Directed Graph): 간선에 방향이 있어 한쪽 방향으로만 연결된 그래프입니다.
• 가중 그래프(Weighted Graph): 간선마다 가중치(비용 또는 거리)가 부여된 그래프입니다.
• 비가중 그래프(Unweighted Graph): 간선에 가중치가 없는 그래프입니다.

3. 그래프 구현

(1) 인접 리스트(Adjacency List) 방식

인접 리스트 방식은 각 정점마다 연결된 정점의 리스트를 저장합니다. 이 방식은 연결된 정점만 저장하기 때문에 메모리를 효율적으로 사용합니다.

import java.util.ArrayList;
import java.util.List;
//무향 그래프
public class Graph {
    private List<List<Integer>> adjList;
    
    public static void main(String[] args) {
        Graph graph = new Graph(5);  // 5개의 정점이 있는 그래프 생성
        graph.addEdge(0, 1);
        graph.addEdge(0, 4);
        graph.addEdge(1, 2);
        graph.addEdge(1, 3);
        graph.addEdge(1, 4);
        graph.addEdge(2, 3);
        graph.addEdge(3, 4);

        graph.printGraph();
    }

    // 그래프 생성자
    public Graph(int numVertices) {
        adjList = new ArrayList<>();
        for (int i = 0; i < numVertices; i++) {
            adjList.add(new ArrayList<>());
        }
    }

    // 간선 추가 (무향 그래프)
    public void addEdge(int u, int v) {
        adjList.get(u).add(v);
        adjList.get(v).add(u);  // 무향 그래프이므로 반대 방향도 추가
    }

    // 그래프 출력
    public void printGraph() {
        for (int i = 0; i < adjList.size(); i++) {
            System.out.print("Vertex " + i + ": ");
            for (int j : adjList.get(i)) {
                System.out.print(j + " ");
            }
            System.out.println();
        }
    }
}

 

(2) 인접 행렬(Adjacency Matrix) 방식

인접 행렬 방식은 2차원 배열을 사용하여 정점 간의 연결을 저장합니다. 인접 행렬 방식은 구현이 간단하지만, 연결되지 않은 간선도 모두 저장하므로 메모리 사용량이 더 많습니다.

//무향 그래프
public class Graph {
    private int[][] adjMatrix;
    private int numVertices;
    
    public static void main(String[] args) {
        Graph graph = new Graph(5);  // 5개의 정점이 있는 그래프 생성
        graph.addEdge(0, 1);
        graph.addEdge(0, 4);
        graph.addEdge(1, 2);
        graph.addEdge(1, 3);
        graph.addEdge(1, 4);
        graph.addEdge(2, 3);
        graph.addEdge(3, 4);

        graph.printGraph();
    }

    // 그래프 생성자
    public Graph(int numVertices) {
        this.numVertices = numVertices;
        adjMatrix = new int[numVertices][numVertices];
    }

    // 간선 추가 (무향 그래프)
    public void addEdge(int u, int v) {
        adjMatrix[u][v] = 1;
        adjMatrix[v][u] = 1;  // 무향 그래프이므로 반대 방향도 추가
    }

    // 그래프 출력
    public void printGraph() {
        for (int i = 0; i < numVertices; i++) {
            for (int j = 0; j < numVertices; j++) {
                System.out.print(adjMatrix[i][j] + " ");
            }
            System.out.println();
        }
    }
}