11장 - 그래프

11.1 그래프란?

 

그래프란 데이터 (객체)들이 서로 복잡하게 연결되어 있는 관계를 표현하는 자료구조이다.

정점 (Vertex, or Node)와 간선 (Edge, or Link)의 집합으로 정의된다.

정점과 간선의 집합이 같으면 시각적으로 다른 그래프여도 같은 그래프라는 것을 유의하자.

 

그래프의 종류

무방향그래프, 방향그래프, 가중치 그래프, 부분 그래프

무방향 그래프는 방향 그래프로 매핑해서 표현한다.

가중치 그래프에 연결관계가 없다고 함부로 0을 쓰지 말자.

 

그래프의 용어

adjaent vertex, in-degree, out-degree

path : 간선을 따라 갈 수 있는 길, 정점의 나열로 표시된다.

경로의 길이 : 경로의 간선의 개수

단순경로 : 반복되는 간선이 없는 경로

사이클 : 단순 경로이며 시작 정점과 종료 정점이 같은 경로

연결그래프 : 모든 정점들 사이에 경로가 존재하는 그래프

트리 : 사이클이 없는 연결 그래프

완전그래프 : 모든 정점 간에 간선이 존재하는 그래프

희소 그래프 : 정점간 간선이 적게 존재하는 그래프

 

 

11.2 그래프의 표현

 

1.  인접 행렬 : 그래프를 행렬로 표현한다.

(adjacency matrix)

정접의 개수가 n개라면 n by n 행렬로 연결 관계를 표현한다.

m[i][j] : i -> j 로 가는 간선이 존재한다.

무방향 그래프라면 m[i][j] = m[j][i]이어야 한다. (transpose가 같아야 한다.)

 

n^2의 메모리 공간이 필요하고

인접 정점을 알아내기 위해선 O(n)

모든 연결관계를 알기 위해선 O(n^2)의 시간이 걸린다.

#include <iostream>
using namespace std;
const int MAX_VTXS = 256;

class AdjMatGraph{
protected:
   int   size;
   char  vertices[MAX_VTXS];
   int   adj[MAX_VTXS][MAX_VTXS];

public:

   AdjMatGraph(){reset();}

   char  getVetexName(int i)              {return vertices[i];}
   int   getEdge(int i, int j)            {return adj[i][j];}
   void  setEdge(int i, int j, int val)   {adj[i][j] = val;}

   bool isFull(){return size >= MAX_VTXS;}
   bool isEmpty(){return size == 0;}

   void reset(){
      size = 0;
      for(int i = 0; i < MAX_VTXS; i++)
         for(int j = 0; j <MAX_VTXS; j++)
            adj[i][j] = 0;
   }

   void insertVertex(char name){
      if(!isFull()) vertices[size++] = name;
      else
      {
         cout << "Error" << endl;
      }
   }

   void insertEdge(int i, int j){
      setEdge(i,j,1);
      setEdge(j,i,1);
   }

   void display(){
      cout << "정점들 : ";
      for(int i = 0; i < size; i++){
         cout << vertices[i] << " ";
      }

      cout << endl;
      cout << "Adjacency : " << endl;

      for(int i = 0; i < size; i++){
         for(int j = 0; j < size; j++){
            cout << adj[i][j] << " ";
         }
         cout << endl;
      }
   }
};

 

 

 

2. 인접 리스트 : 그래프를 연결 리스트로 표현한다.

(adjacency list)

각 정점에 인접한 정점들을 리스트로 표현한다.

adj[i] : i에 인접한 정점들을 담는 리스트의 헤드 포인터

 

인접리스트는 정점의 개수에 비해 간선의 개수가 적은 희소그래프 표현에 적합하다.

모든 연결관계를 알기 위해선 O(n+e)의 시간이 필요하다.

 

#include <iostream>
const int MAX_VTXS = 256;

class Node{
protected:
	int id;
    Node* link;
public:
    Node(int i, Node * l = nullptr):id(i), link(l){}
    ~Node{
    	if(link != nullptr) delete link;
    }
    int getId(){return id;}
    Node* getLink(){return link;}
    void setLink(Node* l){link = l;}
};

