[알고리즘/자료구조] 그래프 (Graph) -1- 인접리스트 구현

그래프

정점의 모음과 이 정점을 잇는 간선의 모음의 결합

정점의 집합을 V, 간선의 집합을 E, 그래프를 G라 했을때 G = (V, E)

인접리스트와 인접 행렬로 구현할 수 있다.

예시

행렬로 구현한 예

리스트로 구현한 예

소스

/*    
/*    khsh5592@naver.com
/*    has3ong.tistory.com
/*    
/*    2018 - 12 - 09
/*
*/
 
 
#include <stdio.h>
#include <iostream>
#include <conio.h>
 
using namespace std;
 
class Vertex
{
public:
    int Data;
    int index;
 
    class Edge* edge_list;
    Vertex* next;
 
    Vertex* vertex_Create(int newData, int index);
};
 
class Edge
{
public:
 
    int weight;
 
    Edge* next;
 
    Vertex* from;
    Vertex* to;
 
    Edge* edge_Create(Vertex* from, Vertex* to, int weight);
};
 
class Graph
{
public:
 
    Vertex* Vertex_list;
 
    int cnt;
 
    Graph* graph_Create();
    void add_Vertex(Graph* G, Vertex* V);
    void add_Edge(Vertex* V, Edge* E);
};
 
 
Graph* graph_Create()
{
    Graph* G = new Graph;
    G -> Vertex_list = NULL;
    G -> cnt = 0;
    
    return G;
}
 
Vertex* vertex_Create(int newData, int index)
{
    Vertex* V = new Vertex;
    V -> Data = newData;
    V -> index = index;
    V -> next = NULL;
    V -> edge_list = NULL;
 
    return V;
}
 
Edge* edge_Create(Vertex* from, Vertex* to, int weight)
{
    Edge* E = new Edge;
    E -> weight = weight;
    E -> from = from;
    E -> to = to;
    E -> next = NULL;
 
    return E;
}
 
void add_Vertex(Graph* G, Vertex* V)
{
    Vertex* list = G -> Vertex_list;
 
    if (list == NULL)
    {
        G -> Vertex_list = V;
    }
 
    else
    {
        while (list -> next != NULL)
        {
            list = list -> next;
        }
 
        list -> next = V;
    }
    G -> cnt++;
}
 
void add_Edge(Vertex* V, Edge* E)
{
    if (V -> edge_list == NULL)
    {
        V -> edge_list = E;
    }
 
    else
    {
        Edge* list = V -> edge_list;
 
        while (list -> next != NULL)
        {
            list = list -> next;
        }
 
        list -> next = E;
    }
}
 
void print(Graph* G)
{
    Vertex* V = NULL;
    Edge* E = NULL;
 
    if(G -> Vertex_list == NULL)
    {
        return;
    }
 
    else
    {
        V = G -> Vertex_list;
        while( V != NULL)
        {
            cout << "Index : " <<  V -> index << " Data : " << V-> Data;
            
            if (V -> edge_list == NULL)
            {
            }
 
            else
            {
                E = V -> edge_list;
                while(E != NULL)
                {
                    cout << "   [ " << E->from << ", " << E -> to << " ]  = " << E->weight;
                    E = E -> next;
                }
            }
            cout << endl;
            V = V -> next;
        }
    }
}
 
void main()
{
    Graph* G = graph_Create();
 
    Vertex* vertex0 = vertex_Create(0, 0);
    Vertex* vertex1 = vertex_Create(1, 1);
    Vertex* vertex2 = vertex_Create(2, 2);
    Vertex* vertex3 = vertex_Create(3, 3);
 
 
    add_Vertex(G, vertex0);
    add_Vertex(G, vertex1);
    add_Vertex(G, vertex2);
    add_Vertex(G, vertex3);
 
 
    Edge* edge0 = edge_Create(vertex0, vertex1, 1);
    Edge* edge1 = edge_Create(vertex0, vertex2, 2);
 
    Edge* edge2 = edge_Create(vertex1, vertex0, 3);
    Edge* edge3 = edge_Create(vertex1, vertex2, 4);
 
    Edge* edge4 = edge_Create(vertex2, vertex0, 5);
    Edge* edge5 = edge_Create(vertex2, vertex1, 6);
    Edge* edge6 = edge_Create(vertex2, vertex3, 7);
 
    Edge* edge7 = edge_Create(vertex3, vertex2, 8);
 
    add_Edge(vertex0, edge0);
    add_Edge(vertex0, edge1);
 
    add_Edge(vertex1, edge2);
    add_Edge(vertex1, edge3);
 
    add_Edge(vertex2, edge4);
    add_Edge(vertex2, edge5);
    add_Edge(vertex2, edge6);
 
    add_Edge(vertex3, edge7);
 
    print(G);
 
    getch();
}

결과화면