int push(int a)
{
s[m]=a;
m++;
if(m>r)
printf("Stack Full\n");
return a;
}
int pop()
{
m--;
return s[m];
}
main() //кусок
{
int x=0,y=0,l=0,z=0,m=0;
push(q); //q начальная вершина графа
while(m>0) //пока времанный стек не пустой
{
x=pop(); //забиваем иксу верхний элемент стека
m++; //m-счетчик стека, m++ тк pop вытащит верх из стека, что нам сдесь не нужно
for(y=0,l=-1;y<n;y++) //проверяем существуют ли непройденные ребра, n-количество вершин
if(g[x][y]==1)
{
l++;
break;
}
if(l!=-1) //если l!=1 то существуют
{
g[x][l]=0; //помечаем ребро как пройденное
g[l][x]=0;
push(l); //кидаем l в стек
}
else //иначе если пройденного ребра нет
{
c[z]=x; //переносим вершину x из стека в масив c[z], где будет содержатся сам путь
z++; //что-бы записать след вершину
pop(); //вытаскиваем x из стека
}
}
for(i=0;i<r;i++) //выводим путь, r-количество ребер которые зараннее посчитаны
printf("%3d",c);
}
Поиск Эйлерова цикла в графе
Проверки на связанность, ориентированность, четность ребер провел. Вход граф содержищий эйлеров цикл.
Получаю путь содержащий только нули. Пишу второй день, мозг болит. Решил наконец просить помощи. Пишу на Си
Пишу по этому алгоритму:
Вход: эйлеров граф G(V,E), заданный матрицей смежности.
Выход: последовательность вершин эйлерова цикла.
S - стек для хранения вершин, C – стек для хранения вершин эйлерова цикла.
Выбрать произвольно вершину а
a>> S(поместить вершину a в стек S)
while ( S не пуст) do
x=top(s) (верхний элемент стека)
if имеется не пройденное ребро (x,y)
then пометить ребро как пройденное
y>>s (поместить y в стек)
else
- переместить вершину X из стека S в стек C
- удалить вершину из стека
end if
end while
Вот что написал:
Код:
Заранее спасибо.