Справочник функций

Ваш аккаунт

Войти через: 
Забыли пароль?
Регистрация
Информацию о новых материалах можно получать и без регистрации:

Почтовая рассылка

Подписчиков: -1
Последний выпуск: 19.06.2015

Поиск Эйлерова цикла в графе

68K
27 мая 2011 года
archibaldo
1 / / 06.03.2011
Столкнулся с проблемой поиска цикла в графе заданной матрицей смежности.
Проверки на связанность, ориентированность, четность ребер провел. Вход граф содержищий эйлеров цикл.
Получаю путь содержащий только нули. Пишу второй день, мозг болит. Решил наконец просить помощи. Пишу на Си
Пишу по этому алгоритму:
Вход: эйлеров граф 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


Вот что написал:
Код:
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);
}

Заранее спасибо.
Реклама на сайте | Обмен ссылками | Ссылки | Экспорт (RSS) | Контакты
Добавить статью | Добавить исходник | Добавить хостинг-провайдера | Добавить сайт в каталог