Форум программистов, компьютерный форум, киберфорум
Наши страницы

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
red_square
2 / 2 / 2
Регистрация: 07.10.2013
Сообщений: 48
#1

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

22.02.2014, 13:48. Просмотров 627. Ответов 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
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;
}
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
22.02.2014, 13:48
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Определение всех простых путей в ориентированном графе (C++):

Класс для поиска простых контуров на ориентированном графе - C++
Ребят, помогите прогу написать :gsorry: завтра сдавать, а я не знаю ничего совсем :gsorry::gcray: Класс для поиска простых контуров на...

Поиск всех контуров в ориентированном графе - C++
Нужно найти все контуры. Контур - путь, у которого начало и конец совпадают. Т.е. например (1;5)(5;2)(2;4)(4;1). Имею вектор с...

Обход всех путей в графе - C++
Помогите с алгоритмом поиска всех путей на графе.Обыскал весь инет робочего не нашол

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

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

Поиск циклов в ориентированном графе - C++
Доброго времени суток. Может кому-нибудь из вас не составит особого труда, или возможно кто-то писал похожую программу. В общем, я написал...

0
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
22.02.2014, 13:48
Привет! Вот еще темы с ответами:

Удаление цикла в ориентированном графе - C++
Помогите реализовать такой вот алгоритм: Задан ориентированный граф. Необходимо найти и удалить из него все циклы. Пример графа: 1 2 ...

Алгоритм поиска в глубину в ориентированном графе - C++
Добрый вечер,форумчане:) Знаю, что подобная тема встречалась тут довольно часто, но у меня все-таки возник вопрос ответ на который я не...

Ранжирование вершин на ориентированном графе без контуров по отношению к вершине - C++
Помогите сделать алгоритм по данному коду. Задание: Написать и исследовать программу, осуществляющюю ранжирование вершин на ориентированном...

Используя метод поиска в ширину, найти и вывести путь в ориентированном графе между двумя вершинами - C++
Ребята день добрый. Задание у меня вот такое: Используя метод поиска в ширину, найти и вывести путь в ориентированном графе между...


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

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

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