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
| #include <iostream>
#include <sstream>
#include <iomanip>
#include <fstream>
#include <vector>
#include <conio.h>
using namespace std;
//обход в ширину
void bfs(vector<vector<int>> &way,int **m,int v,int r,int bgn,int end)
{
int *f=new int[v];//проверки ребер от вершины
for(int i=0; i<v; i++)
f[i]=-1;//сбросили флаги
vector<int> q;//очередь
q.push_back(bgn);//начало
do
{
bgn=q.back();
for(f[bgn]++; f[bgn]<r; f[bgn]++)//пошли по ребрам
if(m[bgn][f[bgn]]==1)//начало пути
{
int k;
for(k=0; k<v; k++)//вниз по столбцу, ищем конец
if(m[k][f[bgn]]==-1 &&(f[k]<0 || k==end))//нашли
{
q.push_back(k);//вершину в очередь
if(k==end)//конечная точка
{
way.push_back(q);//сохранили путь
q.pop_back();//убрали вершину из очереди
}
break;
}
if(k<v) break;//нашли ребро
}
if(f[bgn]>=r)//проверили все ребра
{
f[bgn]=-1;//сбросили флаг вершины
q.pop_back();//убрали вершину из очереди
}
}while(!q.empty());//пока есть путь,его часть
delete[] f;
}
int main()
{
string name="f.txt";
cout<<"File: ";
getline(cin,name);//имя файла
ifstream f(name.c_str());//файл
if(f.is_open())//есть такой файл
{
setlocale(LC_ALL,"Rus");
int v,r;//вершины,ребра
f>>v>>r;//размер
f.get();
cout<<"Граф ориентированный,вершин: "<<v<<",ребра: "<<r<<"\n";
string s;
int **m=new int*[v];
int i=0;
while(f.peek()>0)//пока файл не кончился
{
getline(f,s);//строка
istringstream ss(s);
m[i]=new int[r];
for(int k=0; ss>>s; k++)
{
m[i][k]=atoi(s.c_str());
cout<<setw(4)<<m[i][k];
}
cout<<endl;
i++;
}
f.close();//закрыли файл
cout<<endl;
for(int i=0; i<v; i++)
for(int k=0; k<r; k++)
if(m[i][k]==1)
for(int j=0; j<v; j++)
if(m[j][k]==-1)
cout<<i<<"->"<<j<<endl;
int bgn=1,end=4;
cout<<"\nНачальная и конечная вершины: ";
cin>>bgn>>end;
vector<vector<int>> way;
bfs(way,m,v,r,bgn,end);
cout<<endl;
if(way.size())
for(int i=0; i<(int)way.size(); i++)
{
for(int k=0; k<(int)way[i].size(); k++)
{
if(k) cout<<"->";
cout<<way[i][k];
}
cout<<endl;
}
else cout<<"Путей нет!\n";
for(int i=0; i<v; i++)
delete[] m[i];
delete[] m;
}
else
cout<<"File not found!\n";
system("pause");
return 0;
} |
(
