|
5-laboratoriya ishi Bajardi: Abdumalikov Nurdaulet Tekshirdi: Begimov O’ktam
|
| Sana | 25.12.2023 | | Hajmi | 1,19 Mb. | | #128251 |
Bog'liq algo5 127465
O’ZBEKISTON RESPUBLIKASI AXBOROT TEXNOLOGIYALARI VA KOMMUNIKATSIYALARINI RIVOJLANTIRISH VAZIRLIGI
MUHAMMAD AL-XOZAZMIY NOMIDAGI TOSHKENT AXBOROT TEXNOLOGIYALARI UNIVERSITETI
Algoritmlarni loyihalash
5-laboratoriya ishi
Bajardi:Abdumalikov Nurdaulet
Tekshirdi: Begimov O’ktam
5 - laboratoriya ishi
4-laboratoriya ishida tuzilgan graf uchun “Shajara” daraxti tuzilsin. Bunda orqaga qaytish algoritmidan foydalanilsin.
Tuzilgan shajara daraxtidan Gamilton siklini berishi mumkin bo‘lgan yo‘nalish variantlari ajratilsin.
3. Berilgan graf uchun “kommivoyajer masalasi” uchun tafsiya qilinadigan marshrut va uning narxi topilsin
Gamilton sikli algoritmi:
package hamilton;
class Hamilton {
final int V = 5;
int path[];
boolean isSafe(int v, int graph[][], int path[], int pos) {
if (graph[path[pos - 1]][v] == 0)
return false;
for (int i = 0; i < pos; i++)
if (path[i] == v)
return false;
return true;
}
boolean hamCycleUtil(int graph[][], int path[], int pos) {
if (pos == V) {
if (graph[path[pos - 1]][path[0]] == 1)
return true;
else
return false;
}
for (int v = 1; v < V; v++) {
if (isSafe(v, graph, path, pos)) {
path[pos] = v;
if (hamCycleUtil(graph, path, pos + 1) == true)
return true;
path[pos] = -1;
}
}
return false;
}
int hamCycle(int graph[][]) {
path = new int[V];
for (int i = 0; i < V; i++)
path[i] = -1;
path[0] = 0;
if (hamCycleUtil(graph, path, 1) == false) {
System.out.println("\nSolution does not exist");
return 0;
}
printSolution(path);
return 1;
}
void printSolution(int path[]) {
System.out.println("Solution Exists: Following" +
" is one Hamiltonian Cycle");
for (int i = 0; i < V; i++)
System.out.print(" " + path[i] + " ");
System.out.println(" " + path[0] + " ");
}
public static void main(String args[]) {
Hamilton hamiltonian =
new Hamilton();
/* (0)--(1)--(2)
| / \ |
| / \ |
| / \ |
(3)-------(4) */
int graph1[][] = {{0, 1, 0, 1, 0},
{1, 0, 1, 1, 1},
{0, 1, 0, 0, 1},
{1, 1, 0, 0, 1},
{0, 1, 1, 1, 0},
};
hamiltonian.hamCycle(graph1);
/*
(0)--(1)--(2)
| / \ |
| / \ |
| / \ |
(3) (4) */
int graph2[][] = {{0, 1, 0, 1, 0},
{1, 0, 1, 1, 1},
{0, 1, 0, 0, 1},
{1, 1, 0, 0, 0},
{0, 1, 1, 0, 0},
};
hamiltonian.hamCycle(graph2);
}
}
|
| |
