Переделал рекурсивную реализацию ПВГ, написанную на pascal'е, на c++. Тестирую реализацию на графе, приведенном на рисунке. Вместо ожидаемого вывода 1 3 2 6 7 5 4 8 9 (корректный обход, приведенный на втором рисунке), я получаю 1 3 4 2 5 6 7 8 9 . Где ошибка в алгоритме?

Ошибка - не в алгоритме, а в реализации... И тебе, кстати, на эту ошибку указывает компилятор, внимательно смотри на все Warning-и, и увидишь, в чем дело.

хм, мой компилятор никаких Warning-ов не выдаёт... А Ваш что показывает?

Вот это:

Мой изначальный вариант был :

if ((a[v,i] != 0) && (Nnew[i])) Pg(i);

В a[v,i] почему-то оказывался адрес, а не значение из матрицы - решил использовать *(...).
И о чём этот Warning? Как исправить?

Очень просто: вспомнить, что в С есть "операция-запятая", которую ты пытаешься здесь использовать, но оно тебе не надо. А надо тебе обращаться к элементам многомерных массивов, и это делается так:

if (((a[v][i]) != 0) && (Nnew[i])) Pg(i);

Видишь разницу между тем, что ты пытался сделать, и тем, что написано у меня?

Спасибо, volvo! В который раз подводит меня невнимательность...
Ещё вопрос. Мне по заданию нужно отрисовывать граф и дерево, у меня написана программа на Delphi, которая рисует граф по матрице смежности, которую я пишу в файл в основной программе на c++, где реализован основной алгоритм (ПВШ, а теперь и ПВГ). Вобщем, как в данном случае матрицу смежности получить?

В принципе во всем разобрался сам и доработал программу. Вот окончательный вариант:

#include<iostream>
#include <stdio.h>
#include <stdlib.h>
#include<conio.h>
#include<math.h>
#include <fstream>

using namespace std;

 bool Nnew[15];
 int n;
 int a[15][15]; // =  {{0,0,1,1,0,0,0,0,0},{0,0,1,0,0,0,0,0,0},{1,1,0,0,0,1,0,0,0,},{1,0,0,0,1,0,0,0,0
 },{0,0,0,1,0,0,1,1,0,},{0,0,1,0,0,0,1,0,0,},{0,0,0,0,1,1,0,1,1},{0,0,0,0,1,0,1,0
,0},{0,0,0,0,0,0,1,0,0}}; 
 int tree[15][15];
 char esc;
  
void Pg(int v)
{
int i;



   Nnew[v] = false;
   cout<<v<<" ";
   for (i=0; i<n; i++)
     { 
            // cout<<"a[] = "<<*(a[v,i])<<endl;
             //cout<<"New = "<<Nnew[i]<<endl;
             if ((a[v][i] != 0) && (Nnew[i]))
             {            tree[v][i] = 1;
                           Pg(i);
                           }
     }
}

int main()
{  do
   {
     cout<<"Please, enter the numder of elements!"<<endl;
     cin>>n;   
    
   for (int i=0; i<n; i++)
       Nnew[i] = true;
       
   for (int i = 0; i < n; i++)
       for (int j = 0; j < n; j++)
        {
          if (i == j) a[i][j] = 0;
          else 
          {
               a[i][j] = rand()%2;    
               a[j][i] = a[i][j];
               }
              }  
       
   cout<<endl<<endl;
    cout<<"Ma3X of Graph:"<<endl<<endl;
    for (int i = 0; i < n; i++)
       for (int j = 0; j < n; j++)
       {
           if (j == n-1) {cout<<a[i][j]<<" "; cout<<endl;}
           else cout<<a[i][j]<<" ";
           
           }
       
       cout<<endl<<endl;
       
  for(int i =0; i<n; i++)
      for(int j = 0; j<n; j++)
      tree[i][j] = 0;   
   cout<<"Depth Sort Tree: "<<endl;    
  for (int i=0;i<n;i++)
    {  if (Nnew[i])  Pg(i);
        }
      
  getch();
          
  cout<<endl;
   cout<<"Ma3X of Tree: "<<endl<<endl;
      for (int i = 0; i < n; i++)
       for (int j = 0; j < n; j++)
       {
           if (j == n-1) {cout<<tree[i][j]<<" "; cout<<endl;}
           else cout<<tree[i][j]<<" ";
           
           }
       
   getch();
  
   ofstream out_graph, out_tree;
  
   out_graph.open("graph.txt",ios::out);
    out_tree.open("tree.txt",ios::out);
     
       
       out_graph <<n <<endl;
        for(int i = 0; i < n; i++)
        {
            for(int j = 0; j < n; j++)
            {
                out_graph <<a[i][j] <<' ';
            }
            out_graph <<endl;
        }
        out_graph.close();
        
       out_tree <<n <<endl;
        for(int i = 0; i < n; i++)
        {
            for(int j = 0; j < n; j++)
            {
                out_tree <<tree[i][j] <<' ';
            }
            out_tree <<endl;
        }
         out_tree.close();
    
        
        
       cout<<"Pressed 'ESC' to exit!"<<endl;
       esc = getch();
       system("cls");
       }
       while (esc != 27);
        
       system("cls");	
       return 0;
    }