[C언어] 그래프

알고리즘의 꽃, 그래프.

G=(V,E) 로 표현한다.

V는 정점을, E는 간선을 의미한다. 

크게 방향성 유무(Directed,Undirected)와 사이클 존재 유무(Cyclic,Acyclic)로 구분하는 듯 하다.

최소신장트리 알고리즘, 순회 알고리즘 등 많은 알고리즘이 그래프에서 파생되어 나온다.

1. Graph.h

#ifndef GRAPH_H
#define GRAPH_H
 
#include <stdio.h>
#include <stdlib.h>
 
enum VisitMode {Visited,NotVisited};
 
typedef int ElementType;
 
typedef struct tagVertex{
 
    ElementType Data;
    int VIsited;
    int Index;
 
    struct tagVertex* Next;
    struct tagEdge* AdjacencyList;
}Vertex;
 
typedef struct tagEdge{
    Vertex* From;
    Vertex* Target;
 
    int Weight;
    struct tagEdge* Next;
}Edge;
 
typedef struct tagGraph{
    Vertex* Vertices;
    int VertexCount;
}Graph;
 
 
Graph* CreateGraph();
void DestroyGraph(Graph* G);
 
Vertex* CreateVertex(ElementType Data);
void DestroyVertex(Vertex* V);
 
Edge* CreateEdge(Vertex* From,Vertex* Target,int Weight);
void DestroyEdge(Edge* E);
 
void AddVertex(Graph* G,Vertex* V);
void AddEdge(Vertex* V,Edge* E);
void PrintGraph(Graph* G);
 
#endif
 
 
 

2. Graph.c

#include "Graph.h"
 
 
Graph* CreateGraph(){
    Graph* graph=(Graph*)malloc(sizeof(Graph));
    graph->Vertices=NULL;
    graph->VertexCount=0;
 
    return graph;
}
 
void DestroyGraph(Graph* G){
    
    while(G->Vertices!=NULL){
        Vertex* Vertices=G->Vertices->Next;
        DestroyVertex(G->Vertices);
        G->Vertices=Vertices;
 
    }
 
    free(G);
}
 
Vertex* CreateVertex(ElementType Data){
    Vertex* V=(Vertex*)malloc(sizeof(Vertex));
    V->Data=Data;
    V->AdjacencyList=NULL;
    V->Index=-1;
    V->Next=NULL;
    V->VIsited=NotVisited;
 
    return V;
}
 
void DestroyVertex(Vertex* V){
    while(V->AdjacencyList!=NULL){
        Edge* Edge=V->AdjacencyList->Next;
        DestroyEdge(V->AdjacencyList);
        V->AdjacencyList=Edge;
    }
    free(V);
}
 
Edge* CreateEdge(Vertex* From,Vertex* Target,int Weight){
    Edge* E=(Edge*)malloc(sizeof(Edge));
 
    E->From=From;
    E->Target=Target;
    E->Weight=Weight;
    E->Next=NULL;
 
    return E;
}
 
void DestroyEdge(Edge* E){
    free(E);
}
 
void AddVertex(Graph* G,Vertex* V){
    Vertex* VertexList=G->Vertices;
 
    if(VertexList==NULL){
        G->Vertices=V;
    }
    else{
        while(VertexList->Next!=NULL){
            VertexList=VertexList->Next;
        }
        VertexList->Next=V;
    }
 
    V->Index=G->VertexCount++;
 
}
 
void AddEdge(Vertex* V,Edge* E){
 
    if(V->AdjacencyList==NULL){
        V->AdjacencyList=E;
    }
    else{
        Edge* AdjacencyList=V->AdjacencyList;
        while(AdjacencyList->Next!=NULL){
            AdjacencyList=AdjacencyList->Next;
        }
        AdjacencyList->Next=E;
    }
}
 
void PrintGraph(Graph* G){
    Vertex* V=NULL;
    Edge* E=NULL;
 
    if((V=G->Vertices)==NULL){
        return;
    }
    
    while(V!=NULL){
        printf("%c : ",V->Data);
 
        if((E=V->AdjacencyList)==NULL){
            V=V->Next;
            printf("\n");
            continue;
        }
 
        while(E!=NULL){
            printf("%c[%d] ",E->Target->Data,E->Weight);
            E=E->Next;
        }
 
        printf("\n");
 
        V=V->Next;
    }
 
    printf("\n");
 
}
 

3. Test_Graph.c

#include "Graph.h"
 
int main(){
    Graph* G=CreateGraph();
 
    /*정점 추가*/
    Vertex* V1=CreateVertex('1');
    Vertex* V2=CreateVertex('2');
    Vertex* V3=CreateVertex('3');
    Vertex* V4=CreateVertex('4');
    Vertex* V5=CreateVertex('5');
 
 
    /*그래프에 정점 추가*/
    AddVertex(G,V1);
    AddVertex(G,V2);
    AddVertex(G,V3);
    AddVertex(G,V4);
    AddVertex(G,V5);
 
    /* 정점과 정점을 간선으로 잇기 */
    AddEdge(V1,CreateEdge(V1,V2,0));
    AddEdge(V1,CreateEdge(V1,V3,0));
    AddEdge(V1,CreateEdge(V1,V4,0));
    AddEdge(V1,CreateEdge(V1,V5,0));
 
    AddEdge(V2,CreateEdge(V2,V1,0));
    AddEdge(V2,CreateEdge(V2,V3,0));
    AddEdge(V2,CreateEdge(V2,V5,0));
 
    AddEdge(V3,CreateEdge(V3,V1,0));
    AddEdge(V3,CreateEdge(V3,V2,0));
 
    AddEdge(V4,CreateEdge(V4,V1,0));
    AddEdge(V4,CreateEdge(V4,V5,0));
 
    AddEdge(V5,CreateEdge(V5,V1,0));
    AddEdge(V5,CreateEdge(V5,V2,0));
    AddEdge(V5,CreateEdge(V5,V4,0));
 
    PrintGraph(G);
 
    DestroyGraph(G);
 
    return 0;
}

실행 결과