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

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

Войти
Регистрация
Восстановить пароль
 
Lotus34
5 / 6 / 1
Регистрация: 26.10.2012
Сообщений: 124
#1

Поиск отрицательных циклов в графе - C++

07.12.2014, 13:43. Просмотров 314. Ответов 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
//Дан ориентированный граф без кратных ребер и петель. Каждое ребро имеет вес,
//выражающийся целым числом (возможно, отрицательным). Определить, имеются ли 
//у него циклы отрицательного веса.  
 
#include <iostream>
#include <Windows.h>
 
using namespace std;
const int n=5;
bool *visited=new bool[n];
int i, j;
//матрица смежности графа
int graph[n][n] =
{{0, 1, 0, 0, 0},
{0, 0, -3, 0, 0},
{0, 0, 0, 6, 2},
{-4, 0, 0, 0, 0},
{0, 0, 0, -1, 0}
};
int t=0;
int mas[n];
void DFS(int st)
{
int d;
d=0;
int r;
cout<<st+1<<" ";
mas[t]=st+1;
t++;
visited[st]=true;
for (r=0; r<=n; r++)
if ((graph[st][r]!=0) && (!visited[r]))
{
//d=d+graph[st][r];
//cout<<d<<" ";
DFS(r);
}
}
 
 
void main()
{
setlocale(LC_ALL, "Rus");
int start;
cout<<"Матрица смежности графа: "<<endl;
for (i=0; i<n; i++)
{
visited[i]=false;
for (j=0; j<n; j++)
cout<<" "<<graph[i][j];
cout<<endl;
}
cout<<"Стартовая вершина >> "; cin>>start;
//массив посещенных вершин
bool *vis=new bool[n];
cout<<"Порядок обхода: ";
DFS(start-1);
delete []visited;
cout<<"\n";
 
 
 
 
system("pause>>void");
}
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
07.12.2014, 13:43
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Поиск отрицательных циклов в графе (C++):

Поиск циклов в графе. Поиск центра взвешенного графа - C++
В интернете, к сожалению, по этим вопросам не так уж много нашел. Можете посоветовать статью/пособие, где было бы подробно об этом написано?

Поиск циклов в графе - C++
Как узнать что граф имеет цикл?

Поиск Ф-циклов в графе - C++
Нужно вывести на печать все фундаментальные циклы графа. Мой код выводит правильно(судя по данному примеру),но помоему он не разделяет сами...

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

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

Поиск всех циклов в неориентированном графе. - C++
На входе программа принимает номера вершин и вес ребра между ними. Например: 2 3 1 - между вершинами 2 и 3 есть ребро весом 1. Нужно...

1
Lotus34
5 / 6 / 1
Регистрация: 26.10.2012
Сообщений: 124
09.12.2014, 17:13  [ТС] #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
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
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
//Дан ориентированный граф без кратных ребер и петель. Каждое ребро имеет вес,
//выражающийся целым числом (возможно, отрицательным). Определить, имеются ли 
//у него циклы отрицательного веса.  
 
#include <iostream>
#include <Windows.h>
 
using namespace std;
const int n=5;
bool *visited=new bool[n];
int i, j;
//матрица смежности графа
int graph[n][n] =
{{0, 1, 0, 0, 0},
{0, 0, -3, 0, 0},
{0, 0, 0, 6, 2},
{-3, 0, 0, 0, 0},
{0, 0, 0, -1, 0}
};
int t=0;
int mas[n];
void DFS(int st)
{
int d;
d=0;
int r;
cout<<st+1<<" ";
mas[t]=st+1;
t++;
visited[st]=true;
for (r=0; r<=n; r++)
if ((graph[st][r]!=0) && (!visited[r]))
{
//d=d+graph[st][r];
//cout<<d<<" ";
DFS(r);
}
 
}
 
 
void main()
{
    
setlocale(LC_ALL, "Rus");
int start,r,k;
int cicle[n],summ=0;
 
cout<<"Матрица смежности графа: "<<endl;
 
for (i=0; i<n; i++)
{
 
visited[i]=false;
for (j=0; j<n; j++)
cout<<" "<<graph[i][j];
cout<<endl;
 
}
cout<<"Стартовая вершина >> "; cin>>start;
//массив посещенных вершин
bool *vis=new bool[n];
cout<<"Порядок обхода: ";
DFS(start-1);
delete []visited;
cout<<"\n";
int first=0,tmp;
 
 
for(i=0;i<n;i++)
{
    tmp=i;
    cicle[0]=first;
    r=1;k=0;
    
    for(j=0;j<n;)
    {
 
        for(j=0;j<n;j++)
            {
 
                    if(graph[i][j]!=0)
                        {
                        if(i==j)
                        {
                        cout<<"Встречена петля!";
                        exit(1);
                        }
                        else
                        {
                        summ+=graph[i][j];
                        i=j;
                
                        if(i!=first)
                        {
                        cicle[r]=i;
                        r++;
        
                        }
                        else if (summ<=0)///////////*****/*/*/*/*/*/*/*/
                        {
 
                            for(r=0;r<n;r++)
                            {
                                cout<<cicle[r];
                                cicle[r]=NULL;
                            }
                            r=0;k=1;                    
                            first++;    i=tmp;
                        }
                        else
                        {
                            for(r=0;r<n;r++)
                            {
                                cicle[r]=NULL;
                            }
                            summ=0;r=0;k=1;first++; i=tmp;              
                        }
                        }
 
                    break;  
                    }           
            }
 
        if(k=1) break;
        
        }
    }
 
 
 
 
 
 
system("pause>>void");
}
0
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
09.12.2014, 17:13
Привет! Вот еще темы с ответами:

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

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

Поиск на графе - C++
Доброго времени суток. Мне не совсем понятна реализация в коде поиска на графе в высоту и ширину. Т.к. в книге они описаны не совсем...

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


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

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

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