자료구조 그래프

June 10, 2022

그래프

그래프(Graph)

연결되어 있는 객체 간의 관계를 표현하는 자료구조
ex)
- 트리도 그래프의 하나
- 전기회로의 소자 간 연결상태
- 지도에서 도시들의 연결상태
- 지하철 노선도
- 도로망
- 선수과목 관계

그래프의 역사

1800년대 오일러의 의하여 창안
오일러 문제
- 모든 다리를 한번만 건너서 처음 출발했던 장소로 돌아오는 문제
A.B.C.D 지역의 연결 관계 표현
- 위치 : 정점(node)
- 다리 : 간선(edge)
오일러 정리
- 모든 정점에 연결된 간선의 수가 짝수 이면 오일러 경로가 존재함
- 따라서 그래프 (b)에는 오일러 경로가 존재하지 않음

그래프의 정의

그래프 G는(V,E)로 표시
정점(Vertices)
- 여러 가지 특성을 가질 수 있는 객체 의미
- V(G) : 그래프 G의 정점들의 집합
- 노드(Node)라고도 불림
간선(Edge)
- 정점들 간의 관계 의미
- E(G) : 그래프 G의 간선들의 집합
- 링크(link)라고도 불림

제목 없음

G1 연결 그래프(무방향)
- V(G1)= {0, 1, 2, 3}, E(G1)= {(0, 1), (0, 2), (0, 3), (1, 2), (2, 3)}
G2 비연결 그래프(무방향)
- V(G2)= {0, 1, 2, 3}, E(G3)= {(0, 1), (0, 2))}
G3 방향 그래프
- V(G2)= {0, 1, 2}, E(G2)= {<0, 1>, <1, 0>, <1, 2>}

네트워크

가중치 그래프는 네트워크(network)라고도 함
간선에 비용(cost)이나 가중치(weight)가 할당된 그래프
네트워크의 예
- 정점 : 각 도시를 의미
- 간선 : 도시를 연결하는 도로
- 가중치 : 도로의 길이

부분 그래프

정점 집합 V(G)와 간선 집합E(G)의 부분 집합으로 이루어진 그래프
그래프 G1의 부분 그래프들

그래프

인접 정점(adjacent vertex)
- 하나의 정점에서 간선에 의해 직접 연결된 정점
- G1에서 정점 0의 인접 정점: 정점 1, 정점2, 정점 3
무방향 그래프의 차수(degree)
- 하나의 정점에 연결된 다른 정점의 수
- G1에서 정점 0의 차수 : 3
방향 그래프의 차수(degree)
- 진입 차수
- 진출 차수
- G3에서 정점 1의 차수: 내차수 1, 외차수 2
- 방향 그래프의 모든 진입(진출) 차수의 합은 간선의 수

무방향 인접행렬 그래프

#include <stdio.h>
#include <stdlib.h>

#define N 10

typedef struct Graph
{
    int num_Vertex;
    int adjM[N][N];
}Graph; //그래프를 표현 할 인접행렬

void init(Graph *G){
    G->num_Vertex = 0;
    for(int i=0; i<N; i++){
        for(int j=0; j<N; j++){
            G->adjM[i][j] = 0;
        }
    }
} // 인접행렬의 모든 관계를 0으로 초기화

void makeVertex(Graph *G){
    G->num_Vertex++;
} // 노드를 한개 추가

int indexError(Graph *G, int u, int v){
    if(G->num_Vertex <= u || G->num_Vertex <= v)
        return 1;
    return 0;
}

void insertEdge(Graph *G, int u, int v){
    if(indexError(G,u,v))
        printf("INDEX ERROR!!\n");
    else{
        G->adjM[u][v] = 1;
        G->adjM[v][u] = 1;
        //무방향 그래프의 경우  주대각원소를 기준으로 서로 대칭행렬이므로해당 INDEX에 1를 넣어준다.
    }
}

void print(Graph *G){
    for(int i=0; i<N; i++){
        for(int j=0; j<N; j++){
            printf("[%d]", G->adjM[i][j]);
        }
        printf("\n");
    }
}


