07. 그래프(Graph)

1. 그래프란?

규칙 정리)
1) 2개 이상의 경로가 가능하다.
2) 노드들 사이에 무방향/방향에서 양방향 경로를 가질 수 있다.
3) 루트 노드라는 개념이 없다. (= 루트노드는 트리)
4) 순회는 DFS나 BFS로 이루어진다.
5) 그래프는 순환(Cyclic) 혹은 비순환(Acyclic)이다.
6) 그래프는 크게 방향 그래프와 무방향 그래프가 있다.

 

 

2. 용어 정리

1) 정점(Vertex)

    - 노드(node) 라고도 하며 정점에는 데이터가 저장된다. (0, 1, 2, 3)

 

2) 간선(Edge) 

    - 정점(노드)를 연결하는 선으로 link, branch 라고도 부른다.

 

* 간선의 종류

📍 무방향 간선	방향 없음. A-B면 B-A도 가능	친구 관계
➡️ 방향 간선	방향 있음. A → B만 가능	팔로우 관계
🧮 가중치 간선	간선마다 "비용/시간/거리" 같은 값이 있음	네비게이션 도로 (A → B, 10km

 

 

3) 단순 경로(simple path)

    - 경로 중에서 반복되는 정점이 없는 경우. 한붓그리기와 같이 같은 간선을

       지나가지 않는 경로 ( 0->3->2->1 은 단순경로)

 

4) 차수(degree)

    - 무방향 그래프에서 하나의 정점에 인접한 정점의 수 (0의 차수는 3)

 

5) 경로 길이(path length)

    - 경로를 구성하는데 사용된 간선의 수

 

6) 사이클(cycle)

    - 단순 경로의 시작 정점과 종료 정점이 동일한 경우

 

 

3. 그래프 구현 방식 (2가지)

1) 인접 리스트 방식 [그나마 나음]

-> 각 노드 마다의 인접 정점을 리스트로 나열하여 구현

-> 그에 따른 각 리스트들을 배열로 저장하면 된다.

(*) 기본 생성 가이드

//총 인원
int N = 6
//0 ~ 6 인덱스 생성
List<Integer>[] graph = new ArrayList[N+1];
//1 ~ 6 리스트들 생성
for(int i=1; i<=N; i++){
	graph[i] = new ArrayList<>();
}
//노드 입력
for(int i=0; i<3; i++){
	int node = sc.nextInt();
    graph[node].add(1);
    graph[node].add(2);
    ...
}

 

(*) 정수형 무방향/정방향 그래프 생성 예제

public static void main(String[] args) {
		int size = 4;
		Map<Integer, List<Integer>> graph = new HashMap<>();
		
		createDirGraph(graph, 4);
		for(int key : graph.keySet()) {
			System.out.println("key : " + key + " -> " + graph.get(key));
		}
		
		
		
	}
	//무방향 정수 그래프
	public static void createNoDirGraph(Map<Integer, List<Integer>> graph, int size){
		for(int i=1; i<=size; i++){
			graph.put(i, new ArrayList<>());
		}
	}
	
	//정방향 정수 그래프
	public static void createDirGraph(Map<Integer, List<Integer>> graph, int size) {
		
		for (int i = 1; i <= size; i++) {
		    if (i + 1 <= size) {
		        graph.put(i, new ArrayList<>(Arrays.asList(i + 1)));
		    } 
		    else {
		        graph.put(i, new ArrayList<>());
		    }
		}
	}

 

(*) 격자형 2D 그래프 생성 예제

int[][] dirs = {{-1,0}, {1,0}, {0,-1}, {0,1}}; // 상하좌우
int rows = 3, cols = 3;

Map<String, List<String>> graph = new HashMap<>();

for (int r = 0; r < rows; r++) {
    for (int c = 0; c < cols; c++) {
        String curr = r + "," + c;
        graph.put(curr, new ArrayList<>());

        for (int[] d : dirs) {
            int nr = r + d[0], nc = c + d[1];
            if (nr >= 0 && nr < rows && nc >= 0 && nc < cols) {
                String next = nr + "," + nc;
                graph.get(curr).add(next);
            }
        }
    }
}

 

2) 인접 행렬 방식[어려움/나중에]