Обход графа в ширину и глубину

Лабораторная работа №6

Тема: Обход графа в ширину и глубину.

Задание:

Сделать обход графа в глубину и ширину.

Код программы:

#include
#include
#include
#include
using namespace std;
bool used[6];
void DFS(int st, vector < vector > mas)
{
int r;
cout « st + 1 « " ";
used[st] = true;
for (r = 0; r < mas[st].size(); r++)
if ((mas[st][r] != 0) && (!used[r]))
DFS(r, mas);
}
int main()
{
for (int i(0); i < 6; i++)
used[i] = false;
setlocale(0, "");
ifstream f("graph.txt");
int n = 0, m = 0;
f » n;
f » m;
vector < vector > mas(n);
for (int i = 0; i < n; i++)
mas[i].resize(n);
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++)
mas[i][j] = 0;
for (int k = 0; k < m; k++)
{
int i, j;
f » i;
f » j;
mas[i - 1][j - 1] = 1;
mas[j - 1][i - 1] = 1;
}
for (int i = 0; i < n; i++)
{
for (int j = 0; j < n; j++)
cout « mas[i][j] « ' ';
cout « endl;
}
cout « endl;
// BFS
int n_v, i, k = 0, l = 0;
cout « "№ вершины (BFS) - ";
cin » n_v;
int *maso = new int[n];
bool *masp = new bool[n];
for (int i = 0; i < n; i++)
{
maso[i] = 0;
masp[i] = false;
}
maso[0] = n_v;
masp[n_v - 1] = true;
while (l < n)
{
i = maso[l] - 1;
l++;
for (int j = 0; j < n; j++)
if ((mas[i][j] == 1) && (!masp[j]))
{
k++;
maso[k] = j + 1;
masp[j] = true;
}
}
for (int k = 0; k < n; k++)
if (maso[k] != 0)
cout « maso[k] « ' ';
// DFS
int k1 = 1, j, k2 = 0;
cout « endl « "№ вершины (DFS): ";
cin » k;
k--;
DFS(k, mas);
f.close();
cout « endl;
system("pause");
return 0;
}

Результаты:

[pic 1]