그래프

요소들이 서로 복잡하게 연결되어 있는 관계를 표현하는 자료구조.

정점(vertex)과 간선(edge)들의 집합으로 구성.

 

인접 정점(adjacent vertex)

;간선에 의해 직접 연결된 정점.

정점의 차수(degree)

;정점에 연결된 간선의 수.

경로(path)

;간선을 따라 갈 수 있는 길. 정점의 나열로 표시.

경로의 길이

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

단순 경로(simple path)

;경로 중에서 반복되는 간선이 없는 경로.

사이클(cycle)

;단순 경로의 시작 정점과 종료 정점이 같은 경로.

연결 그래프(connected graph)

;그래프의 모든 정점들 사이에 경로가 존재하는 것.

트리(Tree)

;그래프의 특수한 형태. 사이클을 가지지 않는 연결 그래프.

완전 그래프(complete graph)

;모든 정점 간에 간선이 존재하는 그래프.

 

#include <cstdio>
#define MAX_VTXS    256    // 표현 가능한 최대 정점의 개수
 
class AdjMatGraph
{
protected:
    int        size;                        // 정점의 개수
    char    vertices[MAX_VTXS];            // 정점의 이름
    int        adj[MAX_VTXS][MAX_VTXS];    // 인접 행렬
public:
    AdjMatGraph()
    {
        reset();
    }
    char getVertex(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 isEmpty()
    {
        return size == 0;
    }
    bool isFull()
    {
        return size >= MAX_VTXS;
    }
 
    // 그래프 초기화 -> 공백 상태의 그래프
    void reset()
    {
        size = 0;
        for (int i = 0; i < MAX_VTXS; i++)
        {
            for (int j = 0; j < MAX_VTXS; j++)
                setEdge(i, j, 0);
        }
    }
 
    // 정점 삽입 연산
    void insertVertex(char name)
    {
        if (!isFull())
            vertices[size++] = name;
        else
            printf("Error: 그래프 정점 개수 초과\n");
    }
 
    // 간선 삽입 연산: 무방향 그래프의 경우임.(방향, 가충치 그래프에서는 수정)
    void insertEdge(int u, int v)
    {
        setEdge(u, v, 1);
        setEdge(v, u, 1);    // 방향 그래프에서는 삭제됨(<u, v>만 존재)
    }
 
    // 그래프 정보를 출력함(화면이나 파일에 출력)
    void display(FILE* fp = stdout)
    {
        fprintf(fp, "%d\n", size);
        for (int i = 0; i < size; i++)
        {
            fprintf(fp, "%c ", getVertex(i));
            for (int j = 0; j < size; j++)
            {
                fprintf(fp, "%3d ", getEdge(i, j));
            }
            fprintf(fp, "\n");
        }
    }
 
    // 파일 입력 함수
    void load(char* filename)
    {
        FILE* fp = NULL;
        errno_t err;
        err = fopen_s(&fp, filename, "r");
        if (fp != NULL)
        {
            int n;
            fscanf_s(fp, "%d", MAX_VTXS, &n);    // 정점의 전체 개수
            for (int i = 0; i < n; i++)
            {
                char str[80];
                fscanf_s(fp, "%s", MAX_VTXS, str);    // 정점의 이름
                insertVertex(str[0]);    // 정점 삽입
                for (int j = 0; j < n; j++)
                {
                    int val;
                    fscanf_s(fp, "%d", MAX_VTXS, &val);    // 간선 정보
                    if (val != 0)            // 간선이 있으면
                        insertEdge(i, j);    // 간선 삽입
                }
            }
            fclose(fp);
        }
    }
 
    // 파일 저장 함수
    void store(char* filename)
    {
        FILE* fp = NULL;
        errno_t err;
        err = fopen_s(&fp, filename, "w");
        if (fp != NULL)
        {
            display(fp);
            fclose(fp);
        }
    }
};