[자료구조] 인접리스트로 구현한 그래프

정점 간의 관계를 인접리스트를 통해 표현한다.

인접리스트는 링크필드를 가진 노드와 노드를 가르키는 포인터를 저장하는 1차원 배열을 통해 구현한다.

 

 

 

### 인접리스트에서 사용하는 노드 ###

#pragma once
#include <iostream>
 
class Node {
protected:
    int id;
    Node* link;
public:
    Node(int i, Node* l = NULL) : id(i), link(l) {}
    ~Node() {
        if (link != NULL) delete link;
    }
    int getID() { return id; }
    Node* getLink() { return link; }
    void setLink(Node* l) { link = l; }
};
 

 

 

 

### 인접리스트를 사용한 그래프 ###

#pragma once
#include "Node.h"
#define MAX_VTXS 100
 
class AdjListGraph{
protected:
    int size;
    char vertices[MAX_VTXS];
    Node* adj[MAX_VTXS];
    // 인접리스트에서는 정점을 가르키는 포인터를 이용해서
    // 연결성을 나타내는데 이러한 포인터를 저장하는 배열
 
public:
    AdjListGraph() : size(0) {}
    ~AdjListGraph() { reset(); }
    bool isFull() { return size >= MAX_VTXS; }
    bool isEmpty() { return size == 0; }
    char getVertex(int i) { return vertices[i]; }
 
    void reset() { // 그래프 초기화
        for (int i = 0; i < size; i++)
            if (adj[i] != NULL) delete adj[i];
        // 모든 정점을 대상으로 인접 리스트의 포인터가 가르키고 있는
        // 노드를 메모리 할당 해지한다.
    }
 
    void insertVertex(char val) { // 정점 삽입
        if (!isFull()) {
            vertices[size] = val;
            adj[size++] = NULL;
            // vertices 배열에 입력된 값을 가진 요소를 추가하고
            // adj 배열에 같은 위치(인덱스)에 연결성을 나타낼 수 있는 
            // 포인터를 삽입한다.
        }
        else printf("그래프 정점 개수 초과\n");
    }
 
    void insertEdge(int u, int v) { // 간선 삽입, 정점 U와 V를 연결
        adj[u] = new Node(v, adj[u]);
        adj[v] = new Node(u, adj[v]);
    }
        // 간선을 삽입하는 과정은 연결성을 추가할 새로운 인접리스트 노드가
        // 기존의 노드가 가르켰던 노드를 가르키게 하고,
        // 기존의 노드는 새로운 인접리스트 노드를 가르키게 한다.
        // 
        // 위의 코드는 무방향 그래프 일때의 코드이고
        // 방향 그래프일 경우에는 윗 줄의 코드만 작성해서 한 방향의 연결을 나타내야한다.
 
    void display() { // 출력
        printf("%d\n", size);
        for (int i = 0; i < size; i++) {
            printf("%c ", getVertex(i));
            for (Node* v = adj[i]; v != NULL; v = v->getLink())
                // i번째 정점이 가지고 있는 인접리스트를 전부 출력
 
                printf(" %c", getVertex(v->getID()));
            printf("\n");
        }
    }
 
    Node* adjacent(int v) { return adj[v]; } // v번째 인접리스트 반환
 
};

 void insertEdge(int u, int v) { // 간선 삽입, 정점 U와 V를 연결
        adj[u] = new Node(v, adj[u]);
        adj[v] = new Node(u, adj[v]);
    }
        // 간선을 삽입하는 과정은 연결성을 추가할 새로운 인접리스트 노드가
        // 기존의 노드가 가르켰던 노드를 가르키게 하고,
        // 기존의 노드는 새로운 인접리스트 노드를 가르키게 한다.
        // 
        // 위의 코드는 무방향 그래프 일때의 코드이고
        // 방향 그래프일 경우에는 윗 줄의 코드만 작성해서 한 방향의 연결을 나타내야한다.

인접리스트 그래프 구현 결과(D에 C와 B가 연결되어 있고 E에 B가 연결있고 ... 등등)