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

Найти все пути между двумя любыми вершинами в графе - C++

Восстановить пароль Регистрация
 
Рейтинг: Рейтинг темы: голосов - 24, средняя оценка - 4.92
dragon_ice
0 / 0 / 0
Регистрация: 21.05.2013
Сообщений: 3
04.06.2013, 19:38     Найти все пути между двумя любыми вершинами в графе #1
Пожалуйста, очень нужна помощь. Найти все пути между двумя любыми вершинами в графе. В выводе ошибка. Помогите исправить спасибо.
Вложения
Тип файла: rar K.rar (1.86 Мб, 36 просмотров)
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
04.06.2013, 19:38     Найти все пути между двумя любыми вершинами в графе
Посмотрите здесь:

Поиск самых коротких расстояний между любыми двумя вершинами графа по методу Шимбела C++
C++ Поиск кратчайших путей между двумя вершинами графа методом Шимбела.
C++ Построить алгоритм поиска кратчайшего пути между двумя вершинами в графе
Нужно определить количество путей между двумя вершинами C++
Граф - существует ли связь между двумя вершинами в обоих направлениях C++
C++ Найти все пути шахматного коня между двумя заданными полями, не содержащие повторяющихся полей
Найти вероятность существования пути в графе между заданными точками C++
C++ Графы, нахождение наименьшего пути между вершинами обходом в ширину

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

Или воспользуйтесь поиском по форуму:
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
dragon_ice
0 / 0 / 0
Регистрация: 21.05.2013
Сообщений: 3
04.06.2013, 19:47  [ТС]     Найти все пути между двумя любыми вершинами в графе #2
Код в архиве:
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
#include "stdafx.h"
#include <iostream>
#include <conio.h>
#include <fstream>
#include <iomanip>
using namespace std;
int **graph; //матрица смежности
int *ways; // путь
bool *include; //включена ли точка в путь
int s, f, iskomaya, i, j, N, start, finish; // s - точка, из которой делается шаг, f - конечная точка, iskomaya - номер и скомой точки маршрута, N - количество вершин в графе, start и finish -начальная и конечная точки
void poisk(int s,  int f, int iskomaya);
void main(){
    setlocale(LC_ALL, "Russian");
    cout<< "Введите количество элементов массива N="; cin>>N; cout<< endl;
    graph=new int *[N];
    for(int i=0; i<N; i++)
        graph[i]=new int [N];
    cout<< "Введите элементы массива: 1-если вершины смежны, 0 - если вершины не смежны"; cout<< endl;
    for(i=0; i<N; i++)
        for(j=0; j<N; j++) cin>> graph[i][j];
    for(i=0; i<N; i++){
        for(j=0; j<N; j++) cout<< setw(4) << graph[i][j] << " "; cout<< endl;
    }
 
    ways=new int[N];
    for(i=0; i<N; i++){
        ways[i]=0;
    }
    include=new bool [(bool)N];
    for(i=0; i<N; i++){
        include[i]=0;
    }
    cout<<"Введите первую вершину поиска(от которой будем искать)"; cin>>start; cout<< endl;
    if(start==N || start>N){
        cout<<"Введите первую вершину поиска(от которой будем искать)"; 
        cin>>start;
    }
    
    cout<<"Введите вторую вершину поиска(путь до которой нужно найти)"; cin>>finish; cout<< endl;
    if(finish==0 || finish>N){
        cout<<"Введите вторую вершину поиска(путь до которой нужно найти)";  
        cin>>finish;
    }
    ways[0]=start;
    include[start]=true;
    poisk(start, finish, 1);
 
 
 
}
 
void poisk(int s,  int f, int iskomaya){
    int tek; // точка, в которую делается шаг
    if(s==f){
        for(i=0; i<iskomaya; i++){
            cout<<ways[i]<<" "; 
            //cout<<endl;
        }
    }
    else
        for(tek=0; tek<N; tek++){
            if((graph[s][tek]==1 || graph[tek][s]==1)&&(!include[tek])){
                ways[iskomaya]=tek;
                include[tek]=true;
                poisk(tek, f, iskomaya+2);
                include[tek]=false;
                ways[iskomaya]=0;
            }
        }
        //cout<<ways[i]<<" "; cout<<endl;
 
}
Yandex
Объявления
04.06.2013, 19:47     Найти все пути между двумя любыми вершинами в графе
Ответ Создать тему
Опции темы

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