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

Определение всех простых путей в ориентированном графе - C++

Восстановить пароль Регистрация
 
red_square
2 / 2 / 2
Регистрация: 07.10.2013
Сообщений: 46
22.02.2014, 13:48     Определение всех простых путей в ориентированном графе #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
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
//Подключаемые стандартные заголовочные файлы
#include "stdafx.h"
#include <iostream>
#include <iomanip>
#include <fstream>
#include <windows.h>
 
//Константа, определяющая максимально доступный размер матрицы инцидентности
#define size 5
 
//Блок переменных
int i;
int j;
int counter;
int q_rows;
int q_columns;
 
//Раскрытие пространства имен std
using namespace std;
 
//Используемые функции
 
/*
//Вывод ответа в файл
void outways(void){
ofstream answer;
answer.open("Answer.txt",ios::app);
answer.close();
}*/
 
//рекурсивная функция поиска путей
void find_route(int** arr, int v){
 
int k;
int l;
int routes[size][size];
bool vertex_used[size];
 
for (k = 1; k <= q_rows; k++){
    for (l = 1; l <= q_columns; l++){                                              //проходим строку матрицы
        if (arr[k, l] == 1){                                                          //если данная вершина смежна с какой-либо другой
            for (k = 1; k <= q_rows; k++){                                     //проходим столбец матрицы  
                if ((arr[k, j] == -1) && (vertex_used[k] == false)){           //найдем, в какую вершину идет дуга из данной
                    vertex_used[k] = true;                                     //запишем,что через данную вершину уже проходили 
                    routes[i] = k;                                             //запись вершины в маршрут
                    find_route(arr, k);                                        //запустим алгоритм на новой вершине
                }
                else if (vertex_used[k] == true){                              //Если вершина УЖЕ была отмечена, перейти к поиску следующей
                    break;
                }
            }
        }
    }
}
 
//Главная функция программы
int main(int argc, char* argv[]){
//Cчитать вручную
//Ввод количества строк
cout<<"Enter number of rows : ";
cin>>q_rows;
//Ввод количества столбцов
cout<<"Enter number of columns : ";
cin>>q_columns;
 
//Динамическое выделение памяти под матрицу инцидентности
int ** m_inc = new int *[q_rows];
for(i = 0; i < q_rows; i++){
m_inc[i] = new int[q_columns];
}
 
//Считывание матрицы инцидентности
for(i = 0; i < q_rows; i++){
    for(j = 0; j < q_columns; j++){
      cin>>m_inc[i][j];
 
      //Проверка ввода матрицы инцидентности на корректность
      if ((m_inc[i][j] != 0) && (m_inc[i][j] != 1) && (m_inc[i][j] != -1)){
      cout<<"Error: The numbers you entered does not belong to a correct incedence matrix. Please repeat input.";
      abort;
      }
    }
}
 
//Вывод полученной матрицы на экран
for(i = 0; i < q_rows; i++){
      for(j = 0; j < q_columns; j++)
          cout << m_inc[i][j] << "  ";
      cout<<"\n";
}
 
//Запуск рекурсивного алгоритма поиска путей
find_route(m_inc,i);
system("pause");
return 0;
}
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
22.02.2014, 13:48     Определение всех простых путей в ориентированном графе
Посмотрите здесь:

C++ Удаление цикла в ориентированном графе
Поиск всех контуров в ориентированном графе C++
C++ Обход всех путей в графе
Нахождение всех путей в графе от одной вершины до другой обходом в ширину C++
Поиск всех различных путей в графе C++
C++ Ранжирование вершин на ориентированном графе без контуров по отношению к вершине
C++ Алгоритм поиска в глубину в ориентированном графе

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

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

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