int main(){
    Graph G;
    init(&G);

    int n = 5;
    for(int i=0; i<n; i++)
        makeVertex(&G);

    insertEdge(&G, 0, 1); insertEdge(&G, 0, 2); insertEdge(&G, 0, 3);
    insertEdge(&G, 1, 2); insertEdge(&G, 2, 3);
    print(&G);


    return 0;
}

인접리스트 이용하여 그래프 표현

#include <stdio.h>
#include <stdlib.h>

typedef struct incidentEdge
{
    int key;
    struct incidentEdge * next;

}incidentEdge; //인접엣지는 연결리스트를 계속 추가해주면 된다.

typedef struct Vertex{
    int vKey;
    int isVisit;
    struct Vertex * next;
    incidentEdge * iHead;
}Vertex;
//정점 또는 노드의 구성요소
// 1. 노드의 들어갈 값
// 2. 노드를 방문했는지 여부
// 3. 다음 노드를 가르킬 포인터
// 4. 해당 노드의 인접엣지를 가르킬 포인터

typedef struct Graph{
    Vertex * vHead;
}Graph;
// 그래프의 연결리스트 표현을 위해 최초 노드

void init(Graph *G){
    G->vHead = NULL;
}
// 초기 헤드의 포인터를 NULL로 지정

void makeVertex(Graph *G, int key){
    Vertex * v = (Vertex*)malloc(sizeof(Vertex));
    v->isVisit = 0;
    v->vKey = key;
    v->iHead = NULL;
    v->next = NULL;
// 노드 추가 시 기본셋팅
    Vertex * p = G->vHead;
    if(p==NULL){ //최초의 노드일 경우
        G->vHead = v;
    }
    else{ //최초 노드가 아닐경우
        while(p->next!=NULL)
            p = p->next;
        p->next = v;
    }
}

void makeIncidentEdge(Vertex *v, int key){
    incidentEdge * E = (incidentEdge*)malloc(sizeof(incidentEdge));
    E->key = key;
    E->next = NULL;
    // 초기 셋팅
    incidentEdge * q = v->iHead;
    // 현재 정점의 인접헤드를 저장
    if(q==NULL){ // 최초의 인접헤드
        v->iHead = E;
    }
    else{ // 비어있는 인접헤드까지
        while(q->next!=NULL)
            q = q->next;
        q->next = E;
    }
}

Vertex *findVertex(Graph *G, int vKey){
    Vertex * v = G->vHead;
    while(v->vKey != vKey) //원하는 키까지 간 후
        v = v->next;


    return v; //해당 정점 반환
}

void insertEdge(Graph *G, int vKey1, int vKey2){
    Vertex * v = findVertex(G,vKey1); //해당 정점을 찾고
    makeIncidentEdge(v,vKey2); // 서로 연결
    v = findVertex(G,vKey2);
    makeIncidentEdge(v,vKey1);
}

void print(Graph *G){
    Vertex * p = G->vHead;
    incidentEdge * q;
    for(; p!=NULL; p= p->next){
        printf("[%d] ",p->vKey);
        for(q = p->iHead; q!=NULL; q= q->next){
            printf("[%d] ", q->key);
        }
        printf("\n");
    }
    printf("\n");
}

int main(){

    Graph G;
    init(&G);


    makeVertex(&G, 1); makeVertex(&G, 2); makeVertex(&G, 3);
    makeVertex(&G, 4); makeVertex(&G, 5); makeVertex(&G, 6);
    makeVertex(&G, 7); makeVertex(&G, 8);

    insertEdge(&G, 1, 2); insertEdge(&G, 1, 3);
    insertEdge(&G, 2, 4); insertEdge(&G, 2, 5);
    insertEdge(&G, 3, 5); insertEdge(&G, 5, 6);
    insertEdge(&G, 6, 7); insertEdge(&G, 7, 8);

    print(&G);

    return 0;
}

그래프 탐색

DFS(깊이 우선 탐색) -> Stack을 이용

#include <stdio.h>
#include <stdlib.h>

#define N 10
#define FALSE 0
#define TRUE 1


typedef struct
{
    int stack[N];
    int top;
}StackType;

void initStack(StackType* S)
{
    S->top = -1;
}

