C YC

IT Dev who working in Republic Of Korea

5 minute read

그래프(Graph)란?

그래프는 정점(Vertex) 또는 노드(Node)라고 불리는 객체들의 집합과 이들을 연결하는 간선(Edge)들의 집합으로 구성됩니다. 간선은 두 정점 사이의 관계를 나타냅니다.

  • 정점 (Vertex/Node): 데이터를 저장하는 객체입니다. 예를 들어, 도시, 사람, 웹 페이지 등이 정점이 될 수 있습니다.
  • 간선 (Edge): 두 정점 사이의 연결을 나타냅니다. 예를 들어, 도시 간의 도로, 사람 간의 친구 관계, 웹 페이지 간의 링크 등이 간선이 될 수 있습니다.



그래프(Graph)의 종류

  • 무방향 그래프 (Undirected Graph): 간선에 방향이 없는 그래프입니다. 즉, 두 정점 A와 B를 연결하는 간선이 있다면, A에서 B로 가는 것과 B에서 A로 가는 것이 동일합니다. 친구 관계, 도로망 등이 무방향 그래프의 예입니다.
  • 방향 그래프 (Directed Graph/Digraph): 간선에 방향이 있는 그래프입니다. 즉, A에서 B로 가는 간선과 B에서 A로 가는 간선은 서로 다른 간선입니다. 웹 페이지 링크, 지하철 노선도 등이 방향 그래프의 예입니다.
  • 가중 그래프 (Weighted Graph): 간선에 가중치(weight)가 할당된 그래프입니다. 가중치는 두 정점 사이의 연결 비용, 거리, 시간 등을 나타낼 수 있습니다. 도로망에서 도로의 길이, 통행료 등이 가중치의 예입니다.
  • 부분 그래프 (Subgraph): 주어진 그래프의 정점과 간선의 일부로 이루어진 그래프입니다.
  • 완전 그래프 (Complete Graph): 그래프의 모든 정점 쌍 사이에 간선이 존재하는 그래프입니다.
  • 연결 그래프 (Connected Graph): 무방향 그래프에서 모든 정점 쌍 사이에 경로가 존재하는 그래프입니다.
  • 비연결 그래프 (Disconnected Graph): 연결되지 않은 부분 그래프를 하나 이상 포함하는 그래프입니다.
  • 사이클 (Cycle): 시작 정점에서 시작하여 다른 정점들을 거쳐 다시 시작 정점으로 돌아오는 경로입니다.
  • 트리 (Tree): 사이클이 없는 연결 그래프입니다.



그래프의 표현 방식

  • 인접 행렬 (Adjacency Matrix): 정점의 개수를 N이라고 할 때, N x N 크기의 2차원 배열을 사용하여 그래프를 표현합니다. adj[i][j]는 정점 i와 정점 j 사이에 간선이 존재하는지 여부를 나타냅니다. 가중 그래프의 경우, adj[i][j]는 간선의 가중치를 저장합니다.
  • 인접 리스트 (Adjacency List): 각 정점에 대해 해당 정점과 인접한 정점들의 리스트를 저장하는 방식으로 그래프를 표현합니다. 각 정점은 인접한 정점들의 연결 리스트를 가집니다.



장단점

장점

  • 직관적인 정보 전달: 데이터를 시각적으로 표현함으로써 숫자나 텍스트로 표현된 것보다 훨씬 빠르고 쉽게 정보를 이해할 수 있도록 도와줍니다. 특히 데이터의 추세, 패턴, 관계 등을 명확하게 보여줍니다.
  • 데이터 비교 용이: 여러 데이터 항목 간의 크기, 비율, 변화 등을 쉽게 비교할 수 있습니다. 막대 그래프를 통해 각 항목의 크기를 비교하거나, 꺾은선 그래프를 통해 시간의 흐름에 따른 변화를 비교하는 것이 좋은 예입니다.
  • 패턴 및 추세 파악: 데이터의 패턴이나 추세를 시각적으로 명확하게 보여줍니다. 꺾은선 그래프나 산점도를 통해 데이터의 증가/감소 추세, 주기성, 상관관계 등을 쉽게 파악할 수 있습니다.
  • 복잡한 데이터의 단순화: 복잡하고 많은 양의 데이터를 단순하고 명확하게 표현할 수 있습니다. 예를 들어, 여러 지역의 인구 변화를 하나의 그래프로 표현하여 전체적인 추세를 쉽게 파악할 수 있습니다.
  • 흥미 유발 및 기억력 향상: 시각적인 요소는 사람들의 흥미를 유발하고 기억력을 향상시키는 데 효과적입니다. 따라서 그래프를 사용하면 데이터를 더 효과적으로 전달하고 기억에 오래 남도록 할 수 있습니다.

