Нахождение кратчайшего цикла в графе - C (СИ) (154256)
Формулировка задачи:
Программа для нахождения кратчайшего цикла в графе.
Не могу корректно отладить.Прошу помочь.Заранее благодарен.
#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];[B][/B] 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(); }
Решение задачи: «Нахождение кратчайшего цикла в графе»
textual
Листинг программы
#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(); }
Объяснение кода листинга программы
- Ввод графа:
- Переменная
n
получает значение количества вершин в графе (ввод с клавиатуры). - Ввод матрицы смежности графа с помощью функции
scanf
.
- Переменная
- Поиск цикла:
- Создание и инициализация векторов
ver
иst
. - Переменная
k
инициализируется значением 1, а переменнаяver[1]
устанавливается равной ver[0]+1. - Цикл
do
начинается. В каждой итерации цикла:- Переменная
j
устанавливается равной ver[k-1]. - Цикл
for
начинается. В каждой итерации цикла:- Переменная
tv
устанавливается равной ver[k]. - Если
tv
меньше количества вершин иk
меньше минимальной длины цикла, то:ver[k]
иver[k+1]
обновляются.- Если
ver[0]
равноver[k]
, то:k
уменьшается на 3.ver[k+1]
увеличивается.- Если цикл найден, то:
- Минимальная длина цикла сохраняется в переменной
*dcmin
. - Цикл сохраняется в массив
c
. k
уменьшается на 3.ver[k+1]
увеличивается.- Цикл продолжается, пока
k
больше 0 и*dcmin
больше 3. - Если цикл не найден, то
*dcmin
устанавливается равным количеству вершин плюс 1. - Цикл завершается.
- Функция
main
возвращает значение 0.
- Минимальная длина цикла сохраняется в переменной
- Переменная
- Переменная
- Создание и инициализация векторов
- Главная функция:
- Переменная
n
получает значение количества вершин в графе (ввод с клавиатуры). - Функция
VvodGrafa
вызывается для ввода матрицы смежности графа. - Функция
Poisk
вызывается для поиска цикла в графе. - Функция
getch
вызывается для приостановки выполнения программы до нажатия клавиши.
- Переменная