[멋사 알고리즘 스터디] 23.08.03 - 그래프

📈그래프

연결되어 있는 객체 간의 관계를 표현하는 자료구조

그래프 G는 (V,E)로 표시

• V(vertex) : 정점
  • 여러 가지 특성을 가질 수 있는 객체 의미
  • V(G) : 그래프 G의 정점들의 집합
  • 노드(node)라고도 불림
• E(edge) : 간선
  • 정점들 간의 관계 의미
  • E(G) : 그래프 G의 간선들의 집합
  • 링크(link)라고도 불림

👓종류

1. 무방향 그래프
   두 정점을 연결하는 간선에 방향이 없는 그래프S

   
   V(G) = {A,B,C}
   E(G) = {(A,B), (A,C), (B,C)}

2. 방향 그래프
   간선에 방향이 있는 그래프

   
   V(G) = {A,B,C}
   E(G) = {<A,B>, <A,C>, <B,A>, <B,C>}

3. 완전 그래프

   	연결 그래프 : 서로 다른 모든 쌍의 정점들 사이에 경로가 있는 그래프

   연결 그래프 중 각 정점에서 다른 모든 정점이 연결된, 최대로 많은 간선 수를 가진 그래프
   정점이 n개인 무방향 그래프에서 최대 간선 수 : n(n-1)/2
   방향 그래프에서 최대 간선 수 : n(n-1)

   
   정점이 4개인 무방향 그래프 -> 6개 간선 필요
   
   정점이 4개인 방향 그래프 -> 12개 간선 필요

4. 부분 그래프
   원래 그래프에서 정점이나 간선을 일부만 제외하여 만든 그래프

5. 가중치 그래프 (=네트워크)
   정점을 연결하는 간선에 가중치를 할당한 그래프

🕶️용어

인접 : 두 정점을 연결하는 간선이 있으면 서로 인접하다고 한다.
부속 : 인접한 두 정점 사이의 간선은 두 정점에 부속되었다고 한다.
차수 : 정점에 부속되어 있는 간선의 수
	방향 그래프의 차수
    	* 진입 차수 : 외부에서 오는 간선의 수
		* 진출 차수 : 외부로 향하는 간선의 수
경로 : 그래프에서 간선을 따라 갈 수 있는 길을 순서대로 나열한 것
	* 경로 길이 : 경로를 구성하는 간선의 수
    * 단순 경로 : 경로 중에서 반복되는 간선이 없는 경로
    * 사이클 : 단순 경로의 시작 정점과 종료 정점이 동일한 경로

🔖표현 방법

1. 인접행렬 방법

행렬에 대한 2차원 배열을 사용하는 순차 자료구조 방법
그래프의 두 정점을 연결한 간선의 유무를 행렬로 저장
간선 (i,j)가 그래프에 존재한다면 M[i][j]=1 그렇지 않으면 0

• 무방향 그래프

  행 i의 합 = 열 i의 합 = 정점 i의 차수 (A의 차수 = 1+1 = 2개)

  

• 방향 그래프

  행 i의 합 = 정점 i의 진출차수
  열 i의 합 = 정점 i의 진입차수

  

2. 인접 리스트

각 정점에 인접한 정점들을 연결리스트로 표현
각 정점의 차수만큼 노드를 연결

인접 리스트의 각 노드
-정점 필드와 링크 필드로 구성
-헤드포인터는 정점 개수만큼 필요
-그래프는 정점의 집합이므로 각 정점에 대한 헤드 포인터를 그룹으로 묶어서 포인터 배열로 구성

• 무방향 그래프

  	헤드 노드 배열의 크기 : n
  	연결하는 노드의 수 : 2e
  	각 정점 헤드에 연결된 노드의 수 : 정점의 차수

• 방향 그래프

  	헤드 노드 배열의 크기 : n
  	연결하는 노드의 수 : e
  	각 정점 헤드에 연결된 노드의 수 : 정점의 진출 차수

🔎그래프 탐색

하나의 정점으로부터 시작하여 차례대로 모든 정점들을 한번씩 방문
많은 문제들이 단순히 그래프의 노드를 탐색하는 것으로 해결
ex) 도로망에서 특정 도시에서 다른 도시로 갈 수 있는지 여부
ex) 전자회로에서 특정 단자와 다른 단자가 서로 연결되어 있는지 여부

1. 깊이 우선 탐색 (DFS : Depth First Search)

