Сетью наз-ся совокупность точек (узлов), некоторые соединены м/у собой стрелками. Сети, состоящей из N узлов можно сопоставить 2 квадратные матрицы порядка N: матрицу соединений и матрицу связей. Элемент матрицы соед-ий Aij равен 1, если сеть содержит стрелку, ведущую из узла I в узел j , и 0 в противном случае. Элемент Bij матрицы связей равен 1, если из узла i можно попасть в узел j двигаясь по стрелкам, и 0 в противном случае.
Лабиринт может быть задан матрицей соединений, в кот-ой для каждой пары комнат указано, соединены ли они коридором. Даны матрица соединений из для лабиринта из N комнат и номера комнат 1<=i<=N, 1<=j<=N. Построить путь из комнаты i в комнату j.

Здравствуйте, C0nsul, Вы писали:

C>Сетью наз-ся совокупность точек (узлов), некоторые соединены м/у собой стрелками. Сети, состоящей из N узлов можно сопоставить 2 квадратные матрицы порядка N: матрицу соединений и матрицу связей. Элемент матрицы соед-ий Aij равен 1, если сеть содержит стрелку, ведущую из узла I в узел j , и 0 в противном случае. Элемент Bij матрицы связей равен 1, если из узла i можно попасть в узел j двигаясь по стрелкам, и 0 в противном случае.
C>Лабиринт может быть задан матрицей соединений, в кот-ой для каждой пары комнат указано, соединены ли они коридором. Даны матрица соединений из для лабиринта из N комнат и номера комнат 1<=i<=N, 1<=j<=N. Построить путь из комнаты i в комнату j.

http://en.wikipedia.org/wiki/Breadth-first_search

Здравствуйте, _DAle_, Вы писали:

_DA>Здравствуйте, C0nsul, Вы писали:

C>>Сетью наз-ся совокупность точек (узлов), некоторые соединены м/у собой стрелками. Сети, состоящей из N узлов можно сопоставить 2 квадратные матрицы порядка N: матрицу соединений и матрицу связей. Элемент матрицы соед-ий Aij равен 1, если сеть содержит стрелку, ведущую из узла I в узел j , и 0 в противном случае. Элемент Bij матрицы связей равен 1, если из узла i можно попасть в узел j двигаясь по стрелкам, и 0 в противном случае.
C>>Лабиринт может быть задан матрицей соединений, в кот-ой для каждой пары комнат указано, соединены ли они коридором. Даны матрица соединений из для лабиринта из N комнат и номера комнат 1<=i<=N, 1<=j<=N. Построить путь из комнаты i в комнату j.

_DA>http://en.wikipedia.org/wiki/Breadth-first_search

Спасибо за помощь, смысл я понял. Но вот проблема — как распечатать на экране весь пройденный путь из I в J?

Вот текст моей проги:

#include <windows>
#include <iostream>
#include <fstream>
#include <conio>

class Stack
{
   public:
           Stack() : top(0) {}
           int a[1000];
           int top;
           bool empty();
           int pop();
           void push(int x);
           void print();
};

bool Stack :: empty()
{
   return ( ( !top ) ? (true) : (false) );
}

int Stack :: pop()
{
   return a[--top];
}

void Stack :: push(int x)
{
   a[top++] = x;
}

void Stack :: print()
{
   for(int i=0; i<top; ++i)
      cout << "\n Stack:  " << a[i] << ' ';
   cout << endl;
}

// GLOBAL
const N = 10;
int matrix[N][N];
Stack Queue;

void breadthSearch(int size, int Start, int Goal)
{
     int Node;
     Queue.push(Start);
     while( !Queue.empty() )
     {
          Node = Queue.pop();
          cout << Node+1 << '\n';          
          if( Node == Goal )
          {
              return;
          }
          for(int j=0; j<size; ++j)
          {
              if( matrix[Node][j] )
              {
                 Queue.push(j);
                 matrix[Node][j] = 0;
              }
          }
     }
}

int main()
{
    int i, j, I, J, size;

    // считываем matrix из файла
    ifstream ifile("labirint.txt");
    ifile >> size;
    if ( (size < 2) || (size > N) )
    {
       cout << " Size of Matrix is Bad!";
       ifile.close();
       exit(0);
    }
    for(i=0; i<size; ++i)
      for(j=0; j<size; ++j)
          ifile >> matrix[i][j];
    ifile.close();
        
    cout << " Insert I: ";   // номер I-ой комнаты
    cin >> I;
    cout << " Insert J: ";   // номер J-ой комнаты
    cin >> J;
    if( (I-1 < 0) || (J-1 < 0) || (I-1 >= size) || (J-1 >= size) )
    {
       cout << " Parameter I or J is Bad!";
       exit(0);
    }     

    breadthSearch(size, I, J);

    getch();
    return 1;
}

Файл 'labirint.txt' для случая изображенного на рисунке http://comp-science.narod.ru/89-90/Net.gif :

6
0 0 1 0 0 0
0 0 0 1 0 0
0 0 0 1 1 0
0 0 0 0 0 0
0 0 0 1 0 1
0 0 0 0 0 0

Как вывести на экран путь из I в J?