int isEmpty(StackType* S)
{
    return S->top == -1;
}

int isFull(StackType* S)
{
    return S->top == N - 1;
}

void push(StackType* S, int e)
{
    if(isFull(S))
        printf("Full\n");
    else
    {
        S->top++;
        S->stack[S->top] = e;
    }
}


int pop(StackType* S)
{
    if(isEmpty(S))
    {
        printf("Empty\n");
        return -1;
    }
    int elem = S->stack[S->top];
    S->top--;
    return elem;
}

int peek(StackType* S)
{
    if(isEmpty(S))
    {
        printf("Empty\n");
        return -1;
    }
    int elem = S->stack[S->top];
    return elem;
}
////////////////////////////////////STACK//////////////////////////////////////

// 엣지 정보 구조체
typedef struct IncidentEdge{
    int Inode;
    struct IncidentEdge * Inext;
}IncidentEdge;


// 정점 정보 구조체
typedef struct Vertex{
    int Vnode;
    int isVisit;
    struct Vertex * Vnext;
    struct IncidentEdge * Inext;
}Vertex;

// 그래프의 헤드
typedef struct Graph{
    Vertex * G_head;
}Graph;

// 초기화
void init(Graph *G){
    G->G_head = NULL;
}

// 정점 만들기
void makeVertex(Graph *G, int Node){
    Vertex * V = (Vertex*)malloc(sizeof(Vertex));

    V->Vnode = Node;
    V->isVisit = FALSE;
    V->Inext = NULL;
    V->Vnext = NULL;

    Vertex *p = G->G_head;

    if(p==NULL) //최초의 정점
         G->G_head = V;
    else{
        while(p->Vnext!=NULL)
            p = p->Vnext;
        p->Vnext = V;
    }
}

Vertex *findVertex(Graph *G, int Node){
    Vertex * p = G->G_head;

    while(p->Vnode != Node)
        p = p->Vnext;
    return p;
}

void makeIncidentEdge(Vertex *V, int V2){
    IncidentEdge * E = (IncidentEdge*)malloc(sizeof(IncidentEdge));

    E->Inode = V2;
    E->Inext = NULL;

    IncidentEdge * q = V->Inext;

    if(q==NULL)
        V->Inext = E;
    else{
        while(q->Inext !=NULL)
            q = q->Inext;
        q->Inext = E;
    }

}

void insertEdge(Graph *G, int V1, int V2){
    Vertex *V = findVertex(G,V1);
    makeIncidentEdge(V, V2);
    V = findVertex(G,V2);
    makeIncidentEdge(V, V1);
}


void DFS(Graph *G, int Target){
    // Step1.시작 정점을 찾는다
    Vertex *V = findVertex(G, Target);
    IncidentEdge *E;
    // Step2.스택 생성 및 초기화
    StackType S;
    initStack(&S);

    // Step3.첫 정점 푸쉬
    push(&S, V->Vnode);
    // Step4. 스택의 원소가 없을때까지
    while(!isEmpty(&S)){
        // 스택의 최상단의 정점을 찾음 -> 방문체크 -> 출력 -> 인접노드 확인 방문하지않은 노드가 나오면 push -> break;
        V = findVertex(G, peek(&S));
        if(V->isVisit == FALSE){
            V->isVisit = TRUE;
            printf("[%d] ", V->Vnode);
        }

        for(E=V->Inext; E!=NULL; E= E->Inext){
            V = findVertex(G, E->Inode);
            if(V->isVisit == FALSE){
                push(&S, V->Vnode);
                break;
            }
        }
        // Step5. 만약 인접노드를 다 방문 했다면 해당 노드 삭제
        if(E==NULL)
            pop(&S);
    }
}

void print(Graph *G){
    Vertex *p = G->G_head;
    IncidentEdge *q;

    for(; p!=NULL; p=p->Vnext){
        printf("[%d] ", p->Vnode);
        for(q= p->Inext; q!=NULL; q= q->Inext){
            printf("[%d] ", q->Inode);
        }
        printf("\n");
    }
    printf("\n");
}





