Сетевой график

[Nina+]

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

[Nina+]

Помогите с решением такой задачи (С):
есть массив из двух столбцов, каждая строка массива содержит номера начального и конечного событий работы. Нужно занести в другой двумерный массив все возможные пути.

[Nina+]

Ну помогите...пожалуйста...очень нужно

[Nina+]

Попыталась сама написать, но работает не правильно.
Нужно чтобы выводила:
1 2 3 4 9 11 12 13
1 2 3 5 10 11 12 13
1 2 3 6 11 12 13
1 2 3 7 11 12 13
1 2 3 8 11 12 13
1 2 3 9 11 12 13

Ещё не знаю как определить количество этих путей в общем случае...

#include<stdio.h>
#include<conio.h>
#define N 17
main(){
       int k,i;
       int mas[17][2]={{1,2},{2,3},{3,4},{3,5},{3,6},{3,7},{3,8},{3,9},{4,9},{5,10},{6,11},{7,11},{8,11},{9,11},{10,11},{11,12},{12,13}};
       int dop[17]={0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0};
       int put[N][N];
       int kol[N];
for(int q=0;q<6;q++){
  k=0;i=0;
  i=dop[mas[i][0]];
  put[q][k]=mas[i][0];
  put[q][k+1]=mas[i][1];
  dop[mas[i][0]]=dop[mas[i][0]]+1;
  k+=2;
  i++;
  while(i<N){
       if(put[q][k-1]==mas[i][0]){
            i=i+dop[mas[i][0]];
            put[q][k]=mas[i][1];
            dop[mas[i][0]]=dop[mas[i][0]]+1;
            k++;
            }
       i++;
       }
       kol[q]=k;
       }     
  for(int q=0;q<6;q++){
  for(i=0;i<kol[q];i++)
       printf(" %d",put[q][i]);
       printf("\n");
       }
  getch();                    
}

[Sazary]

Nina+, опишите более подробно, что имеется и что нужно получить. Именно логику работы.
Вот я вижу 2 массива:

 int mas[17][3]={{0,1,2},{0,2,3},...............,{0,7,11},{0,8,11},{0,9,11},{0,10,11},{0,11,12},{0,12,13}};
       int dop[17]={0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0};

Что из себя представляет первый?
По какому принципу должна получаться таблица, которую вы написали?

А то я как-то не очень понимаю..

[Nina+]

Массив int mas[17][2]={{1,2},{2,3},{3,4},{3,5},{3,6},{3, 7},{3,8},{3,9},{4,9},{5,10},{6,11}, {7,11},{8,11},{9,11},{10,11},{11,12 },{12,13}};
в нем построчно хранятся номера начального и конечного события работы, всего 17 работ
каждое событие является начальным для разного числа работ
нужно определить все возможные пути от самого первого события к последнему

вот график

[Sazary]

Хороший рисунок - наглядный. Вам нужно было его сразу выложить )

Как вариант, можно составить матрицу смежности. Тогда, навскидку, будет несложно сделать остальное.

[Nina+]

мы теорию графов ещё не проходили...

[Sazary]

мы теорию графов ещё не проходили...

Ну там только матрицу смежности пригодится. Честно говоря, сейчас пока других идей нет.
Сегодня или завтра накидаю пример (с матрицей смежности через рекурсию).
Просто есть матрица 18 на 18 (т.к. индексацию придется сделать от 1).
Если, например, в ячейке [1][2] стоит 1, то есть путь от 1 к 2. Если 0, то нет.

[Sazary]

Вот. Вроде, все понятно.

#include <stdio.h>
#include <conio.h>
#include <stdlib.h>
#define N 17

const int COUNT = 13;
int matr[COUNT][COUNT]; // матрица смежности

// рекурсивная функция
// принимает: предыдущее звено, массив (путь), размер массива
void rec(int tek, int *dop, int d)
{
 //printf("%d\n",tek);
 if(tek==COUNT-1) // если текущее звено - последнее, то...
  {
   printf("%d",dop[0]);  // выводим первое звено (1)
   for(int i=1; i<d; i++) // и остальные
    printf(" -> %d",dop[i]);
   printf("\n");
  }

 for(int i=0; i<COUNT; i++)  // проверяем все связи для текущего звена
  {
   if(matr[tek][i]==1)  // если связь есть...
    {
     dop[d] = i+1;  // заносим в массив
     rec(i, dop, d+1); // и переходим к следующему звену
    }
  }
}

//------------------
int main()
{
int k,i,j;
int mas[N][2]={{1,2},{2,3},{3,4},{3,5},{3,6},{3,7},{3,8},{3,9}, {4,9},{5,10},{6,11},{7,11},{8,11},{9,11},{10,11},{ 11,12},{12,13}};
int dop[N],d=0;

for(i=0; i<COUNT; i++)
 for(j=0; j<COUNT; j++)
  matr[i][j] = 0;       // заполняем матрицу смежности нулями

for(i=0; i<N; i++)
 matr[mas[i][0]-1][mas[i][1]-1] = 1;  // устанавливаем связи

dop[0] = 1; // первый элемент - 1
for(i=0; i<COUNT; i++) // смотрим связи
 {
  if(matr[0][i]==1)  // если связь есть, то...
   {
    dop[1] = i+1; // заносим в массив
    rec(i,dop,2);  // и переходим к следующему звену
   }
 }

getch();
return 0;
}

------------------
Поясню один момент:
индексация массива идет от нуля. А названия работ - от 1. Поэтому там, в массив (сформированный путь) заносится значение i+1, а не i.

---------------
В результате получится такая картинка:

1 -> 2 -> 3 -> 4 -> 9 -> 11 -> 12 -> 13
1 -> 2 -> 3 -> 5 -> 10 -> 11 -> 12 -> 13
1 -> 2 -> 3 -> 6 -> 11 -> 12 -> 13
1 -> 2 -> 3 -> 7 -> 11 -> 12 -> 13
1 -> 2 -> 3 -> 8 -> 11 -> 12 -> 13
1 -> 2 -> 3 -> 9 -> 11 -> 12 -> 13