Форум программистов
 

Восстановите пароль или Зарегистрируйтесь на форуме, о проблемах и с заказом рекламы пишите сюда - alarforum@yandex.ru, проверяйте папку спам!

Вернуться   Форум программистов > C/C++ программирование > Общие вопросы C/C++
Регистрация

Восстановить пароль
Повторная активизация e-mail

Купить рекламу на форуме - 42 тыс руб за месяц

Ответ
 
Опции темы Поиск в этой теме
Старый 06.10.2013, 14:07   #1
Максим 116
Пользователь
 
Регистрация: 06.10.2013
Сообщений: 31
Восклицание Поиск кратчайшего цикла в графе

Программа для нахождения кратчайшего цикла в графе.
Проблемы с компиляцией.

Код:
#include <stdio.h>
#include <conio.h>
#define N 10

/***** Vvod Grafa *****/

void VvodGrafa(int g[N][N], int n)
{
int i,j;// nomer stroki,stolbca
   printf("Vvedite matricy smeznosti:\n\n");
   printf(" | ");
 for(j=0;j<n;j++)
     printf("%d",j);
     putchar('\n');
 for(i=0;i<2*n+2;i++)
     putchar('-');
 for(i=0;i<n;i++)
{
     printf("\n%d| ",i);
   for(j=0;j<n;j++)
       scanf("%d",&g[i][j]);}
}


/***** Poisk cikla *****/

int Poisk(int g[N][N],int n,int *dcmin,int c[])//c-vektor s nomerami vershin naidennogo cikla;dlina min.cikla - dcmin
{
 int k;// ukazatel steka
 int ver[N+1];//Stek s nomerami vershin 
 int st[N];//stek
 int tv;//nomer ocherednoi vershini tecushego puti
 int i,j;
  
  /*Obhod v glubinu*/
  
  *dcmin=n+1;
 for(ver[0]=1;ver[0]<=n && *dcmin>3;)/* Nachalnaya vershina*/

{/*Obhod v glubinu dereva putei,nachinayshihsya s ver[0]*/

    k=1;ver[1]=ver[0]+1;//nachalnyu nomer priemnikov s ver[0]
  do
 {/*nahogdenie vershini tv - priemnika ver[k-1]*/
    j=ver[k-1];
 for(tv=ver[k];tv<n && (g[i][tv]==0 || k>1 && tv==ver[k-2]);ver++)
     if(tv<n && k<*dcmin)
     {
         ver[k]=tv;/*vpered:tv-v stek*/
         ver[k+1]=tv[0];/*nachalnyi priemnik ver[k]*/
     if(ver[0]==ver[k] && k>0) /*nashli cikl*/
     {
         *dcmin=k;
    /*Zapomnit' cikl ver[0]...ver[k]*/
    for(j=0;j<=k;j++) c[j]=ver[j];
        k=k-3;/*Nazad: udalit' dve vershini*/
        ver[k+1]++;/*Sled priemnik ver[k]*/
     }
         k++;
     }
     else
     {
         k--;/*udalit' ver[k] iz steka*/
         ver[k]++;
     }
     }
     while(k>0 && *dcmin>3);/*stek ne pustoi*/
     }
  return *dcmin>n;
}  

/***** Glavnaya funkciya *****/

main()
{int n,j;
 int c[];
 int g[N][N];
  printf("n=");
  scanf("%d",&n);
  VvodGrafa(g,n);
  Poisk(g,n);
  for(j=0;j<n;j++)
  printf("%d",&c[j]);
  getch();
}

Последний раз редактировалось Максим 116; 06.10.2013 в 14:11.
Максим 116 вне форума Ответить с цитированием
Ответ


Купить рекламу на форуме - 42 тыс руб за месяц



Похожие темы
Тема Автор Раздел Ответов Последнее сообщение
поиск кратчайшего пути в графе zokwild Помощь студентам 0 30.11.2012 18:22
Поиск кратчайшего пути в графе BaceK Помощь студентам 0 18.12.2011 11:49
найти длину кратчайшего цикла в графе Petruha-nsk Общие вопросы C/C++ 4 13.05.2009 17:08
1) Поиск кратчайшего пути в графе методом полного перебора в ширину(очередь) Serega123 Помощь студентам 3 30.10.2008 22:26