[자료구조] 그래프 (Graph)

그래프

그래프는 객체 사이의 연결 관계를 표현할 수 있는 자료구조다.

 

---

 

📈 정의

그래프는 정점과 간선들의 유한 집합으로 G = (V, E)로 표시할 수 있다.

여기서 정점은 노드라고도 불리고, 간선은 링크라고도 불린다.

 

여러 그래프가 존재하지만 오늘은 인접 행렬 C++ 구현에 대해 집중적으로 다뤄보려고 한다.

 

---

구현 (C++)

• getVertex(int i)
• getEdge(int i, int j)
• setEdge(int i, int j, int val)
• insertVertex(char name)
• void insertEdge(int u, int v)
• void display()
• isEmpty()
• isFull()

 

---

 

클래스 생성

class AdjMatGraph
{
private:
    int size;                       // 정점의 개수
    char vertices[MAX_VTXS];        // 정점의 이름
    int adjMat[MAX_VTXS][MAX_VTXS]; // 인접 행렬

public:
    AdjMatGraph();
    char getVertex(int i);
    int getEdge(int i, int j);
    void setEdge(int i, int j, int val);
    void insertVertex(char name);
    void insertEdge(int u, int v);
    void display();
    bool isEmpty();
    bool isFull();
};

 

 

생성자 초기화

AdjMatGraph::AdjMatGraph()
{
    for (int i = 0; i < MAX_VTXS; i++)
    {
        for (int j = 0; j < MAX_VTXS; j++)
        {
            setEdge(i, j, 0);
        }
    }
    size = 0;
}

 

 

getVertex 함수

char AdjMatGraph::getVertex(int i)
{
    return vertices[i];
}

 

 

getEdge 함수

int AdjMatGraph::getEdge(int i, int j)
{
    return adjMat[i][j];
}

 

 

setEdge 함수

void AdjMatGraph::setEdge(int i, int j, int val)
{
    adjMat[i][j] = val;
}

 

 

insertVertex 함수

void AdjMatGraph::insertVertex(char name)
{
    if (isFull())
    {
        cout << "Graph vertex full error\n";
        return;
    }

    vertices[size++] = name;
}

 

 

insertEdge 함수

void AdjMatGraph::insertEdge(int u, int v)
{
    setEdge(u, v, 1); // 가중치 그래프에서는 1이 아닌 가중치 삽입
    setEdge(v, u, 1); // 방향 그래프에서는 삭제 (<u,v>만 존재)
}

 

 

display 함수

void AdjMatGraph::display()
{
    cout << "vertex size : " << size << "\n";
    cout << "    ";
    for (int i = 0; i < size; i++)
    {
        cout << getVertex(i) << " ";
    }
    cout << "\n";

    for (int i = 0; i < size; i++)
    {
        cout << getVertex(i) << " : ";
        for (int j = 0; j < size; j++)
        {
            cout << getEdge(i, j) << " ";
        }
        cout << "\n";
    }
}

 

 

isEmpty 함수

bool AdjMatGraph::isEmpty()
{
    return size == 0;
}

 

 

isFull 함수

bool AdjMatGraph::isFull()
{
    return size >= MAX_VTXS;
}

 

---

📌 전체 코드

#include <iostream>
using namespace std;

#define MAX_VTXS 256

class AdjMatGraph
{
private:
    int size;                       // 정점의 개수
    char vertices[MAX_VTXS];        // 정점의 이름
    int adjMat[MAX_VTXS][MAX_VTXS]; // 인접 행렬

public:
    AdjMatGraph();
    char getVertex(int i);
    int getEdge(int i, int j);
    void setEdge(int i, int j, int val);
    void insertVertex(char name);
    void insertEdge(int u, int v);
    void display();
    bool isEmpty();
    bool isFull();
};

AdjMatGraph::AdjMatGraph()
{
    for (int i = 0; i < MAX_VTXS; i++)
    {
        for (int j = 0; j < MAX_VTXS; j++)
        {
            setEdge(i, j, 0);
        }
    }
    size = 0;
}

char AdjMatGraph::getVertex(int i)
{
    return vertices[i];
}

int AdjMatGraph::getEdge(int i, int j)
{
    return adjMat[i][j];
}

void AdjMatGraph::setEdge(int i, int j, int val)
{
    adjMat[i][j] = val;
}

void AdjMatGraph::insertVertex(char name)
{
    if (isFull())
    {
        cout << "Graph vertex full error\n";
        return;
    }

    vertices[size++] = name;
}

void AdjMatGraph::insertEdge(int u, int v)
{
    setEdge(u, v, 1); // 가중치 그래프에서는 1이 아닌 가중치 삽입
    setEdge(v, u, 1); // 방향 그래프에서는 삭제 (<u,v>만 존재)
}

void AdjMatGraph::display()
{
    cout << "vertex size : " << size << "\n";
    cout << "    ";
    for (int i = 0; i < size; i++)
    {
        cout << getVertex(i) << " ";
    }
    cout << "\n";

    for (int i = 0; i < size; i++)
    {
        cout << getVertex(i) << " : ";
        for (int j = 0; j < size; j++)
        {
            cout << getEdge(i, j) << " ";
        }
        cout << "\n";
    }
}

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

int main()
{
    AdjMatGraph graph;

    // 정점 삽입 (A, B, C, D)
    graph.insertVertex('A'); // 0
    graph.insertVertex('B'); // 1
    graph.insertVertex('C'); // 2
    graph.insertVertex('D'); // 3

    // 간선 삽입
    graph.insertEdge(0, 1); // A->B
    graph.insertEdge(0, 2); // A->C
    graph.insertEdge(0, 3); // A->D
    graph.insertEdge(2, 3); // C->D

    graph.display();
}

 

 

 

참고 사이트

[자료구조] 그래프 (Graph) - 인접행렬 vs 인접리스트, DFS, BFS, Connected Component, Spanning Tree

 

 

좋아요는 로그인하지 않아도 누를 수 있습니다!