Поиск эйлерова пути в графе
Дипломная работа - Компьютеры, программирование
Другие дипломы по предмету Компьютеры, программирование
мера вершин
n-количество вершин
g, t-матрицы смежности графа, t - копия g
res-массив, содержащий результат
АЛГОРИТМ: см. алгоритм 3.2., рис. 3.2.
Алгоритм 3.2. Алгоритм модуля main
if (VVOD(&n,g)!=0) {Vyvod(VVOD(&n,g));return 0;}//ошибка ввода
if (prov1(n,g)==6) {Vyvod(prov1(n,g));return 0;}//проверка на связность
if (prov2(n,g)==7) {Vyvod(prov2(n,g));return 0;}//проверка на степень вершин
j=0;
while ( j<n)//перебор вершин для поиска путей
{ no=0;//указатель конца массива результата
for (i = 0; i < n; i++) for (k = 0; k< n; k++) t[i][k]=g[i][k]; //копия матрицы смежности
Poisk(j,n,t,&no,res);//поиск пути в графе от вершины j
k=0;
for (i = 0; i < no-1; i++)
{
if (g[res[i]][res[i+1]]==1) k++;/*проверка массива результата на наличие ребер в матрице смежности*/
}
if (k==no-1) break;//эйлеров путь найден, выход из цикла перебора вершин
j++;
}(i = no-1; i >=0; i--)
{("%d\n", res[i]);//печать результата
}();0;
3.3.2 VVOD - ввод графа
ЗАГОЛОВОК: int VVOD(int *n,int g[][NMAX])
ФУНКЦИЯ: ввод графа из файла f в виде матрицы смежности, перед которой указывается количество вершин n. NMAX - максимальное количество вершин.
ВХОДНЫЕ ДАННЫЕ: количество вершин n, матрица смежности g.
ВЫХОДНЫЕ ДАННЫЕ:
n - количество вершин графа;
g - матрица смежности графа( первые n строк и n столбцов матрицы NMAX*NMAX).
ЗНАЧЕНИЕ:
- недопустимое количество вершин;
- файл пуст;
- нет входного файла;
- ввод завершен без ошибок
РАБОЧИЕ ДАННЫЕ:
i,j - номера вершин;
*f - указатель на входной файл
АЛГОРИТМ: см. алгоритм 3.3., рис. 3.3.
Алгоритм 3.3 Алгоритм модуля VVOD
//ввод количества вершин и графа из файла
if ((f=fopen("f.txt","r"))!=NULL)//файл существует, открытие для чтения
{
fscanf(f,"%d",n);//количество вершин
if ((*n20)) return 5;//недопустимое количество вершин
if (feof(f)) return 4;//файл пуст(i=0;i<(*n);i++)(j=0;j<(*n);j++)(f,"%d",&g[i][j]); //ввод матрицы смежности
}return 3;//нет входного файла0;//успешное завершение
3.3.3 prov1 - проверка на связность
ЗАГОЛОВОК: int prov1(int n,int g[][NMAX])
ФУНКЦИЯ: проверка графа на связность.
ВХОДНЫЕ ДАННЫЕ: количество вершин n, матрица смежности g.
ВЫХОДНЫЕ ДАННЫЕ: код завершения - граф связный/несвязный
ЗНАЧЕНИЕ:
- граф связный
- граф несвязный
РАБОЧИЕ ДАННЫЕ:
v - начальная вершина
massiv - массив меток
i, j - номера вершин
АЛГОРИТМ: см. алгоритм 3.4., рис. 3.4.
Алгоритм 3.4 Алгоритм модуля prov1
int *massiv=(int*)malloc(sizeof(int)*n);/*создание массива меток, где номер ячейки - вершина, содержимое - метка*/
for (int i=0; i < n; i++) massiv[i]=1;//все вершины помечены 1[v]=2;//метка начальной вершины
while (marker(n,massiv,2)!=0)//есть вершины, помеченные 2
{(int i=0; i < n; i++) if (massiv[i]==2){ v=i; break;} //переход к вершине, связанной с v[v]=3;(int j=0; j < n; j++) if ((g[v][j]==1)||(massiv[j]==1)) massiv[j]=2; /*метка связанных вершин*/
}(int i=0; i < n; i++) if (massiv[i]==1) return 6;//граф несвязный
return 0;//граф связный
3.3.4 prov2 - проверка степеней вершин
ЗАГОЛОВОК: int prov2(int n,int g[][NMAX])
ФУНКЦИЯ: подiет степеней вершин, если вершин нечетной степени более двух, то не существует эйлерова пути в графе.
ВХОДНЫЕ ДАННЫЕ: количество вершин n, матрица смежности g.
ВЫХОДНЫЕ ДАННЫЕ: код завершения - эйлеров путь есть/нет.
ЗНАЧЕНИЕ:
- вершин нечетной степени не больше двух
- вершин нечетной степени больше двух
РАБОЧИЕ ДАННЫЕ:
i, j - номера вершин
k - степень вершины
t - количество вершин нечетной степени
АЛГОРИТМ: см. алгоритм 3.5., рис. 3.5.
Алгоритм 3.5 Алгоритм модуля prov2
t=0;
k=0;
for (i=0;i<n;i++)
{for (j=0;j<n;j++) k+=g[i][j];//нахождение степени вершины
if (k%2!=0) t++;//степень вершины нечетная
if (t>2) return 7;//нечетных вершин более двух=0;
}0;
3.3.5 poisk - поиск эйлерова пути
ЗАГОЛОВОК: void Poisk(int v, int n,int g[][NMAX], int *no, int res[NMAX])
ФУНКЦИЯ: нахождение эйлерова пути в графе.
ВХОДНЫЕ ДАННЫЕ: начальная вершина v, количество вершин n, матрица смежности g.
ВЫХОДНЫЕ ДАННЫЕ: массив с результатом, указатель конца массива.
ЗНАЧЕНИЕ: нет.
РАБОЧИЕ ДАННЫЕ:
i, j - номера вершин;
stack - стек;
ns - указатель на следующий после последнего элемента стека;
V - степень вершины;
АЛГОРИТМ: см. алгоритм 3.6., рис. 3.6.
Алгоритм 3.6 Алгоритм модуля poisk
ns=0;
V=0;
stack[ns++]=v;//занос начальной вершины в стек
while (ns!=0)//стек не пуст
{
V=0;
v=stack[ns];//v - значение на вершине стека
for (i = 0; i < n; i++) V+=g[v][i];//степень вершины (V==0) {ns--;res[(*no)++]=v;}//удаление вершины из стека, занос в результат
else
{=0;(g[v][i]!=1) i++;//нахождение ребра[v][i]=0;//удаление ребра
g[i][v]=0;
stack[ns++]=i;//занос второго конца ребра в стек
}
}
3.3.6 VYVOD - вывод сообщений
ЗАГОЛОВОК: void Vyvod(int pr)
ФУНКЦИЯ: вывод сообщений, полученных при вызове других модулей.
ВХОДНЫЕ ДАННЫЕ: код завершения, полученный при вызове одного из модулей.
ВЫХОДНЫЕ ДАННЫЕ: нет.
ЗНАЧЕНИЕ: нет.
РАБОЧИЕ ДАННЫЕ: нет.
АЛГОРИТМ: см. алгоритм 3.7., рис. 3.7.
Алгоритм 3.7 Алгоритм модуля VYVOD
(pr)
{
case 5: {printf("недопустимое количество вершин");getch();break;}
case 3: {printf("нет входного файла");getch();break;}
case 4: {printf("файл пуст");getch();break;}6: {printf("нет эйлерова пути: граф несвязный");getch();break;} 7: {printf("нет эйлерова пути: вершин нечетной степени более 2");getch();break;}:
;
}
3.3.7 marker - подiет меток
ЗАГОЛОВОК: int marker(int n, int massiv[], int metka)
ФУНКЦИЯ: подiет вершин, помеченных определенным значением.
ВХОДНЫЕ ДАННЫЕ: количество вершин n, массив меток massiv[], метк