단점

  • 정확한 수치 표현의 한계: 그래프는 전반적인 추세나 비교를 보여주는 데 효과적이지만, 정확한 수치를 나타내는 데는 한계가 있을 수 있습니다. 예를 들어, 막대 그래프에서 막대의 높이로 크기를 비교할 수는 있지만, 정확한 수치를 읽어내기는 어려울 수 있습니다.
  • 데이터 왜곡 가능성: 그래프의 종류, 축의 설정, 눈금 간격 등에 따라 데이터를 왜곡하여 보여줄 수 있습니다. 예를 들어, y축의 범위를 조절하여 데이터의 변화폭을 과장하거나 축소하여 보여줄 수 있습니다.
  • 특정 유형의 데이터에만 적합: 모든 유형의 데이터를 그래프로 표현하는 것이 적합한 것은 아닙니다. 예를 들어, 범주형 데이터의 비율을 나타낼 때는 원 그래프가 적합하지만, 시간의 흐름에 따른 변화를 나타낼 때는 꺾은선 그래프가 더 적합합니다. 데이터의 특성에 따라 적절한 그래프 유형을 선택해야 합니다.
  • 세부 정보 손실 가능성: 그래프는 데이터를 단순화하여 보여주기 때문에, 세부적인 정보가 손실될 수 있습니다. 예를 들어, 산점도에서 데이터의 분포를 보여줄 수는 있지만, 각 데이터의 정확한 값은 알 수 없습니다.
  • 많은 공간 차지: 표에 비해 더 많은 공간을 차지할 수 있습니다. 특히 여러 개의 그래프를 함께 표시해야 하는 경우, 페이지 레이아웃에 제약이 생길 수 있습니다.

그래프 유형별 장단점

  • 막대 그래프:
    • 장점: 항목 간의 크기 비교가 용이, 최대/최소값 파악 용이.
    • 단점: 전체 합계를 나타내기 어려움, 시간에 따른 변화를 보여주기에는 부적합.
  • 꺾은선 그래프:
    • 장점: 시간에 따른 데이터 변화 추세 파악 용이, 여러 데이터의 변화 추세 비교 용이.
    • 단점: 정확한 수치 표현이 어려울 수 있음, 변화가 없는 데이터에는 적합하지 않음.
  • 원 그래프:
    • 장점: 전체에 대한 각 부분의 비율을 한눈에 파악 가능, 간결한 표현.
    • 단점: 작은 값의 표현이 어려움, 시간에 따른 변화 표현에 부적합, 전체 합계가 100%여야 함.
  • 산점도:
    • 장점: 두 변수 간의 상관관계 파악 용이, 데이터의 분포 파악 용이.
    • 단점: 정확한 수치 표현이 어려움, 데이터가 많을 경우 해석이 어려울 수 있음.



예제

[기본적인 형태]

#include <iostream>
#include <vector>
#include <list>

using namespace std;

class Graph {
private:
    int numVertices; // 정점의 개수
    vector<list<int>> adj; // 인접 리스트

public:
    Graph(int vertices) : numVertices(vertices), adj(vertices) {}

    void addEdge(int u, int v) {
        adj[u].push_back(v); // u에서 v로 가는 간선 추가
        // 무방향 그래프의 경우 아래 코드 추가
        // adj[v].push_back(u);
    }

    void printGraph() {
        for (int v = 0; v < numVertices; v++) {
            cout << "Adjacency list of vertex " << v << endl;
            cout << "head";
            for (int x : adj[v])
                cout << " -> " << x;
            cout << endl;
        }
    }
};

int main() {
    Graph g(4);
    g.addEdge(0, 1);
    g.addEdge(0, 2);
    g.addEdge(1, 2);
    g.addEdge(2, 0);
    g.addEdge(2, 3);

    g.printGraph();

    return 0;
}



[연결리스트로 그래프 구현]

#include <iostream>

// 연결 리스트 노드 구조체
struct AdjListNode {
    int dest; // 인접 정점 번호
    AdjListNode* next;

    AdjListNode(int d) : dest(d), next(nullptr) {}
};

// 그래프 구조체
class Graph {
private:
    int numVertices; // 정점의 개수
    AdjListNode** adj; // 인접 리스트 배열 (각 요소가 연결 리스트의 헤드)

public:
    Graph(int vertices) : numVertices(vertices) {
        adj = new AdjListNode*[numVertices];
        for (int i = 0; i < numVertices; ++i) {
            adj[i] = nullptr; // 각 정점의 연결 리스트 초기화
        }
    }

    ~Graph() {
        for (int i = 0; i < numVertices; ++i) {
            AdjListNode* current = adj[i];
            while (current != nullptr) {
                AdjListNode* next = current->next;
                delete current;
                current = next;
            }
        }
        delete[] adj;
    }

    void addEdge(int src, int dest) {
        AdjListNode* newNode = new AdjListNode(dest);
        newNode->next = adj[src];
        adj[src] = newNode;

        // 무방향 그래프의 경우 반대 방향 간선도 추가
        // newNode = new AdjListNode(src);
        // newNode->next = adj[dest];
        // adj[dest] = newNode;
    }

    void printGraph() {
        for (int v = 0; v < numVertices; ++v) {
            AdjListNode* temp = adj[v];
            std::cout << "Adjacency list of vertex " << v << "\n head";
            while (temp) {
                std::cout << " -> " << temp->dest;
                temp = temp->next;
            }
            std::cout << "\n";
        }
    }
};

int main() {
    Graph g(5);
    g.addEdge(0, 1);
    g.addEdge(0, 4);
    g.addEdge(1, 2);
    g.addEdge(1, 3);
    g.addEdge(1, 4);
    g.addEdge(2, 3);
    g.addEdge(3, 4);

    g.printGraph();

    return 0;
}




Top

You May Also Enjoy

1 minute read