자료구조 with C/그래프

그래프 기초

4gats 2023. 2. 16. 14:49

그래프는 정점과 간선으로 이루어진다

정점 사이의 인접 관계를 나타내는 방법에는

인접 행렬과 인접 리스트가 있다

 

인접 행렬을 이용하면 정점 간의 인접 여부를 빠르게 알 수 있다.

BUT! 메모리의 양이 정점의 크기 * N^2만큼 커진다

 

인접 리스트는 정점 간의 인접 여부를 알기 위해 리스트를 타고 순차 탐색을 해야한다..

BUT! 정점과 간선의 삽입이 빠르고 인접 관계를 표시하는 리스트에 사용되는 메모리 양이 적다.

한 정점과 연결된 모든 간선을 찾는 시간 O(차수)

 

結論！프로그램의 목적에 따라 결정하자

 

인접 리스트

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
typedef struct tagVertex
{
    VElementType       Data;
    int               Visited;       // 순회 알고리즘에서 사용
    int               Index;         // 정점의 인덱스
 
    struct tagVertex* Next;          // 다음 정점을 가리키는 포인터
    struct tagEdge*   AdjacencyList; // 인접 정점의 목록
} Vertex;
 
typedef struct tagEdge
{
    int    Weight;             // 간선의 가중치
    struct tagEdge* Next;      // 다음 간선을 가리키는 포인터
    Vertex* From;              // 간선의 시작 정점
    Vertex* Target;            // 간선의 끝 정점
} Edge;
 
typedef struct tagGraph
{
    Vertex* Vertices;
    int     VertexCount;
} Graph;
 cs

 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
Graph* CreateGraph()
{
    Graph* graph = (Graph*)malloc( sizeof( Graph ) );
    graph->Vertices = NULL;
    graph->VertexCount = 0;
 
    return graph;
}
 
Vertex* CreateVertex( VElementType Data )
{
    Vertex* V = (Vertex*)malloc( sizeof( Vertex ) );
    
    V->Data = Data;
    V->Next = NULL;
    V->AdjacencyList = NULL;
    V->Visited = NotVisited;
    V->Index = -1;
 
    return V;
}
 
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++;
}
 
Edge*   CreateEdge( Vertex* From, Vertex* Target, int Weight )
{
    Edge* E   = (Edge*)malloc( sizeof( Edge ) );
    E->From   = From;
    E->Target = Target;
    E->Next   = NULL;
    E->Weight = Weight;
 
    return E;
}
 
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");
}
 
 cs

 

 

 

그래프 생성                 Graph* G = CreateGraph();

정점 생성                   Vertex* V1 = CreateVertex('1')

그래프에 정점을 추가         AddVertext( G, V1);

정점과 정점을 간선으로 잇기  AddEdge (V2, CreateEdge(V1, V2, 0) );

 

PrintGraph 결과

1 : 2[0] 3[0] 4[0] 5[0]