10.3.1 그래프 구현 [디딤돌 자료구조와 알고리즘 with C++]

10.3.1 그래프 구현

깊이 우선 탐색(인접행렬).zip

그래프는 방향성 없는 그래프와 방향성 있는 그래프가 있습니다. 먼저 방향성 없는 그래프를 살펴보아요.

 

방향성 없는 그래프는 정점 A에서 정점 B로 이동할 수 있으면 언제나 정정 B에서 정정 B로 이동할 수 있음을 보장하는 그래프예요.

 

방향성 없는 그래프를 표현하는 방법 중에 간단한 그래프에는 인접 행렬을 많이 사용해요. 인접 행렬로 방향성 없는 그래프를 표현하면 좌상단에서 우하단으로 이어지는 대각선에 대칭 형태죠.

 

 

먼저 그래프 형식을 정의하기로 해요. 인접 행렬로 그래프를 표현할 때 그래프에는 정점 개수와 인접 행렬이 필요하겠죠.

 

이제 방향성 없는 그래프를 구현해 봅시다.

 

정점을 보관하는 벡터를 이웃이라고 정합시다.

typedef vector<int> Neighbors;

class Graph

{

정점의 개수와 인접행렬이 필요하겠죠. 인접행렬은 정점의 개수에 맞게 동적으로 생성합시다. 행과 열이 있어야 하기 때문에 int ** 형식으로 정의하세요.

    const int vn;//정점의 개수

    int **matrix;//인접 행렬   

public:

생성자에서는 정점 개수를 인자로 받습니다.

    Graph(int vn);

동적으로 생성한 행렬 매트릭스를 해제하기 위해 소멸자를 제공하세요.

    ~Graph(void);

두 정점 사이에 간선을 추가하는 메서드를 제공하세요.

    void AddEdge(int start, int goal);//간선 추가

모든 정점에서 이웃하는 정점 목록을 출력하는 메서드를 제공하세요.

    void ViewNeighbors()const;

특정 정점에서 이웃하는 이웃을 출력하는 메서드도 제공합시다.

    void ViewNeighbor(int vt)const;

특정 정점에서 이웃하는 정점 목록을 구하는 메서드도 제공합시다.

    Neighbors FindNeighbors(int vt);

};

 

그래프 생성자를 구현합시다. 입력 인자로 받은 정점 개수로 상수 vn을 초기화하세요.

Graph::Graph(int vn):vn(vn)

{

정점 개수의 행을 보관하는 메모리를 매트릭스에 할당하세요.

    matrix = new int *[vn];//매트릭스 메모리 할당

     for (int i = 0; i < vn; i++)

     {

매트릭스의 각 행에 vn개의 컬럼 메모리를 할당하고 메모리를 초기화하세요.

         matrix[i] = new int[vn];//매트릭스 [i-row] 메모리 할당

할당한 메모리를 초기화합니다.

         memset(matrix[i], 0, sizeof(int)*vn);//메모리 0으로 초기화

     }

}

 

소멸자에서는 동적으로 할당한 매트릭스를 소멸합니다.

Graph::~Graph(void)

{

    for (int i = 0; i < vn; i++)

    {

        delete[] matrix[i];//매트릭스 [i-row]  메모리 소멸

    }

    delete[] matrix;//매트릭스 메모리 해제

     

}

 

간선 추가하는 메서드에서는 start행에서 goal 열과 goal행 start열을 1로 설정하세요. 만약 방향성 있는 그래프일 때는 둘 중 하나만 1로 설정합니다.

void Graph::AddEdge(int start, int goal)//간선 추가

{

    matrix[start][goal] = 1;//간선 설정

    matrix[goal][start] = 1;//간선 설정

}

 

 

 

모든 정점의 이웃하는 정점을 출력하는 메서드를 구현합시다.

void Graph::ViewNeighbors()const

{

    cout<<"=== 이웃 정점 ==="<<endl;

반복해서 특정 정점의 이웃을 출력하는 메서드를 호출하세요.

    for (int i = 0; i < vn; i++)

    {

        cout<<i<<"의 이웃: ";

        ViewNeighbor(i);//i정점의 이웃 보여주기

    }

    cout<<endl;

}

 

특정 정점의 이웃하는 정점을 출력하는 메서드를 구현합시다.

void Graph::ViewNeighbor(int vt)const

{

    for (int i = 0; i < vn; i++)

    {

특정 정점으로 가는 간선이 있으면 이웃 정보를 출력하세요.

        if(matrix[vt][i])

        {

            cout<<i<<" ";

        }

    }

    cout<<endl;

}

 

같은 원리로 이웃하는 정점을 반환하는 메서드를 구현하세요.

Neighbors Graph::FindNeighbors(int vt)

{

    Neighbors neighbors;

    for (int i = 0; i < vn; i++)

     {

         if(matrix[vt][i])

         {

콘솔에 출력하는 대신 neighbors에 추가합니다.

             neighbors.push_back(i);

         }

     }

    return neighbors;

}

 

 

이제 그래프를 테스트하는 코드를 작성합시다.

int main()

{

    Graph *graph = new Graph(9);//그래프 동적 생성

     graph->AddEdge(0, 1);//간선 추가

     graph->AddEdge(0, 2);//간선 추가

     graph->AddEdge(1, 2);//간선 추가

     graph->AddEdge(1, 3);//간선 추가

     graph->AddEdge(2, 4);//간선 추가

     graph->AddEdge(3, 6);//간선 추가

     graph->AddEdge(4, 5);//간선 추가

     graph->AddEdge(4, 6);//간선 추가

     graph->AddEdge(4, 7);//간선 추가

     graph->AddEdge(6, 8);//간선 추가

     graph->ViewNeighbors();

     delete graph;

     return 0;

}

▷ 실행 결과

=== 이웃 정점 ===

0의 이웃: 1 2

1의 이웃: 0 2 3

2의 이웃: 0 1 4

3의 이웃: 1 6

4의 이웃: 2 5 6 7

5의 이웃: 4

6의 이웃: 3 4 8

7의 이웃: 4

8의 이웃: 6

 

만약 AddEdge에서 start에서 goal로 가는 행열만 1로 설정하면 방향성 있는 그래프입니다.

void Graph::AddEdge(int start, int goal)//간선 추가

{

    matrix[start][goal] = 1;//간선 설정

}

 

다음은 예제 코드에서 만든 그래프를 방향성 있는 그래프와 인접 행렬로 표시한 것입니다.

그리고 다음은 방향성 있는 그래프로 테스트 한 실행 결과입니다.

 

▷ 실행 결과

=== 이웃 정점 ===

0의 이웃: 1 2

1의 이웃: 2 3

2의 이웃: 4

3의 이웃: 6

4의 이웃: 5 6 7

5의 이웃:

6의 이웃: 8

7의 이웃:

8의 이웃:

 

참고로 그래프에서 자신에게 올 수 있는 이웃 정점의 수(간선의 수)를 진입 차수(In degree)라 부르고 자신에게서 갈 수 있는 이웃 정점의 수(간선의 수)를 진출 차수(Out degree)라고 부릅니다. 위 그래프에서 4의 집입 차수는 1(정점 2)이며 진출 차수는 3(정점 5, 정점 6, 정점 7)입니다.

10.3 인접 행렬을 이용한 깊이 우선 탐색

10.3.2 깊이 우선 탐색(인접 행렬) 구현

10.3.3 깊이 우선 탐색(인접 행렬) 코드