Добавил:
Опубликованный материал нарушает ваши авторские права? Сообщите нам.
Вуз: Предмет: Файл:
Скачиваний:
16
Добавлен:
18.03.2018
Размер:
1.66 Кб
Скачать
//Поиск в ширину нерекурсивный

#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, queue[N], beg = 0, end=-1;
    
	queue[++end] = a;   //помещаем вершину в queue
    P[a] = ++c;    //помечаем, что она посещается первой
    while (beg < N)           //пока queue не пустa
    {
          x = queue[beg];      //берем элемент с вершины стека
 	      y = -1;
         do
         { 
          do
              y = next (x, y); //получаем смежные с данной вершины
          while (y != -1 && P[y]);        //пока не найдем еще не посещенную или не убедимся, что такой нет
          if (y != -1)   //если есть непосещенная смежная
          {

                queue[++end] = y;         //помещаем ее в стек
                P[y] = ++c;               //помечаем ее посещенной
          }
          else
                beg++; //если двигаться некуда, извлекаем вершину из queue
         }
         while (y != -1);
    }
}

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