class AdjListGraph{
protected:
	int size;
    char vertices[MAX_VTXS];
    Node * adj[MAX_VTXS];
    
public:
	AdjListGraph(){reset();}

   char  getVetexName(int i)              {return vertices[i];}

   bool isFull(){return size >= MAX_VTXS;}
   bool isEmpty(){return size == 0;}

   void reset(){
      for(int i = 0; i < size; i++)
      	if(adj[i] != nullptr) delete adj[i];
      size = 0;
   }

   void insertVertex(char name){
      if(!isFull()){
      	vertices[size++] = name;
        adj[size++] = name;
      }
      else{
         cout << "Error" << endl;
      }
   }

   void insertEdge(int u, int v){
      adj[u] = new Node(v,adj[u]);//새로 들어온 노드가 헤드포인터가 된다.
      adj[v] = new Node(u,adj[v]);
      
   }

   void display(){
      cout << "정점들 : ";
      for(int i = 0; i < size; i++){
         cout << vertices[i] << " ";
      }

      cout << endl;
      cout << "Adjacency : " << endl;

      for(int i = 0; i < size; i++){
         for(Node * v = adj[i]; v != nullptr; v = v->getLink()){
            cout << getVertex(v->getId()) << " ";
         }
         cout << endl;
      }
   }
	
	
};

 

11.3 그래프의 탐색

 

그래프의 탐색이란 한 정점에서 시작해서 다른 정점들을 한번씩 방문하는 작업니다.

연결되어 있는지 파악하고 싶을 때나 미로찾기(dfs) 최단거리 구하기(bfs)등 많은 문제 해결에 이용된다.

dfs와 bfs모두 방문했다는 것을 표시할 배열이 필요하다.

 

1. 깊이우선탐색 (dfs)

한 방향으로 갈 수 있을 때까지 가다가 더이상 갈 수 없게 되면 다시 가장 가까운 갈림길로 돌아와서 다른 방향을 탐색한다. 스택이나 재귀를 이용해서 구현할 수 있다.

 

void dfs(int v){
		//정점 v를 방문했다 표시
        visited[v] = true;
        
        //정점 v에 대한 액션 (command 패턴을 적용할 수 있다.)
        std::cout << getVertex(v) << " ";
        
        //정점 v에 대한 연결리스트를 순회하면서
        for(Node * p = adj[v]; p != nullptr; p = p->getLink()){
        
        	//방문하지 않은 노드가 있다면
            if(!visited[p->getID()])
            	//재귀적으로 dfs -> 이진트리 순회의 post order와 비슷하다.
                dfs(p->getID());
        }
}

 

 

2. 너비우선탐색 (bfs)

시작 정점으로부터 가까운 정점을 먼저 방문하고, 멀리 떨어져 있는 정점을 나중에 방문하는 순회 방법이다.

큐를 사용해서 구현할 수 있다.

void bfs(int v){
        std::queue<int> q;
        
        //시작 정점을 큐에 삽입
        //큐에 삽입한다는 것은 방문함과 동시에 해당 노드에 대해 어떤 액션을 취하는 것.
        q.push(v);
        visited[v] = true;
        std::cout << getVertex(v) << " ";

        while(!q.empty()){
        	//큐에서 하나를 빼서 i에 저장
            int i = q.front();
            q.pop();
            
            //i에 인접한 정점들을 순회하면서
            for(Node * v = adj[i]; v != nullptr; v = v->getLink()){
                int id = v->getID();
                //인접 정점을 방문하지 않았다면
                if(!visited[id]){
                	//큐에 삽입
                    q.push(id);
                    visited[id] = true;
                    std::cout << getVertex(id) << " ";
                }
            }
        }
}

 

11.4 연결 성분

 

연결 성분이란 최대로 연결된 부분 그래프를 말한다. 연결 성분을 찾기 위해서 dfs나 bfs를 사용할 수 있다.

#pragma once
#include "SrchALGraph.hpp"

using namespace std;