int main(){

    Graph G;
    init(&G);


    makeVertex(&G, 1); makeVertex(&G, 2); makeVertex(&G, 3);
    makeVertex(&G, 4); makeVertex(&G, 5); makeVertex(&G, 6);
    makeVertex(&G, 7); makeVertex(&G, 8);

    insertEdge(&G, 1, 2); insertEdge(&G, 1, 3);
    insertEdge(&G, 2, 4); insertEdge(&G, 2, 5);
    insertEdge(&G, 3, 5); insertEdge(&G, 5, 6);
    insertEdge(&G, 6, 7); insertEdge(&G, 7, 8);

    print(&G);

    DFS(&G,1);
    return 0;
}

그래프 탐색

BFS(너비우선탐색) -> Queue를 이용

#include <stdio.h>
#include <stdlib.h>

#define N 10
#define FALSE 0
#define TRUE 1


typedef struct
{
    int stack[N];
    int top;
}StackType;

void initStack(StackType* S)
{
    S->top = -1;
}

int isEmpty(StackType* S)
{
    return S->top == -1;
}

int isFull(StackType* S)
{
    return S->top == N - 1;
}

void push(StackType* S, int e)
{
    if(isFull(S))
        printf("Full\n");
    else
    {
        S->top++;
        S->stack[S->top] = e;
    }
}


int pop(StackType* S)
{
    if(isEmpty(S))
    {
        printf("Empty\n");
        return -1;
    }
    int elem = S->stack[S->top];
    S->top--;
    return elem;
}

int peek(StackType* S)
{
    if(isEmpty(S))
    {
        printf("Empty\n");
        return -1;
    }
    int elem = S->stack[S->top];
    return elem;
}
////////////////////////////////////STACK//////////////////////////////////////


typedef struct
{
char elem[N];
int front, rear;
}QueueType;

void initQueue(QueueType* Q)
{
Q->front = Q->rear = 0;
}

int isQueueEmpty(QueueType* Q)
{
return Q->rear == Q->front;
}

int isQueueFull(QueueType* Q)
{
return (Q->rear + 1) % N == Q->front;
}

void enqueue(QueueType* Q, char vName)
{
if (isQueueFull(Q))
{
printf("FULL\n");
return;
}

Q->rear = (Q->rear + 1) % N;
Q->elem[Q->rear] = vName;
}

char dequeue(QueueType* Q)
{
if (isQueueEmpty(Q))
{
printf("EMPTY\n");
return 0;
}

Q->front = (Q->front + 1) % N;
return Q->elem[Q->front];
}
////////////////////////////////////QUEUE//////////////////////////////////////


// 엣지 정보 구조체
typedef struct IncidentEdge{
    int Inode;
    struct IncidentEdge * Inext;
}IncidentEdge;


// 정점 정보 구조체
typedef struct Vertex{
    int Vnode;
    int isVisit;
    struct Vertex * Vnext;
    struct IncidentEdge * Inext;
}Vertex;

// 그래프의 헤드
typedef struct Graph{
    Vertex * G_head;
}Graph;

// 초기화
void init(Graph *G){
    G->G_head = NULL;
}

// 정점 만들기
void makeVertex(Graph *G, int Node){
    Vertex * V = (Vertex*)malloc(sizeof(Vertex));

    V->Vnode = Node;
    V->isVisit = FALSE;
    V->Inext = NULL;
    V->Vnext = NULL;

    Vertex *p = G->G_head;

    if(p==NULL) //최초의 정점
         G->G_head = V;
    else{
        while(p->Vnext!=NULL)
            p = p->Vnext;
        p->Vnext = V;
    }
}

Vertex *findVertex(Graph *G, int Node){
    Vertex * p = G->G_head;

    while(p->Vnode != Node)
        p = p->Vnext;
    return p;
}

void makeIncidentEdge(Vertex *V, int V2){
    IncidentEdge * E = (IncidentEdge*)malloc(sizeof(IncidentEdge));

    E->Inode = V2;
    E->Inext = NULL;

    IncidentEdge * q = V->Inext;

    if(q==NULL)
        V->Inext = E;
    else{
        while(q->Inext !=NULL)
            q = q->Inext;
        q->Inext = E;
    }

}

