Форум программистов, компьютерный форум CyberForum.ru

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

Восстановить пароль Регистрация
 
Рейтинг: Рейтинг темы: голосов - 9, средняя оценка - 4.67
GrizliK91
 Аватар для GrizliK91
1 / 1 / 0
Регистрация: 27.02.2011
Сообщений: 13
23.12.2011, 21:34     Гамильтонов путь #1
Доброго времени суток.
Дали мне задачку: Граф ориентированный. Определить, есть ли гамильтонов путь из заданной вершины в другую заданную. Если есть, напечатать его.

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();
}
Проблема в том что он по сути не выводит гамильтонов путь, он вывод короткий путь от одной вершины к другой.
Не могу понять что надо исправить
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
23.12.2011, 21:34     Гамильтонов путь
Посмотрите здесь:

Гамильтонов цикл C++
C++ Путь
Гамильтонов цикл в графе C++
C++ коротчайший путь
C++ Гамильтонов цикл в графе с выполненным условием Дирака
путь фишки C++
C++ Графы. Гамильтонов Цикл. Матрица смежности
Путь символа C++

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

Или воспользуйтесь поиском по форуму:
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Ответ Создать тему
Опции темы

Текущее время: 16:11. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru