Поиск вершин в графе.Язык С/С++

[East Undia Trading]

Мне необходимо найти вершины из которых дуги только выходят, но не понимаю какому признаку должно удовлетворять данное условие.И еще вопрос, какой алгоритм поиска лучше использовать?
Полный текст задания:

Во взвешенном орграфе найти все стоки, то есть вершины, в которые только входят дуги, и истоки, т. е. вершины, из которых дуги только выходят, а также кратчайший путь, связывающий две заданные вершины. Списки смежности орграфа и номера вершин для поиска вводятся с клавиатуры.

[BDA]

Имеем список смежности:
Xi -> Yi, что обозначает путь из Xi в Yi
Получаем два множества X и Y. Множество X-Y - истоки. Множество Y-X - стоки.

Еще один способ - построить матрицу смежности. Номер строки - номер вершины-выхода, номер столбца - номер вершины-входа. Столбец, заполненный нулями, соответствует вершине-истоку. Строка, заполненная нулями, соответствует вершине-стоку.

Список алгоритмов поиска пути

[East Undia Trading]

#include <stdio.h>
#include <stdlib.h>

void FindWay( Graph&, int, int ); //тут ругается
 
void ForStep( Graph& g, int ixArc )  //тут ругается
{ 
     int transit = g.arcs[ ixArc ].from; 
     int step    = g.arcs[ ixArc ].to; 
 
     double newSumWeight = g.pMinWay[ transit ].sumWeight + g.arcs[ ixArc ].weight; 
 
     if( !g.pMinWay[ step ].exist ) 
     { 
     g.pMinWay[ step ].exist = true; 
  
     g.pMinWay[ step ].sumWeight = newSumWeight; 
  
     g.pMinWay[ step ].refPrev = transit; 
      FindWay( g, step, finish ); 
     } 
     else 
     { 
         if( g.pMinWay[ step ].sumWeight > newSumWeight ) 
         { 
         g.pMinWay[ step ].sumWeight = newSumWeight; 
         g.pMinWay[ step].refPrev = transit; 
         FindWay( g, step, finish ); 
         } 
     } 
} 
  
void FindWay( Graph& g, int transit, int finish )  //тут ругается
{ 
   if( transit == finish ) return; 
 
   for( int ixArc=0; ixArc < g.numArcs; ixArc++ ) 
   { 
   if( g.arcs[ ixArc ].from == transit ) 
   ForStep( g, ixArc ); 
  } 
  return; 
}

Разобрался

[East Undia Trading]

Разобрался

[East Undia Trading]

Все равно ничего не понял.Я нашел это решение в интернете, но сам понять что там происходит не могу.Что должно передаваться в FindWay?Что за тип такой Graph& ?То что у меня получилось ниже, как и текст задания, ниже.

Во взвешенном орграфе найти все стоки, то есть вершины, в которые только входят дуги, и истоки, т. е. вершины, из которых дуги только выходят, а также кратчайший путь, связывающий две заданные вершины. Списки смежности орграфа и номера вершин для поиска вводятся с клавиатуры.

PHP код:

struct edge_struct
{
    int node;     //номер узла
    int in[80];   //номера входящих ребер
    int out[80];  //номера исходящих ребер 
};
struct edge_item
{
    int id;
    int inedge;
    int outedge;
    int weight;

};

int main(){
    FILE *edge,*node;
    int n,i,node_number,edge_number;
    struct edge_struct edge_item[n];
    if(!edge=fopen("edge.txt","r"))
    {    
       fread(&n,sizeof(int),1,edge);
       struct edge_struct edge_item[n];
         edge_number;
       i=0;
       while(!eof(edge))
       {
       fread(&n,sizeof(int),edge);
       edge_item[i].id=n;
       fread(&n,sizeof(int),edge);
       edge_item[i].out=n;
       fread(&n,sizeof(int),edge);
       edge_item[i].in=n;
       fread(&n,sizeof(int),edge);
       edge_item[i].weight=n;            
       }   
    }
if(!node=fopen("node.txt","r")){
fread(&n,sizeof(int),1,node);
struct node_struct node_item[n];
node_number=n;
}
close(edge);
close(node);
for(i=0;i<n;i++)
{
    scanf("%d", edge_struct.in);
    scanf("d", edge_struct.out);
}
    
} 


PHP код:

#include <stdio.h>
#include <stdlib.h>

void FindWay( Graph&, int, int );
 
void ForStep( Graph& g, int ixArc )
{ 
     int transit = g.arcs[ ixArc ].from; 
     int step    = g.arcs[ ixArc ].to; 
 
     double newSumWeight = g.pMinWay[ transit ].sumWeight + g.arcs[ ixArc ].weight; 
 
     if( !g.pMinWay[ step ].exist ) 
     { 
     g.pMinWay[ step ].exist = true; 
  
     g.pMinWay[ step ].sumWeight = newSumWeight; 
  
     g.pMinWay[ step ].refPrev = transit; 
      FindWay( g, step, finish ); 
     } 
     else 
     { 
         if( g.pMinWay[ step ].sumWeight > newSumWeight ) 
         { 
         g.pMinWay[ step ].sumWeight = newSumWeight; 
         g.pMinWay[ step].refPrev = transit; 
         FindWay( g, step, finish ); 
         } 
     } 
} 
  
void FindWay( Graph& g, int transit, int finish )  //тут ругается
{ 
   if( transit == finish ) return; 
 
   for( int ixArc=0; ixArc < g.numArcs; ixArc++ ) 
   { 
   if( g.arcs[ ixArc ].from == transit ) 
   ForStep( g, ixArc ); 
  } 
  return; 
} 


