# 그래프

그래프 구현 방식 -> 인접 행렬, 인접 리스트

<figure><img src="https://3826875100-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2FOEGtw7tLJ7KClr0bS369%2Fuploads%2FqWU06wEZEB7rBzMHqbSS%2Fimage.png?alt=media&#x26;token=26025840-2ab8-4963-b1aa-2eb8c32d9cb7" alt=""><figcaption></figcaption></figure>

<figure><img src="https://3826875100-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2FOEGtw7tLJ7KClr0bS369%2Fuploads%2F5kHyZy13ieJmZC3eiGdx%2Fimage.png?alt=media&#x26;token=130b3995-72e1-44b5-90bf-bfba0bf8f3d3" alt=""><figcaption></figcaption></figure>

3번 정점과 연결되어 있는 정점을 확인한다?

3행 전부 살펴보면 된다.

<figure><img src="https://3826875100-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2FOEGtw7tLJ7KClr0bS369%2Fuploads%2F6aFE6SxkX6n1WoqUkivy%2Fimage.png?alt=media&#x26;token=148d73c3-4d9d-4ba7-b564-6f6ee7ee6fa9" alt=""><figcaption></figcaption></figure>

<figure><img src="https://3826875100-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2FOEGtw7tLJ7KClr0bS369%2Fuploads%2FDymaX2G1wdRjVvaJvR9o%2Fimage.png?alt=media&#x26;token=96b3688f-e9fb-4e53-8116-286390825859" alt=""><figcaption></figcaption></figure>

공간 복잡도 -> Vertex + Edge

* 인접리스트 기본 틀

```
1. 문제에서 주어진 정점, 간선 개수 받기
// int N = ...;
// int M = ...;

// 2. Map으로 그래프 자료구조 선언
Map<Integer, List<Integer>> graph = new HashMap<>();

// 3. 간선 정보 입력받아 그래프 만들기
for (int i = 0; i < M; i++) {
    int u = //u 입력
    int v = //v 입력
    
    // u -> v
    graph.computeIfAbsent(u, k-> new ArrayList<>()).add(v);
    // v -> u
    graph.computeIfAbsent(v, k-> new ArrayList<>()).add(u);
}
```

인접 행렬

1. 정점만 있는 경우

```java
public class GraphMatrix {
    private final int[][] adj;
    private final int size;
    
    public GraphMatrix(int size) {
        this.size = size;
        this.adj = new int[size][size];
    }
    
    public void addEdge(int from, int to) {
        adj[from][to] = 1; // 무방향이면 adj[to][from]도 1
    }
    
    public boolean hasEdge(int from,int to) {
        return adj[from][to] == 1;
    }
}
```

2. 가중치가 있는 경우

```java
public class WeightedGraphMatrix {
    private final int[][] adj;
    private final int size;
    private static final int INF = Integer.MAX_VALUE; 
    
    public WeightedGraphMatrix(int size) {
        this.size = size;
        this.adj = new int[size][size];
        
        for (int i = 0; i < size; i++) {
            for (int j = 0; j < size; j++) {
                adj[i][j] = INF;
            }
        }
    }
    
    public void addEdge(int from, int to, int weight) {
        adj[from][to] = weight;
    }
    
    public int getWeight(int from, int to) {
        return adj[from][to];
    }
}
```

인접 리스트

```javascript
public class GraphList {
    private final ArrayList<Integer>[] adj;
    
    public GraphList(int size) {
        for (int i = 0; i < size; i++) {
            adj.add(new ArrayList<>();
        }
    }
    
    public void addEdge(int from, int to) {
        add.get(from).add(to);
    }
    
    public List<Integer> getNeighbors(int vertex) {
        return adj.get(vertex);
    }
}
```

```java
import java.util.*;

public class WeightedGraphList {
    public static class Edge {
        int to, weight;
        public Edge(int to, int weight) {
            this.to = to;
            this.weight = weight;
        }
    }

    private final List<List<Edge>> adj;

    public WeightedGraphList(int size) {
        adj = new ArrayList<>();
        for (int i = 0; i < size; i++) {
            adj.add(new ArrayList<>());
        }
    }

    public void addEdge(int from, int to, int weight) {
        adj.get(from).add(new Edge(to, weight));
    }

    public List<Edge> getNeighbors(int vertex) {
        return adj.get(vertex);
    }
}

```

```java
class GraphListTraversal {
    private final List<List<Integer>> adj;
    private final int n;

    public GraphListTraversal(int n) {
        this.n = n;
        adj = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            adj.add(new ArrayList<>());
        }
    }

    public void addEdge(int u, int v) {
        adj.get(u).add(v);
        // adj.get(v).add(u);  // 무방향이라면
    }

    public void dfs(int start, boolean[] visited) {
        visited[start] = true;
        System.out.println("DFS visit: " + start);
        for (int neighbor : adj.get(start)) {
            if (!visited[neighbor]) {
                dfs(neighbor, visited);
            }
        }
    }

    public void bfs(int start) {
        boolean[] visited = new boolean[n];
        Queue<Integer> queue = new LinkedList<>();
        queue.add(start);
        visited[start] = true;

        while (!queue.isEmpty()) {
            int curr = queue.poll();
            System.out.println("BFS visit: " + curr);
            for (int neighbor : adj.get(curr)) {
                if (!visited[neighbor]) {
                    queue.add(neighbor);
                    visited[neighbor] = true;
                }
            }
        }
    }
}

```

가중치 포함

```java
void dfs(int current, boolean[] visited, int currentCost) {
    visited[current] = true;
    System.out.println("DFS visit: " + current + ", total cost: " + currentCost);

    for (Edge edge : adj.get(current)) {
        if (!visited[edge.to]) {
            dfs(edge.to, visited, currentCost + edge.weight);
        }
    }
}
class Node {
    int v, cost;
    Node(int v, int cost) {
        this.v = v;
        this.cost = cost;
    }
}

void bfs(int start) {
    boolean[] visited = new boolean[n];
    Queue<Node> queue = new LinkedList<>();
    queue.add(new Node(start, 0));
    visited[start] = true;

    while (!queue.isEmpty()) {
        Node curr = queue.poll();
        System.out.println("BFS visit: " + curr.v + ", total cost: " + curr.cost);

        for (Edge edge : adj.get(curr.v)) {
            if (!visited[edge.to]) {
                queue.add(new Node(edge.to, curr.cost + edge.weight));
                visited[edge.to] = true;
            }
        }
    }
}

```

가중치가 전부 동일한 경우에 한해, 그래프의 방향성 유무와 상관 없이 BFS를 통해 최단 거리를 구할 수 있다.
