인접리스트

Graph.h

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
#ifndef GRAPH_H
#define GRAPH_H
#include <iostream>
 
using namespace std;
 
enum VisitMode { Visited , NotVisited};
 
 
// 정점 구조체
typedef struct tagVertex
{
    int Data; // 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;
 
Graph* CreateGraph();
void DestroyGraph(Graph* G);
 
Vertex* CreateVertex(int 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
Colored by Color Scripter
cs

G

Graph.cpp

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
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
#include "Graph.h"
 
 
Graph* CreateGraph()
{
    Graph* graph = new Graph;
    graph->Vertices = NULL;
    graph->VertexCount = 0;
    return graph;
}
 
void DestroyGraph(Graph* G)
{
    while(G->Vertices != NULL)
    {
        Vertex* Vertices = G->Vertices;
        DestroyVertex(G->Vertices);
        G->Vertices = Vertices;
    }
    delete G;
}
Vertex* CreateVertex(int Data)
{
    Vertex* V = new Vertex;
    V->Data = Data;
    V->Next = NULL;
    V->AdjacencyList = NULL;
    V->Visited = NotVisited;
    V->Index;
 
    return V;
}
void DestroyVertex(Vertex* V)
{
    while(V->AdjacencyList!=NULL)
    {
        Edge* edge = V->AdjacencyList->Next;
 
        DestroyEdge(V->AdjacencyList);
 
        V->AdjacencyList = edge;
    }
    delete V;
}
 
Edge* CreateEdge(Vertex* From, Vertex* Target, int Weight)
{
    Edge* E = new Edge;
    E->From = From;
    E->Target = Target;
    E->Next = NULL;
    E->Weight = Weight;
 
    return E;
}
 
void DestroyEdge(Edge * E)
{
    delete 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)
    {
        cout<<V->Data;
        if((E= V->AdjacencyList) == NULL)
        {
            V = V->Next;
            cout<<endl;
            continue;
        }
        while(E!= NULL)
        {
            cout<<E->Target->Data<<" "<<E->Weight;
            E->Next;
        }
        cout<<endl;
 
        V=V->Next;
    }
    cout<<endl;
 
}
 
 
 
Colored by Color Scripter
cs

황소

인접리스트

티스토리툴바