[자료구조] 그래프(Graph)란? - 컴도리돌이

그래프(Graph)란?

 

연결되어 있는 객체 간의 관계를 표현하는 자료구조이다. 그래프 G는 (V, E)로 표시되며 V는 정점 또는 노드라고 불리며, 여러 가지 특성을 가질 수 있는 객체를 의미하고 E는 간선 또는 링크로 정점들 간의 관계를 의미한다.

 

 

그래프의 종류

무방향 그래프(undirected graph)

 

간선을 통해서 양방향으로 갈 수 있다.

 

방향 그래프(directed graph)

 

간선을 통해서 한쪽 방향으로만 갈 수 있다.

 

가중치 그래프(weighted graph)

 

간선에 비용이나 가중치가 할당된 그래프

그래프(graph)의 용어

 

• 인접 정점(adjacent vertex) :하나의 정점에서 간선에 의해 직접 연결된 정점

G1에서 정점 0의 인접 정점 : 1,2,3

• 차수(degree) : 하나의 정점에 연결된 간선의 수

G1에서 정점 0의 차수 : 3

• 경로(path) : 간선을 따라갈 수 있는 길

-무방향 그래프의 정점 s로부터 정점 e까지의 경로

-방향 그래프의 정점 s로부터 정점 e까지의 경로

• 경로의 길이(length) : 경로를 구성하는 데 사용된 간선의 수
• 단순 경로(simple path) : 경로 중에서 반복되는 간선이 없는 경로

1,0,2,3 단순 경로 <> 1,0,2,0은 단순 경로 x

• 사이클(cycle) : 시작 정점과 종료 종료 정점이 동일한 경로

사이클 0,1,2

인접 행렬로 구현한 그래프 그림 예시 && c언어 코드

 

 

인접 행렬로 구현한 그래프 그림 예시

 

 

#include <stdio.h>
#include <stdlib.h>
#define MAX_VTXS    256

void error(char str[])            // 오류 메시지 출력후 종료 함수: 공통
{
    printf("%s\n", str);
    exit(1);
}

typedef char VtxData;            // 그래프 정점에 저장할 데이터의 자료형
int adj[MAX_VTXS][MAX_VTXS];    // 인접 행렬
int vsize;                    // 전체 정점의 개수
VtxData vdata[MAX_VTXS];        // 정점에 저장할 데이터 배열

int is_empty_graph() { return (vsize == 0); }
int is_full_graph() { return (vsize >= MAX_VTXS); }
void init_graph()
{
    int i, j;
    vsize = 0;
    for (i = 0; i<MAX_VTXS; i++)
        for (j = 0; j<MAX_VTXS; j++)
            adj[i][j] = 0;
}
void insert_vertex(VtxData name)
{
    if (is_full_graph())
        error("Error: 그래프 정점의 개수 초과\n");
    else
        vdata[vsize++] = name;
}
void insert_edge(int u, int v, int val)
{
    adj[u][v] = val;
}
void insert_edge2(int u, int v, int val)
{
    adj[u][v] = adj[v][u] = val;
}

void print_graph(char* msg)
{
    int i, j;
    printf("%s", msg);
    printf("%d\n", vsize);
    for (i = 0; i<vsize; i++) {
        printf("%c  ", vdata[i]);
        for (j = 0; j<vsize; j++)
            printf(" %3d", adj[i][j]);
        printf("\n");
    }
}

 

인접 리스트로 구현한 그래프 그림 예시 && C언어 코드

 

 

인접 리스트로 구현한 그래프 그림 예시

 

인접리스트로 구현한 그래프 c언어 

 

#include <stdio.h>
#include <stdlib.h>
#define MAX_VTXS    256

void error(char str[])            // 오류 메시지 출력후 종료 함수: 공통
{
    printf("%s\n", str);
    exit(1);
}

typedef struct GraphNode {
    int id;                    // 정점의 id
    struct GraphNode* link;    // 다음 노드의 포인터
} GNode;

typedef char VtxData;            // 그래프 정점에 저장할 데이터의 자료형
GNode*    adj[MAX_VTXS];        // 각 정점의 인접 리스트 -> 이중포인터로 사용해도됌
int        vsize;                // 정점의 개수
VtxData vdata[MAX_VTXS];        // 정점에 저장할 데이터 배열

int is_empty_graph() { return (vsize == 0); }
int is_full_graph() { return (vsize >= MAX_VTXS); }

void init_graph() //그래프 초기화
{
    int i;
    vsize = 0;
    for (i = 0; i<MAX_VTXS; i++)
        adj[i] = NULL;
}
void reset_graph()
{
    int i;
    GNode* n;
    for (i = 0; i<vsize; i++) {
        while (adj[i] != NULL) {
            n = adj[i];
            adj[i] = n->link;
            free(n);
        }
    }
    vsize = 0;
}
void insert_vertex(VtxData name)
{
    if (is_full_graph())
        error("Error: 그래프 정점의 개수 초과\n");
    else
        vdata[vsize++] = name;
}
void insert_edge(int u, int v)
{
    GNode* n = (GNode*)malloc(sizeof(GNode));
    n->link = adj[u];
    n->id = v;
    adj[u] = n;
}

void print_graph(char* msg)
{
    int i;
    GNode* v;
    printf("%s%d\n", msg, vsize);
    for (i = 0; i<vsize; i++) {
        printf("%c  ", vdata[i]);
        
        for (v = adj[i]; v != NULL; v = v->link)
            printf("   %c", vdata[v->id]);
        printf("\n");
    }
}

void load_graph(char *filename)
{
    int i, j, val, n;
    char    str[80];
    FILE *fp = fopen(filename, "r");
    if (fp != NULL) {
        init_graph();
        fscanf(fp, "%d", &n);
        for (i = 0; i<n; i++) {
            fscanf(fp, "%s", str);
            insert_vertex(str[0]);
            for (j = 0; j<n; j++) {
                fscanf(fp, "%d", &val);
                if (val != 0)
                    insert_edge(i, j);
            }
        }
        fclose(fp);
    }
}