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

[East Undia Trading]

А как правильно записать граф в файл чтобы считывание было правильным?

[BDA]

fread подразумевает бинарные данные, так что придётся или записывать вручную в HEX-редакторе, или писать дополнительную программу, преобразующую текстовые данные в бинарные, или переписать считывание с помощью fscanf(edge, "%d%d%d%d", &edge_item[i].id, &edge_item[i].out, &edge_item[i].in, &edge_item[i].weight); и оформить входной файл примерно так:

3
1 1 2 5
2 2 3 6
3 1 3 2

[East Undia Trading]

Что-то я все-таки упускаю.Программа компилируется, появляется окошко консоли, но работа завершается без ошибки.
Вот что я хотел сделать:

1. считать количество узлов
2. считать количество ребер
3. инициализировать массивы структур ребер и узлов
4. работать в цикле пока не достигнут конца файла заполнить массив ребер данными
5. работа с полученной информацией, перебор массива ребер и заполняем массива узлов

Что получилось:

#include <stdio.h>
#include <stdlib.h>
/*void FindWay(edge_struct, int, int );
struct edge_struct
{
	int id;
	int in;
    int out;
    int weight;
} newList;
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))
	   {
       fscanf(edge, "%d%d%d%d", &edge_item[i].id, &edge_item[i].out, &edge_item[i].in, &edge_item[i].weight);          
	   }   
	}
if(node=fopen("edge.txt","r")){
fread(&n,sizeof(int),1,node);
node_number=n;
}
close(edge);
close(node);
for(i=0;i<n;i++)
{
	scanf("%d", newList.in);
	scanf("%d", newList.out);
}
}

[BDA]

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

struct edge_struct
{
    int id;
    int in;
    int out;
    int weight;
};

int
main()
{
    FILE *edge;
    int i, edge_number;
    struct edge_struct *edge_item;
    edge = fopen("edge.txt", "r");
    if (!edge)
        return 1;
    fscanf(edge, "%d", &edge_number);
    edge_item = calloc(edge_number, sizeof(*edge_item));
    for (i = 0; i < edge_number; ++i)
        fscanf(edge, "%d%d%d%d", &edge_item[i].id, &edge_item[i].out, &edge_item[i].in, &edge_item[i].weight);
    fclose(edge);
    //работа с данными
    free(edge_item);
    return 0;
}

Считывание ребер из файла.

[East Undia Trading]

BDA, переделал и исправил программу.Запускается окно консоли и завершается без ошибки.Мне кажется я finish неправильно объявил и неправильно передаю в функцию FindWay, но как иначе я не знаю.Эта функция ищет кратчайшее расстояние из вершины transit до finish.Как лучше представить данные в файле чтобы заполнить структуру Graph?

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
struct Arc
{
	int from;     //индекс исходящей вершины
	int to;       //индекс входящей вершины
    double weight;
} ;
struct Way
{
    bool exist;       //существование пути
    double sumWeight;  //суммарный вес
    int refPrev;      //индекс узла, через который проходит путь
};
struct Graph
{
	int numNodes;      //число вершин
	int numArcs;       //число дуг
	struct Arc *arcs;         //указатель на массив дуг
	
	struct Way *pMinWay;        //Адрес первого элемента массива и инфрмацией о минималном пути от start до finish
	                    //pMinWay[i] минимальная стоимость из i в start
};

void FindWay(struct Graph g, int, int);
 
int main(){
    FILE *edge;
    int i, edge_number;
    struct edge_struct *edge_items;
    struct edge_item *items;
    struct Graph *g;
    edge = fopen("edge.txt", "r");
    if (!edge)
        return 1;
    fscanf(edge, "%d", &edge_number);
    g = calloc(edge_number, sizeof(*g));
    for (i = 0; i < edge_number; ++i)
        fscanf(edge, "%d%d%d%d", &g[i].numNodes, &g[i].numArcs);
    fclose(edge);
        //ForStep(struct edge_struct *edge_items, struct edge_item *items, int edge_number); 
    free(edge_items);
    return 0;
}
 
// Шаг по дуге ixArc к вершине, смежной с вершиной transit 
void ForStep(struct Graph g, int ixArc) 
{ 
     int transit = g.arcs[ ixArc ].from; // Транзитная вершина 
     int step    = g.arcs[ ixArc ].to; // Смежная вершина 
     int finish  = g.arcs[ ixArc ].from; // Транзитная вершина ////////////
 
     // Вычисляем новый суммарный вес пути через 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(struct Graph g, int transit, int finish ) 
{ 
   int ixArc;
   if( transit == finish ) return; 
 
   // Находим дуги, исходящие из transit и 
   // выполняем шаг по каждой найденной дуге 
   for( ixArc=0; ixArc < g.numArcs; ixArc++ ) 
   { 
   // Рассматриваем случай орграфа, поэтому анализируем 
   // только исходящую вершину дуги 
   if( g.arcs[ ixArc ].from == transit ) 
   ForStep( g, ixArc ); 
  } 
  return; // Больше путей нет 
}

[East Undia Trading]

BDA, на самом деле все работает, но я все равно дурь сделал.Нужно было вводить матрицу смежности, а я массив дуг из файла тут пытаюсь.Можете подсказать с чего начать?Можно использовать данный пример или эта программа вообще не подойдет?

[BDA]

Честно говоря, я не отвечал, потому что при виде такого длинного кода (2 экрана) отпадает желание в нём разбираться
Забавно получилось (к тому, что я упоминал матрицу смежности во 2 посте).

fscanf(f, "%d", &n);
int **a;
a = calloc(n, sizeof(*a));
for (i = 0; i < n; ++i)
    a[i] = calloc(n, sizeof(**a));
for (i = 0; i < n; ++i)
    for (j = 0; j < n; ++j)
        fscanf(f, "%d", &a[i][j]);

Пример входного файла:

3
1 0 1
0 0 1
1 1 1

[East Undia Trading]

BDA, на счет размера кода - учту.
Действительно забавно.
Главные вопрос, можно ли заполнить поля данной структуры примерно так же как и массив дуг?(я думаю, нет) Иначе, соответственно, функция не подходит и нудно делать все по другому.

struct Arc
{
	int from;          //индекс исходящей вершины
	int to;            //индекс входящей вершины
    double weight;
} ;
struct Way
{
    bool exist;        //существование пути
    double sumWeight;  //суммарный вес
    int refPrev;       //индекс узла, через который проходит путь
};
struct Graph
{
	int numNodes;      //число вершин
	int numArcs;       //число дуг
	struct Arc *arcs;         //указатель на массив дуг
	
	struct Way *pMinWay;        //Адрес первого элемента массива и инфрмацией о минималном пути от start до finish
	                            //pMinWay[i] минимальная стоимость из i в start
};

[BDA]

Вообще, такой способ хранения будет более эффективным при большом количестве вершин и малом количестве дуг. Если не брать в расчет массив pMinWay, то Graph будет эквивалентен матрице смежности (одно представимо через другое).
Для сравнения:
4 * n * n - количество памяти для матрицы смежности (n - количество вершин)
12 + 16 * m - количество памяти для графа без учета pMinWay (m - количество дуг)

[East Undia Trading]

BDA, а если я буду использовать списки смежности орграфа, мне подойдет такая структура?Подскажите какие именно поля нужно будет заполнять.Я буду делать это с клавиатуры.

struct Arc
{
	int from;          //индекс исходящей вершины
	int to;            //индекс входящей вершины
    double weight;
} ;
struct Way
{
    bool exist;        //существование пути
    double sumWeight;  //суммарный вес
    int refPrev;       //индекс узла, через который проходит путь
};
struct Graph
{
	int numNodes;      //число вершин
	int numArcs;       //число дуг
	struct Arc *arcs;         //указатель на массив дуг
	
	struct Way *pMinWay;        //Адрес первого элемента массива и инфрмацией о минималном пути от start до finish
	                            //pMinWay[i] минимальная стоимость из i в start
};