void insertEdge(Graph *G, int V1, int V2){
    Vertex *V = findVertex(G,V1);
    makeIncidentEdge(V, V2);
    V = findVertex(G,V2);
    makeIncidentEdge(V, V1);
}

void BFS(Graph *G, int Target){
    Vertex *V = findVertex(G, Target);
    IncidentEdge *E;

    QueueType Q;
    initQueue(&Q);

    V->isVisit = TRUE;
    printf("[%d] ", V->Vnode);
    enqueue(&Q, V->Vnode);

    while(!isQueueEmpty(&Q)){
        V = findVertex(G, dequeue(&Q));
        for(E=V->Inext; E!=NULL; E= E->Inext){
            V =findVertex(G,E->Inode);
            if(V->isVisit == FALSE){
                V->isVisit = TRUE;
                printf("[%d] ", V->Vnode);
                enqueue(&Q, V->Vnode);
            }
        }
    }
}

void DFS(Graph *G, int Target){
    Vertex *V = findVertex(G, Target);
    IncidentEdge *E;

    StackType S;
    initStack(&S);

    push(&S, V->Vnode);

    while(!isEmpty(&S)){
        V = findVertex(G, peek(&S));
        if(V->isVisit == FALSE){
            V->isVisit = TRUE;
            printf("[%d] ", V->Vnode);
        }

        for(E=V->Inext; E!=NULL; E= E->Inext){
            V = findVertex(G, E->Inode);
            if(V->isVisit == FALSE){
                push(&S, V->Vnode);
                break;
            }
        }
        if(E==NULL)
            pop(&S);
    }
}



void print(Graph *G){
    Vertex *p = G->G_head;
    IncidentEdge *q;

    for(; p!=NULL; p=p->Vnext){
        printf("[%d] ", p->Vnode);
        for(q= p->Inext; q!=NULL; q= q->Inext){
            printf("[%d] ", q->Inode);
        }
        printf("\n");
    }
    printf("\n");
}





int main(){

    Graph G;
    init(&G);


    makeVertex(&G, 1); makeVertex(&G, 2); makeVertex(&G, 3);
    makeVertex(&G, 4); makeVertex(&G, 5); makeVertex(&G, 6);
    makeVertex(&G, 7); makeVertex(&G, 8);

    insertEdge(&G, 1, 2); insertEdge(&G, 1, 3);
    insertEdge(&G, 2, 4); insertEdge(&G, 2, 5);
    insertEdge(&G, 3, 5); insertEdge(&G, 5, 6);
    insertEdge(&G, 6, 7); insertEdge(&G, 7, 8);

    print(&G);

    // DFS(&G,1);
    printf("\n");
    BFS(&G,1);

    return 0;
}

신장트리

최소비용 신장 트리
가중치 그래프를 이용하여 최소비용의 신장트리를 만들 수 있는 알고리즘이다.

Kruscal 알고리즘

#include <stdio.h>
#include <stdlib.h>


typedef struct Edge{
    char v1, v2;
    int weight;
    struct Edge *next;
}Edge;


typedef struct IncidentEdge
{
    char aName;
    Edge *e;
    struct IncidentEdge* next;
}IncidentEdge;


typedef struct Vertex
{
    char vName;
    IncidentEdge* iHead;
    struct Vertex* next;
}Vertex;


typedef struct
{
    Vertex *vHead;
    Edge *eHead;
    int eCount, vCount;
}GraphType;


void init(GraphType* G)
{
    G->vHead = NULL;
    G->eHead = NULL;
    G->vCount = G->eCount = 0;
}

void makeVertex(GraphType* G, char vName)
{
    Vertex* v = (Vertex*)malloc(sizeof(Vertex));
    v->vName = vName;
    v->iHead = NULL;
    v->next = NULL;
    G->vCount++;
    Vertex* p = G->vHead;
    if(p == NULL)
        G->vHead = v;
    else
    {
        while(p->next != NULL)
            p = p->next;
        p->next = v;
    }
}


