0 / 0 / 0
Регистрация: 05.12.2016
Сообщений: 7
1

Найти все пути в графе от одной вершины в другую

13.12.2016, 14:25. Показов 2977. Ответов 0
Метки нет (Все метки)

Author24 — интернет-сервис помощи студентам
Нуждаюсь в помощи. Пытаюсь на основе поиска в ширину(BFS) найти все пути от одной вершины в другую. Программа выводит часть путей. У меня есть вектор для восстановления пути(одномерный), не могу понять можно ли вообще одномерным вектором восстановить все пути? Оставляю свой код, может кто-нибудь поможет советом...

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
void BFS(int size, int arr[MAX][MAX])
{
 
    int start, cur, fin, key;
    char txt_name1[14];
    int *pyti = new int[size+1];
    vector<int> predki(size+1, -1);
    
        bool *used = new bool[size+1];
    bool *inque = new bool[size+1];
        for(int i=1; i<=size; i++)
            used[i] = inque[i] = false;
 
    cout<<"Где вы? ";
    cin>>start;
    cout<<"Куда летим? ";
    cin>>fin;
    
    cout<<"\n\nВыберите режим получения ответа(нахождение всех путей от пункта "<<start<<" до пункта "<<fin<<")"<<endl;
    cout<<"1: Автоматический\n2: Поэтапный вывод в файл"<<endl;
    cin>>key;
 
    if (key!=1 && key!=2)
    {
        cout<<"Введите корректное значение!: ";
        cin>>key;
    }
    
    /*cout<<"Введите имя файла для записи данных: ";
    cin>>txt_name1;*/
    ofstream fout("output.txt");
    
    if (key==1 || key==2)
    {
        used[start]=true;
        inque[start]=true;
        pyti[start]=0;
        q_beg= new Que;
        q_beg->next=NULL;
        q_beg->info=start;
        q_end=q_beg;    
 
        while(!EmptyQ(q_beg))
        {
            cur=q_beg->info;
            cout<<"\ncur "<<cur;
            if (cur != fin) inque[cur]=true;
            cout<<" inque "<<inque[cur];
            DelQ(&q_beg);
            
 
            for (int i=1; i<=size; i++)
            {
                if (arr[cur][i]==1)
                {
                    if (!inque[i])
                        {
                            pyti[i] = pyti[cur] + 1;
                            if (i!=fin) AddQ(&q_beg, &q_end, i);
                            used[i] = true; 
                            predki[i] = cur;
                        }
            
                    //if (used[fin]==true)
                    //{
                /*cout<<"\npyti ";
                for(int a=1; a<=size; a++)
                    cout<<" "<<pyti[a];*/
                cout<<"\npredki ";
                for(int a=1; a<=size; a++)
                    cout<<" "<<predki[a];
                
                
                    int k = i;
                    vector<int> path;
                    //for (int j=1;j<=pyti[i];j++)                          
                    //{
                        while (predki[k]!=-1)
                            {
                            path.push_back(k);
                            k = predki[k];
                            //cout<<"\nk= "<<k;
                        }
                    //}
            
                    path.push_back(k);
                    cout<<"\nПуть: ";
                    for(int j = path.size()-1; j >=0; j--)
                    {
                        cout << path[j] << ' ';
 
                    }
                    used[fin]=false;
                    //predki[i] = cur;  
                    }
                }
            }
        }
        //if (predki[fin]==-1) cout<<"\nМаршрута из города "<<start<<" в город "<<fin<<" нет!"<<endl;
        cout<<"\n";
    }
    fout.close();
}
0
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
13.12.2016, 14:25
Ответы с готовыми решениями:

Все простые пути на графе, ведущие от одной вершины к другой
Напишите программу, на входе которой вводятся две его вершины. Программа должна распечатывать все...

Найти на графе все пути длиной два, соединяющие вершины 1 и 2.
Ребят! Помогите срочно! Такой вопрос по графам: Дана матрица смежности A. По ней построен граф....

кратчайшие пути из одной заданной вершины графа в другую
Найти, если возможно, кратчайшие пути из одной заданной вершины в другую и наоборот. ...

Найти все вершины графа, к которым от заданной вершины можно добраться по пути не длиннее А
Найти все вершины графа, к которым от заданной вершины можно добраться по пути не длиннее А....

0
13.12.2016, 14:25
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
13.12.2016, 14:25
Помогаю со студенческими работами здесь

Подсчитать все пути длины 3 по ребрам единичного трехмерного куба, входящие из одной вершины
Подсчитать все пути длины 3 по ребрам единичного трехмерного куба, входящие из одной вершины....

В заданном графе найдите все вершины, растояние от которых до заданной вершины равно 2
гласит так: &quot;В заданном графе найдите все вершины, растояние от которых до заданной вершины равно...

Нахождение кратчайшего пути в неорентированном графе от заданой вершины к заданной
Добрый день. Вот решаю задачку о кратчайщем расстояние между двумя верщинами в неорентированном...

Найти все пути между двумя любыми вершинами в графе
Пожалуйста, очень нужна помощь. Найти все пути между двумя любыми вершинами в графе. В выводе...


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

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

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2024, CyberForum.ru