Скачиваний:
16
Добавлен:
18.03.2018
Размер:
1.59 Кб
Скачать
//Поиск в глубину нерекурсивный

#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;
}
Соседние файлы в папке Граф