void makeIncidentEdge(Vertex* v, char aName, Edge* e)
{
    IncidentEdge* p = (IncidentEdge*)malloc(sizeof(IncidentEdge));
    p->aName = aName;
    p->e = e;
    p->next = NULL;
    IncidentEdge* q = v->iHead;
    if(q == NULL)
        v->iHead = p;
    else
    {
        while(q->next != NULL)
            q = q->next;
        q->next = p;
    }
}


Vertex* findVertex(GraphType* G, char vName)
{
    Vertex* v = G->vHead;
    while(v->vName != vName)
        v = v->next;
    return v;
}


void insertEdge(GraphType* G, char v1, char v2, int w)
{
    Edge* e = (Edge *)malloc(sizeof(Edge));
    e->weight = w;
    e->v1 = v1;
    e->v2 = v2;
    e->next = NULL;
    G->eCount++;

    Edge* q = G->eHead;
    if(q == NULL)
        G->eHead = e;
    else
    {
        while(q->next != NULL)
            q = q->next;
        q->next = e;
    }
    Vertex* v = findVertex(G, v1);
    makeIncidentEdge(v, v2, e);
    v = findVertex(G, v2);
    makeIncidentEdge(v, v1, e);
}



void print(GraphType* G)
{
    Vertex* p = G->vHead;
    IncidentEdge* q;
    for(; p != NULL; p = p->next)
    {
        printf("[%c] : ", p->vName);
        for(q = p->iHead; q != NULL; q = q->next)
            printf("[%c, %d] ", q->aName, q->e->weight);
        printf("\n");
    }
    printf("\n");
}

void incSort(GraphType* G, Edge* e[])
{
    int i, least;
    Edge* p = G->eHead;
    for(i = 0; i < G->eCount; i++)
    {
        e[i] = p;
        p = p->next;
    }
    for(i = 0; i < G->eCount - 1; i++)
    {
        least = i;
        for(int j = i + 1; j < G->eCount; j++)
            if(e[j]->weight < e[least]->weight)
                least = j;
        p = e[least];
        e[least] = e[i];
        e[i] = p;
    }
    for(i = 0; i < G->eCount - 1; i++)
        printf("[%c%c%d] ", e[i]->v1, e[i]->v2, e[i]->weight);
    printf("\n\n");
}


int vFind(int v[], int vNum)
{
    if(v[vNum] == -1)
        return vNum;
    while (v[vNum] != -1)
vNum = v[vNum];
return vNum;
}



void vUnion(int v[], int vNum1, int vNum2)
{
int r1 = vFind(v, vNum1);
int r2 = vFind(v, vNum2);
if (r1 != r2)
v[r2] = r1;
}


void kruskal(GraphType* G, Edge* e[], int v[])
{
    int eCnt = 0, i = 0;
    int vNum1, vNum2;
    Edge* p;
    while(eCnt < G->vCount - 1)
    {
        p = e[i];
        vNum1 = vFind(v, p->v1 - 97);
        vNum2 = vFind(v, p->v2 - 97);
        if(vNum1 != vNum2)
        {
            printf("%d. [%c%c %d]\n", eCnt + 1, p->v1, p->v2, p->weight);
            eCnt++;
            vUnion(v, vNum1, vNum2);
        }
        i++;
    }
}


int main()
{

    GraphType G;
    init(&G);


    makeVertex(&G, 'a'); makeVertex(&G, 'b'); makeVertex(&G, 'c');
    makeVertex(&G, 'd'); makeVertex(&G, 'e'); makeVertex(&G, 'f');
    makeVertex(&G, 'g');

    insertEdge(&G, 'a', 'b', 29); insertEdge(&G, 'a', 'f', 10);
    insertEdge(&G, 'b', 'c', 16); insertEdge(&G, 'b', 'g', 15);
    insertEdge(&G, 'c', 'd', 12); insertEdge(&G, 'd', 'g', 18);
    insertEdge(&G, 'd', 'e', 22); insertEdge(&G, 'e', 'f', 27);
    insertEdge(&G, 'e', 'g', 25); print(&G);


    Edge* e[20];
    incSort(&G, e);

    int v[10] = {-1, -1, -1, -1, -1, -1, -1, -1, -1, -1};
    kruskal(&G, e, v);

}