class ConnectedComponentGraph : public SrchALGraph{
private:
    int label[MAX_VTXS];
public:
    void labelBFS(int v, int color){
        std::queue<int> q;
        q.push(v);
        visited[v] = true;
        label[v] = color;
        while(!q.empty()){
            int id = q.front();
            q.pop();
            for(Node * v = adj[id]; v != nullptr; v = v->getLink()){
                if(!visited[v->getID()]){
                    visited[v->getID()] = true;
                    label[v->getID()] = color;
                    q.push(v->getID());
                }
            }
        }
    }
    void findConnectedComponent(){
        int count = 0;
        for(int i = 0; i < size; i++){
            if(!visited[i])
                labelBFS(i,++count);
        }
        for(int i = 0; i < size; i++){
            std::cout << getVertex(i) << "  " << label[i] << std::endl;
        }
    }

};

 

 

11.5 신장 트리 ( Spanning Tree)

 

그래프 내의 모든 정점을 포함하는 트리이다. 네트워크 포스팅에서 브로드 캐스팅 부분에 나왔었다.

일단 신장 트리도 트리이므로 트리의 정의를 따른다.

트리는 모든 정점이 연결되어 있어야 하고 (연결 그래프) 사이클이 없어야 한다.

하나의 그래프에는 여러 개의 신장 트리를 만들 수 있다.

n개의 정점을 연결하기 위해 정확히 n-1개의 간선을 사용한다.

dfs나 bfs 같은 탐색을 이용하면 탐색은 모든 정점을 한번씩 방문하는 것이므로 신장 트리를 만든다고 생각할 수 있다.

마지막 장에서 최소 신장 트리로 자세히 살펴보자.

 

 

11.6 위상정렬

 

방향 그래프에서 간선 <u,v>가 있다면 "정점 u는 v을 선행한다"고 한다.

preceding을 번역한 것같은데 쉽게 말하면 u 다음 v로 요약할 수 있다.

정점들의 선행 순서를 위배하지 않으면서 모든 정점들을 나열하는 것을 방향그래프의 위상정렬이라고 한다.

 

1. 진입차수가 0인 정점을 선택한다.

2. 선택한 정점과 그 정점에 연결된 간선을 삭제한다.

3. 남은 정점들의 진입차수를 변경한다.

4. 모든 정점이 삭제되면 알고리즘이 종료된다.

 

정점이 삭제되는 순서가 위상 순서가 된다.

진입차수가 0인 정점이 존재하지 않으면 위상정렬이 불가능하다. 이것은 그래프에 사이클이 존재한다는 것이다.

정점 i의 진입차수를 저장하는 배열 inDeg[i]를 추가하자.

#pragma once
#include <iostream>
#include "AdjListGraph.hpp"
#include <stack>
using namespace std;

class TopoSortGraph : public AdjListGraph{

public:
    int inDeg[MAX_VTXS];

    void insertEdge(int u, int v){
        //방향 그래프이므로 간선을 하나만 넣는다!
        adj[u] = new Node(v,adj[u]);
    }

    void TopoSort(){
        //inDeg 배열은 전역이 아니므로 초기화가 필요하다.
        for(int i=0; i<size; i++){
            inDeg[i] = 0;
        }
        //초기화 후, 값을 넣어주자.
        for(int i=0; i<size; i++){
            Node * node = adj[i];
            while(node != nullptr){
                //i에서 연결된 정점들의 진입차수를 하나 올려준다.
                inDeg[node->getID()]++;
                //다음 노드로 슝
                node = node ->getLink();
            }
        }
        //진입 차수가 0인 정점들을 스택에 삽입
        std::stack<int> s;
        for(int i = 0; i < size; i++){
            if(!inDeg[i]) s.push(i);
        }

        //위상 순서 생성
        while(!s.empty()){
            int w = s.top();
            s.pop();
            cout << getVertex(w) << " ";
            // 주변 정점 간선 차수 변경
            Node * node = adj[w];
            while(node != nullptr){
                int u = node -> getID();
                inDeg[u]--;
                //뺐는데 0이면 s에 삽입
                if(!inDeg[u])
                    s.push(u);
                node = node -> getLink();
            }

        }
    }

};

슈도 코드에 int w = s.top();이라서 순간 헷갈렸다.

s.pop()잊지 말자...