Добавил:
FluffyUnicorn
Опубликованный материал нарушает ваши авторские права? Сообщите нам.
Вуз:
Предмет:
Файл:Структуры данных примеры / Граф / dfs
.cpp//Поиск в глубину нерекурсивный
#include <conio.h>
#include <iostream>
#define N 6
using namespace std;
/*int G[N][N]={{0,1,1,0},
{1,0,1,0},
{1,0,0,1},
{0,1,0,0}},
P[N]={0,0,0,0}, */
int G[N][N]={0,1,1,0,0,0,
1,0,1,0,1,0,
1,0,0,1,0,0,
0,1,0,0,1,0,
0,0,0,0,0,1,
0,0,0,1,1,0},
P[N]={0,0,0,0,0,0},
c=0;
int next (int i, int cur)
{
cur++;
while (cur<N && !G[i][cur]) cur++;
if (cur<N) return cur;
return -1;
}
void DFS (int a)
{
int x, y, stack[N], top = -1;
stack[++top] = a; //помещаем вершину в стек
P[a] = ++c; //помечаем, что она посещается первой
while (top > -1) //пока стек не пуст
{
x = stack[top]; //берем элемент с вершины стека
y = -1;
do
y = next (x, y); //получаем смежные с данной вершины
while (y != -1 && P[y]); //пока не найдем еще не посещенную или не убедимся, что такой нет
if (y != -1) //если есть непосещенная смежная
{
stack[++top] = y; //помещаем ее в стек
P[y] = ++c; //помечаем ее посещенной
}
else
top--; //если двигаться некуда, извлекаем вершину из стека
}
}
main()
{
int x;
for (x=0; x<N; x++)
if (P[x]==0) {c=0; DFS(x);}
/* DFS(1);*/
for (x=0; x<N; x++)
cout << P[x] <<" ";
getch();
return 0;
}