[자료구조] 인접 행렬로 구현한 그래프

정점간의 관계를 인접행렬을 통해 나타낸다.

인접행렬은 2차원 배열을 통해 구현할 수 있다.

#pragma once
#include <iostream>
#define MAX_VTXS 100
 
class AdjMatGraph {
protected:
    int size;
    char vertices[MAX_VTXS]; // 정점을 배열로 표현
    int adj[MAX_VTXS][MAX_VTXS]; // 연결성을 나타내는 인접행렬을 
                                 // 2차원 배열로 표현
 
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);
            // 인접행렬을 모두 0으로 초기화
        }
    }
 
    void insertVertex(char name) { // 정점 삽입
        if (!isFull()) vertices[size++] = name;
        else printf(" 그래프 정점 개수 초과\n");
    }
 
    void insertEdge(int i, int j) { // 간선 삽입
        setEdge(i, j, 1);
        setEdge(j, i, 1);
        // 위의 코드는 무방향 그래프인 경우임.
        // i에서 j로, j에서 i로 모두 연결
        // 
        // 방향 그래프의 경우에는 두 라인 중에 하나만 작성해야됨.
        // i에서 j로의 방향 or j에서 i로의 방향
    }
 
    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));
            printf("\n");
        }
    }
};