Форум программистов, компьютерный форум, киберфорум
C для начинающих
Войти
Регистрация
Восстановить пароль
Карта форума Темы раздела Блоги Сообщество Поиск Заказать работу  
 
 
Рейтинг 5.00/18: Рейтинг темы: голосов - 18, средняя оценка - 5.00
0 / 0 / 2
Регистрация: 25.10.2012
Сообщений: 248
1

Нахождение кратчайшего цикла в графе

03.10.2013, 17:59. Показов 3293. Ответов 20
Метки нет (Все метки)

Author24 — интернет-сервис помощи студентам
Программа для нахождения кратчайшего цикла в графе.
Не могу корректно отладить.Прошу помочь.Заранее благодарен.


C
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
#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 c[],int *dcmin)//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 || 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;
 int g[N][N];
  printf("n=");
  scanf("%d",&n);
  VvodGrafa(g,n);
  Poisk(g,n);
  getch();
}
0
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
03.10.2013, 17:59
Ответы с готовыми решениями:

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

Нахождение кратчайшего цикла в графе
Программа для нахождения кратчайшего цикла в графе. Не могу корректно отладить.Прошу...

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

Нахождение кратчайшего пути в графе (алгоритм Дейкстры)
Здравствуйте, помогите пожалуйста, СРОЧНО,написать псевдокод реализации нахождения кратчайшего пути...

20
0 / 0 / 2
Регистрация: 25.10.2012
Сообщений: 248
09.10.2013, 20:46  [ТС] 21
Author24 — интернет-сервис помощи студентам
Консольное!

Добавлено через 4 минуты
Сохранял с расширением сpp. сейчас просто на c. сохранил,выдает другие данные при открытие консольного окна.
Выводит в окно все printf и потом задает граф из двух высот.
0
09.10.2013, 20:46
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
09.10.2013, 20:46
Помогаю со студенческими работами здесь

Нахождение кратчайшего цикла
Нужно найти кратчайший цикл в графе. Прошу помощи.

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

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

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


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
21
Ответ Создать тему
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2024, CyberForum.ru