[BDA]

По поводу Вашего кода - есть ошибки. Смысла тоже не уловил. Зачем 2 структуры? Что за 2 файла? Как задумывалась работа?
По поводу второго кода - судя по всему, этот код на C++. Graph, скорее всего, самописный тип. А Grapsh& - это аргумент-ссылка.

[East Undia Trading]

BDA, работа задумывалась как заполнение структуры графа значениями->резервирование памяти для массивов arcs и PMinway.Получилось то, что получилось

поле номер 1 номер узла
поле 2 массив  номеров входящих ребер
поле 3 массив номеров исходящих ребер
и структура ребер
номер ребра
исходящий узел
узел вхождения
вес ребра

[East Undia Trading]

Для начала я не могу правильно загрузить граф из файла , можете подсказать в чем проблема?

if(!edge=fopen("edge.txt","r"))

Здесь пишет [Error] lvalue required as left operand of assignment

struct edge_struct
{
    int node;     //номер узла
    int in[80];   //номера входящих ребер
    int out[80];  //номера исходящих ребер 
};
struct edge_item
{
    int id;
    int inedge;
    int outedge;
    int weight;

};

int main(){
    FILE *edge,*node;
    int n,i,node_number,edge_number;
    struct edge_struct edge_item[n];
    if(!edge=fopen("edge.txt","r"))
    {    
       fread(&n,sizeof(int),1,edge);
       struct edge_struct edge_item[n];
         edge_number;
       i=0;
       while(!eof(edge))
       {
       fread(&n,sizeof(int),edge);
       edge_item[i].id=n;
       fread(&n,sizeof(int),edge);
       edge_item[i].out=n;
       fread(&n,sizeof(int),edge);
       edge_item[i].in=n;
       fread(&n,sizeof(int),edge);
       edge_item[i].weight=n;            
       }   
    }
if(!node=fopen("node.txt","r")){
fread(&n,sizeof(int),1,node);
struct node_struct node_item[n];
node_number=n;
}
close(edge);
close(node);
for(i=0;i<n;i++)
{
    scanf("%d", edge_struct.in);
    scanf("d", edge_struct.out);
}
    
}

[BDA]

if (edge = fopen("edge.txt", "r"))

Восклицательный знак не нужен.

[East Undia Trading]

BDA, я исправил main и вот что получилось.

#include <stdio.h>
#include <stdlib.h>
const n;
void FindWay(edge_struct, int, int ); // Предварительное объявление 
struct edge_struct
{
	int id;     //номер узла
	int in;   //номера входящих ребер
    int out;  //номера исходящих ребер 
    int weight;
};
int main(){
    FILE *edge,*node;
    int n,i,node_number,edge_number;
    struct edge_struct *newList;
    newList = (struct edge_struct *) malloc(sizeof(struct edge_struct));
    struct edge_struct edge_item[n];
    if(edge=fopen("edge.txt","r"))
	{	
       fread(&n,sizeof(int),1,edge);
       struct edge_struct edge_item[n];
         edge_number;
       i=0;
       while(!eof(edge))
	   {
       fread(&n,sizeof(int), 1,edge);
       edge_item[i].id=n;
       fread(&n,sizeof(int),1 ,edge);
       edge_item[i].out=n;
       fread(&n,sizeof(int),1 ,edge);
       edge_item[i].in=n;
       fread(&n,sizeof(int),1 ,edge);
       edge_item[i].weight=n;            
	   }   
	}
if(node=fopen("node.txt","r")){
fread(&n,sizeof(int),1,node);
struct edge_struct edge_item[n];
node_number=n;
}
close(edge);
close(node);
for(i=0;i<n;i++)
{
	scanf("d", newList->in);
	scanf("d", newList->out);
}
}



 
// Шаг по дуге ixArc к вершине, смежной с вершиной transit 
void ForStep( struct node_struct, int ixArc ) 
{ 
     int transit = g.arcs[ ixArc ].from; // Транзитная вершина 
     int step    = g.arcs[ ixArc ].to; // Смежная вершина 
 
     // Вычисляем новый суммарный вес пути через transit до step 
     double newSumWeight = g.pMinWay[ transit ].sumWeight + g.arcs[ ixArc ].weight; 
 
     if( !g.pMinWay[ step ].exist ) 
     { 
     // Эта вершина раскрыта впервые 
     g.pMinWay[ step ].exist = true; 
  
     g.pMinWay[ step ].sumWeight = newSumWeight; 
  
     g.pMinWay[ step ].refPrev = transit; 
      FindWay( g, step, finish ); 
     } 
     else 
     { 
         // Эта вершина раньше встречалась 
         if( g.pMinWay[ step ].sumWeight > newSumWeight ) 
         { 
          // Новый путь короче 
         g.pMinWay[ step ].sumWeight = newSumWeight; 
         g.pMinWay[ step].refPrev = transit; 
         FindWay( g, step, finish ); 
         } 
         // Здесь: прежний путь лучше, то есть дальше искать 
         // нечего, поэтому игнорируем этот шаг 
     } 
} 
 
// Поиск кратчайшего пути от transit до finish 
void FindWay( Graph& g, int transit, int finish ) 
{ 
   if( transit == finish ) return; 
 
   // Находим дуги, исходящие из transit и 
   // выполняем шаг по каждой найденной дуге 
   for( int ixArc=0; ixArc < g.numArcs; ixArc++ ) 
   { 
   // Рассматриваем случай орграфа, поэтому анализируем 
   // только исходящую вершину дуги 
   if( g.arcs[ ixArc ].from == transit ) 
   ForStep( g, ixArc ); 
  } 
  return; // Больше путей нет 
}