Форум программистов, компьютерный форум, киберфорум
Наши страницы
С++ для начинающих
Войти
Регистрация
Восстановить пароль
 
GrizliK91
1 / 1 / 1
Регистрация: 27.02.2011
Сообщений: 13
1

Гамильтонов путь

23.12.2011, 21:34. Просмотров 1704. Ответов 0
Метки нет (Все метки)

Доброго времени суток.
Дали мне задачку: Граф ориентированный. Определить, есть ли гамильтонов путь из заданной вершины в другую заданную. Если есть, напечатать его.

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
#include "stdafx.h"
#include "stdio.h"
#include "conio.h"
int graph[100][100];
int label[100];
int fifo[100];
int way[100];
int i,j,p,k,n,q,d,f,m,cur,first,end;
 
void main()
{
    printf("Input amount of tops: \t");
    scanf("%d",&n);
    printf("\nInput amount of ribs: \t");
    scanf("%d",&m);
    for (i=0;i<n;i++)
        for (j=0;j<n;j++)
            graph[i][j]=0;
    for (k=0;k<m;k++)
    {
        printf("\nInput connection between two tops [i][j]: "); // Ввод связей графа
        scanf("%d" "%d",&i,&j);
        graph[i][j]=1;
    }
    for (k=0;k<n;k++)
    {
        fifo[k]=0;
        label[k]=0;
    }
    for (i=0;i<n;i++)
    {printf("\n");
        for (j=0;j<n;j++)
            printf("%d ",graph[i][j]);
    }
    getch();
    printf("\nStart top: ");
    scanf("%d", &first);
    printf("\nEND top: ");
    scanf("%d", &end);
    label[first]=1;
    p=0;k=1;f=0;q=0;
    fifo[p]=first;
    while((p!=k)&&(f!=1))
            {
                cur=fifo[p];
                if (cur == end)
                {   
                    f=1;
                    way[q]=end;
                }
                else
                {
                p++;
                d=0;
                for (i=0;i<n;i++)
                { 
                    if ((graph[cur][i]==1)&&(label[i]==0))
                    {
                        fifo[k]=i;
                        k++;
                        label[i]=label[cur]+1;
                        d++;
                }
                }
                if (d!=0)
                {
                    way[q]=cur;
                    q++;
                }
                }
            }
    if(f==0)
        printf("No solution");
    else
        for (i=0;i<=q;i++)
            printf("%d ", way[i]);
    getch();
}
Проблема в том что он по сути не выводит гамильтонов путь, он вывод короткий путь от одной вершины к другой.
Не могу понять что надо исправить
0
QA
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
23.12.2011, 21:34
Ответы с готовыми решениями:

Гамильтонов цикл
надо разобрать прогу.выявления Гамильтонова цикла в графе...

Гамильтонов цикл в графе
Нужно написать функцию нахождения гамильтонова цикла в графе. Цикл ищется по матрице смежности...

Гамильтонов Цикл (из Delphi в C++)
Здравствуйте дорогие форумчане! Прошу прощение за беспокойство.Сразу к сути. Мне необходимо...

Графы. Гамильтонов Цикл. Матрица смежности
Вот программа, которую я взял с поиска. Программа должна найти Гамильтонов цикл. #include...

Гамильтонов цикл в графе с выполненным условием Дирака
:Задача 1 . SMS счастья Имя входного файла: input.txt Имя выходного файла: output.txt ...

0
Answers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
23.12.2011, 21:34

Гамильтонов путь
Опишите пожалуйста словесный алгоритм нахождения гамильтоного пути в орграфе. =) ошибочка! просто...

Гамильтонов путь в графе
Доброго времени форумчане! В прологе, откровенно говоря, я чайник. Пытаюсь разобраться. В задании...

Гамильтонов путь, критерии существования
Есть ли какие-то критерии существования гамильтонова пути (не цикла)? Для цикла знаю, но мне нужен...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
1
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2019, vBulletin Solutions, Inc.
Рейтинг@Mail.ru