Euler Circuit

Posted by admin on March 18, 2012 in Programming with Comments closed | ∞

In this post we will publish our solution to the Euler Circuit Problem, it was an assignment in the “intro to computer science”. Code is Written in C.
Site of class intro to computer science http://www.corelab.ntua.gr/courses/introcs/shmmy/

Assigment subject is:

“Write an Algorithm in C that has as input a graph in adjacency matrix form and it gives as output an Euler Circuit”

#include
#include
#include "stack.h" /* Βιβλιοθήκη με συναρτήσεις για χειρισμό στοίβας */
#define max 25 /* Μέγιστος αποδεκτός αριθμός κορυφών */
 
/* Begin fucntion prototypes */
void read_adj(int [max][max],int);
int euler_check_un(int [max][max],int);
int euler_check_di(int [max][max],int);
void euler_un(int [max][max],int,NodePtr *,char [max]);
NodePtr euler_di(int [max][max],int,NodePtr *,NodePtr *,char [max]);
void fill_Alpha(char [max]);
void print_stack(NodePtr *,char [max]);
/* End function prototypes */
 
int location = 0 ; /* Global μεταβλητή για να κρατάμε το που βρισκόμαστε κατα την διάρκεια της διάσχησης ενός γράφου */
 
int main()
{
    int adj[max][max], n, choice ;
    char Alpha[max]; /* Πίνακας για αντιστοιχεία αριθμών με γράμματα */
    NodePtr stack = NULL, circuit = NULL, cir ;
 
    system("chcp 1253 &gt; nul");  /* Για την εμφάνιση ελληνικών ! */
 
    fill_Alpha(Alpha);
 
    printf("Επιλέξτε τον τύπο του γράφου που θα εισάγετε:");
    printf("\n1)Μη Κατευθυνόμενος");printf("\n2)Κατευθυνόμενος");
    printf("\nΕπιλογή:"); scanf("%d",&amp;choice);
    if( (choice!=1) &amp;&amp; (choice!=2) ) /* Έλεγχος μη έγκυρης επιλογής */
    {
        printf("\nΕισάγατε μη έγκυρη επιλογή το πρόγραμμα θα τερματίσει την λειτουργεία του\n");
        return 0;
    }
    printf("\nΠληκτρολογείστε τον αριθμό των κορυφών :"); scanf("%d", &amp;n);
    read_adj(adj,n); /* Διάβασμα πίνακα γειτνίασης κατα σειρά */
 
    if(choice==1) /* Μη κατευθυνόμενος γράφος */
    {
        if(euler_check_un(adj,n)) /* Αν ο βαθμός κάθε κορυφής είναι άρτιος , υπάρχει κύκλος Euler */
        {
            printf("\nΟ μη κατευθυνόμενος γράφος που εισάγατε έχει τον εξής κύκλο Euler:\n");
            euler_un(adj,n,&amp;stack,Alpha);
        }
        else /* Αλλιώς δεν υπάρχει κύκλος Euler */
            printf("\nΟ γράφος που εισάγατε δεν έχει κύκλο Euler");
    }
    if(choice==2) /* Κατευθυνόμενος γράφος */
    {
        if(euler_check_di(adj,n)) /* Αν ο αριθμός εισόδων είναι ίδιος με αυτόν των εξόδων σε κάθε κορυφή τότε υπάρχει κύκλος Euler */
        {
            printf("\nΟ κατευθυνόμενος γράφος που εισάγατε έχει τον εξής κύκλο Euler:\n");
            cir = euler_di(adj,n,&amp;stack,&amp;circuit,Alpha);
            print_stack(&amp;cir,Alpha);
        }
        else /* Αλλιώς δεν υπάρχει κύκλος Euler */
            printf("\nΟ γράφος που εισάγατε δεν έχει κύκλο Euler");
    }
 
    printf("\n");
    return 0;
}
 
/* FUNCTIONS */
 
void read_adj(int adj[max][max],int n)
{
    int i, j;
 
    for(i=0;iinfo]);
        p = p-&gt;next;
    }
}
int euler_check_un(int adj[max][max],int n)
{
    int i, j, sum;
 
    for(i=0;iinfo]);
        p = p-&gt;next;
    }
}