그래프(Graph)

◼︎ 그래프 (Graph)

노드(Node) 또는 정점(Vertex)으로 이루어진 개체들이 간선(Edge)라고 하는 연결선으로 서로 연결된 추상 네트워크를 의미한다.

G = (V,E)

Vertex set (정점)
Edge set (엣지)

---

► 그래프 관련 용어

용어	설명
정점(Vertex)	노드(node) 라고도 하며 정점에는 데이터가 저장된다. (0, 1, 2, 3)
간선(Edge)	정점(노드)를 연결하는 선으로 link, branch 라고도 부른다.
인접 정점(adjacent Vertex)	간선에 의해 직접 연결된 정점 (0과 2은 인접정점)
단순 경로(simple path)	경로 중에서 반복되는 정점이 없는 경우. 한붓그리기와 같이 같은 간선을 지나가지 않는 경로 ( 0->3->2->1 은 단순경로 )
차수(degree)	무방향 그래프에서 하나의 정점에 인접한 정점의 수 (0의 차수는 3)
진출 차수(in-degree)	방향 그래프에서 외부로 향하는 간선의 수
진입 차수(out-degree)	방향 그래프에서 외부에서 들어오는 간선의 수
경로 길이(path length)	경로를 구성하는데 사용된 간선의 수
사이클(cycle)	단순 경로의 시작 정점과 종료 정점이 동일한 경우

---

그래프

Node, Edge

• Node (노드) = Vertex (정점)
• 6번 4번 노드를 연결하는 선을 Edge(간선)

인접성

‘엣지 (4,5) → 노드 4와 노드 5는 인접한다.’ 라고 표현한다.

경로(Path)

• 3 → 2 → 5
• 3 → 2 → 1 → 5
• 3 → 2 → 1 → 2 → 5는 경로라고 할 수 없다.

사이클(Cycle)

그래프에서 시작 정점과 끝 정점이 같은 경로를 의미한다. 다시 말해, 경로가 자기 자신으로 돌아오는 형태이다. 3 → 2 → 5 → 4 → 3은 경로를 형성한다고 말할 수 있다.

---

그래프 표현법

그래프를 표현하는 방법에는 주로 인접 행렬과 인접 리스트가 있다.

인접 행렬

2차원 배열을 사용하여 그래프의 연결 관계를 표현하는 방법이며, 각 정점 간의 연결 여부를 행렬로 나타낸다.

그래프의 모든 정점을 고려하므로 공간 복잡성이 높지만, 두 정점의 연결 여부를 알아내는 시간 복잡성은 낮다.

Example

예를 들어, 0, 1, 2, 3 총 4개의 노드를 가진 그래프가 있다고 가정하면, 인접 행렬은 다음과 같이 표현할 수 있다.

	0	1	2	3
0	0	1	0	1
1	1	0	1	1
2	0	1	0	0
3	1	1	0	0

행렬의 각 행과 열은 노드를 나타내며, 값 1은 두 노드가 연결되어 있음을, 값 0은 연결되어 있지 않음을 나타낸다. 예를 들어, [0][1]의 값이 1이므로 노드 0와 노드 1이 연결되어 있음을 의미한다.

자바 인접 행렬 예시

public class AdjacencyMatrix {
    private int[][] adjacencyMatrix;
    private int numVertices;

    public AdjacencyMatrix(int numVertices) {
        this.numVertices = numVertices;
        this.adjacencyMatrix = new int[numVertices][numVertices];
    }

    public void addEdge(int i, int j) {
        adjacencyMatrix[i][j] = 1;
        adjacencyMatrix[j][i] = 1;
    }

    public void removeEdge(int i, int j) {
        adjacencyMatrix[i][j] = 0;
        adjacencyMatrix[j][i] = 0;
    }

    public boolean isEdge(int i, int j) {
        return adjacencyMatrix[i][j] == 1;
    }

    public void printMatrix() {
        for (int i = 0; i < numVertices; i++) {
            for (int j = 0; j < numVertices; j++) {
                System.out.print(adjacencyMatrix[i][j] + " ");
            }
            System.out.println();
        }
    }
}

인접 리스트

각 정점에 연결된 정점들을 리스트로 표현하는 방법이다. 각 리스트는 해당 정점에 연결된 다른 정점들을 포함한다. 인접 리스트는 공간 복잡성이 낮지만, 두 정점이 연결되어 있는지 확인하는데 더 많은 시간이 걸린다.

예시

예를 들어, 0, 1, 2, 3 총 4개의 노드를 가진 그래프가 있다고 가정하면, 인접 리스트는 다음과 같이 표현할 수 있다.

0: 1->3
1: 0->2->3
2: 1
3: 0->1

각 행은 노드를 나타내며, 화살표 뒤의 숫자들은 해당 노드에 연결된 다른 노드들을 나타낸다. 예를 들어, 노드 0은 노드 1과 3에 연결되어 있으며, 노드 1은 노드 0, 2, 3에 연결되어 있다.

자바 인접 리스트 예시

import java.util.*;

public class AdjacencyList {
    private Map<Integer, List<Integer>> adjacencyList;

    public AdjacencyList(int numVertices) {
        adjacencyList = new HashMap<Integer, List<Integer>>();
        for (int i = 0; i < numVertices ; i++) {
            adjacencyList.put(i, new LinkedList<Integer>());
        }
    }

    public void addEdge(int src, int dest) {
        List<Integer> slist = adjacencyList.get(src);
        slist.add(dest);
        List<Integer> dlist = adjacencyList.get(dest);
        dlist.add(src);
    }

    public Iterable<Integer> getNeighbors(int v) {
        return adjacencyList.get(v);
    }

    public void printAdjacencyList() {
        for (int v = 0; v < adjacencyList.size(); v++) {
            System.out.print(v + ": ");
            for (int w : this.getNeighbors(v)) {
                System.out.print(w + " ");
            }
            System.out.println();
        }
    }
}

---

사용 상황

인접 행렬은 주로 두 노드 간의 연결 여부를 빠르게 확인해야 하는 경우나, 노드 간의 거리, 가중치를 저장해야 하는 경우에 사용된다.

반면, 인접 리스트는 공간 복잡도가 더 낮아 노드의 수가 많은 그래프에 효율적이다. 또한, 각 노드의 이웃 노드들을 빠르게 탐색해야 하는 경우에도 유용하다.

---