-
Notifications
You must be signed in to change notification settings - Fork 266
/
HamiltonianCycle.c
143 lines (125 loc) · 4.4 KB
/
HamiltonianCycle.c
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
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
/*
*
* Grafos - CICLO HAMILTONIANO em C
*
* -----------------------------------
* | |
* (A)---------------(B)-------------(E)---------------(F)
* | | | |
* | | | |
* | | | |
* (C)---------------(D)--------------- |
* | |
* -----------------------------------
*
* 6 Vértices
* 9 Arestas
*/
#include <malloc.h>
#include <stdio.h>
#define MAX_VERTICES \
6 // MÁXIMO DE VÉRTICES DO GRAFO, SE FOR ALTERAR O GRAFO PRECISA ALTERAR ESTA
// VARIÁVEL TAMBÉM
#define MAX_ARESTAS \
(MAX_VERTICES * \
(MAX_VERTICES - \
1)) // CALCULA O NÚMERO MÁXIMO DE ARESTAS QUE O GRAFO PODERÁ TER
// Estrutura que define cada Vértice do Grafo
typedef struct NO {
char id;
int nroVizinhos;
struct NO *vizinhos[MAX_ARESTAS];
bool visitado;
} *VERTICE;
VERTICE solucao[MAX_VERTICES]; // Array que irá guardar a solução do ciclo
// hamiltoniano
// Cria Vértice e retorna
VERTICE criaVertice(char id) {
VERTICE novoVertice = (VERTICE)malloc(sizeof(NO)); // Aloca um novo Vértice
novoVertice->id = id;
novoVertice->nroVizinhos = 0;
novoVertice->visitado = false;
for (int i = 0; i < MAX_ARESTAS; i++) {
novoVertice->vizinhos[i] = NULL;
}
return novoVertice;
}
// Liga os vértices passados como parâmetro
bool ligaVertices(VERTICE v1, VERTICE v2) {
int aux = 0;
while (v1->vizinhos[aux] !=
NULL) { // Busca a primeira posição 'vazia'(NULL) dos vizinhos
aux++;
}
v1->vizinhos[aux] = v2; // Adiciona o novo vizinho a lista de vizinhos
aux = 0;
while (v2->vizinhos[aux] !=
NULL) { // Busca a primeira posição 'vazia'(NULL) dos vizinhos
aux++;
}
v2->vizinhos[aux] = v1; // Adiciona o novo vizinho a lista de vizinhos
v1->nroVizinhos++; // Incrementa o número de vizinhos
v2->nroVizinhos++; // Incrementa o número de vizinhos
}
bool cicloHamiltonianoAuxiliar(int aux) {
if (aux == MAX_VERTICES) {
for (int i = 0; i < solucao[aux - 1]->nroVizinhos; i++) {
if (solucao[aux - 1]->vizinhos[i] == solucao[0]) {
return true;
}
}
return false;
}
VERTICE s = solucao[aux - 1]; // Auxiliar para simplificar o código
for (int i = 0; i < s->nroVizinhos;
i++) { // Percorre todos os vizinhos do vértice de posição aux-1 no array
// solução
if (s->vizinhos[i]->visitado == false) {
s->vizinhos[i]->visitado = true;
solucao[aux] = s->vizinhos[i];
if (cicloHamiltonianoAuxiliar(aux + 1) == true) {
return true;
}
s->vizinhos[i]->visitado = false;
}
}
return false;
}
bool cicloHamiltoniano(VERTICE grafo[MAX_VERTICES]) {
grafo[0]->visitado = true; // Marca a posição inicial como visitada
solucao[0] = grafo[0]; // Array que irá guardar a solução do ciclo
return cicloHamiltonianoAuxiliar(1);
}
int main() {
// Grafo conjunto de vértices em um array
VERTICE GRAFO[MAX_VERTICES];
GRAFO[0] = criaVertice('A');
GRAFO[1] = criaVertice('B');
GRAFO[2] = criaVertice('C');
GRAFO[3] = criaVertice('D');
GRAFO[4] = criaVertice('E');
GRAFO[5] = criaVertice('F');
// Liga todos os vértices de acordo com o GRAFO apresentado na introdução
ligaVertices(GRAFO[0], GRAFO[1]); // A - B
ligaVertices(GRAFO[0], GRAFO[2]); // A - C
ligaVertices(GRAFO[1], GRAFO[3]); // B - D
ligaVertices(GRAFO[2], GRAFO[3]); // D - C
ligaVertices(GRAFO[1], GRAFO[4]); // B - E
ligaVertices(GRAFO[3], GRAFO[4]); // D - E
ligaVertices(GRAFO[4], GRAFO[5]); // E - F
ligaVertices(GRAFO[3], GRAFO[5]); // D - F
ligaVertices(GRAFO[1], GRAFO[5]); // B - F
for (int i = 0; i < MAX_VERTICES; i++) {
solucao[i] = criaVertice('0');
}
if (cicloHamiltoniano(GRAFO)) {
printf("Ciclo Hamiltoniano:\n");
for (int i = 0; i < MAX_VERTICES; i++) {
printf("%c, ", solucao[i]->id);
}
printf("\n\n");
} else {
printf("Nao possui Ciclo Hamiltoniano\n");
}
return 0;
}