한 방향으로 갈 수 있을 때까지 가다가 더 이상 갈 수 없게 되면 가장 가까운 갈림길로 돌아와서 이 곳으로부터 다른 방향으로 다시 탐색 진행
되돌아가기 위해서는 스택 필요 (순환 함수 호출로 묵시적인 스택 이용 가능)

1. 정점 0을 시작 정점으로 DFS 시작 -> 1
2. 정점 1을 시작 정점으로 DFS 시작 -> 2
3. 정점 2을 시작 정점으로 DFS 시작 -> 3
4. 정점 3을 시작 정점으로 DFS 시작 -> 4
5. 정점 4을 시작 정점으로 DFS 시작하지만 0,3,2가 모두 방문한 정점이라서 노드 3으로 돌아간다. (backtracking)
6. 정점 3에서도 더 이상 방문할 정점이 없어서 점점 순환 호출을 돌아간다.
7. 정점 2,1에서도 순환 호출을 되돌아간다.
8. 정점 0에서 더 이상 방문할 정점이 없어 탐색 종료

c언어로 작성한 DFS 함수

//인접 행렬로 표현된 그래프에 대한 깊이 우선 탐색
void dfs_mat(GraphType * g, int v){
	int w;
    visited[v] = TRUE; //정점 v의 방문 표시
    printf("정점 %d -> ", v); //방문한 정점 출력
    for (w=0; w<g->n; w++){ //인접 정점 탐색
    	if (g->adj_mat[v][w] && !visited[w])
        	dfs_mat(g,w); //정점 w에서 DFS 시작
}

int visited[MAX_VERTICES];
//인접 리스트로 표현된 그래프에 대한 깊이 우선 탐색
void dfs_list(GraphType * g, int v){
	GraphNode* w;
    visited[v] = TRUE; //정점 v의 방문 표시
    printf("정점 %d -> ", v); //방문한 정점 출력
    for (w=0; w<g->n; w++){ //인접 정점 탐색
    	if (g->adj_mat[v][w] && !visited[w])
        	dfs_mat(g,w); //정점 w에서 DFS 새로 시작
}

---

2. 너비 우선 탐색 (BFS : Breath First Search)

시작 정점으로부터 가까운 정점을 먼저 방문하고 멀리 떨어져 있는 정점을 나중에 방문하는 순회 방법
큐를 사용하여 구현됨

1. 처음에는 시작 정점인 A를 큐에 추가한다. (A)
2. 큐에서 A를 꺼내서 방문하고 A의 인접 정점들을 큐에 추가한다. (C, E)
3. 큐에서 C를 꺼내서 방문하고 C의 인접 정점들을 큐에 추가한다. (E, B, D, F)
4. 큐에서 E를 꺼내서 방문하고 인접 정점인 F는 이미 큐에 들어 있으므로 추가하지 않는다. (B, D, F)
5. 남은 정점들이 모두 큐에 들어있는 상태이기에 큐에서 B, D, F 차례대로 꺼내서 방문한다.

C언어로 작성한 BFS 함수

//인접 행렬로 표현된 그래프에 대한 넓이 우선 탐색
void bfs_mat(GraphType *g, int v){
	int w;
    QueueType q;
    
    queue_init(&q); //큐 초기화
    visited[v] = TRUE; //정점 v 방문 표시
    printf("%d 방문 ->",v);
    enqueue(&q, v) //시작 정점을 큐에 저장
    while (!is_empty(&q)){
    	v= dequeue(&q); //큐에 정점 추출
        for (w=0; w<g->n; w++){ //인접 정점 탐색
        	if (g->adj_mat[v][w] && !visited[w]){
            	visited[w]=TRUE; // 방문 표시
                printf("%d 방문 ->", w);
                enqueue(&q, w); //방문한 정점을 큐에 저장
            }
        }
    }
}

//인접 리스트로 표현된 그래프에 대한 넓이 우선 탐색
void bfs_list(GraphType *g, int v){
	GraphNode* w;
    QueueType q;
    
    init(&q); //큐 초기화
    visited[v] = TRUE; //정점 v 방문 표시
    printf("%d 방문 ->",v);
    enqueue(&q, v) //시작 정점을 큐에 저장
    while (!is_empty(&q)){
    	v= dequeue(&q); //큐에 지정된 정점 선택
        for (w=g->adj_list[v]; w; w=w->link){ //인접 정점 탐색
        	if (!visited[w->vertex]){ //미방문 정점 탐색
            	visited[w->vertex]=TRUE; // 방문 표시
                printf("%d 방문 ->", w->vertex);
                enqueue(&q, w->vertex); //정점을 큐에 저장
            }
        }
    }
}