Thuật toán tìm đường đi Euler:

Bước 1 (Khởi tạo):

            u=< đỉnh có deg+(1)-deg-(1) =1 >; stack = f; CE = f;

u => Stack; // Đưa u vào stack;

// chu trình       u=< đỉnh bất kỳ >; stack = f; CE = f;

u => Stack; // Đưa u vào stack;

Bước 2 (Lặp):

            while (stack ≠f) {

                        v = <đỉnh đầu stack>;

                        if (Ke(v) ≠ f )  {

                                    t =<đỉnh đầu trong danh sách Ke(v)>;

                                    t => Stack; // đưa t vào stack;

                                    E = E \(v,t); //loại bỏ cạnh (v,t) đã đi qua;

                        }

                        else { // nếu Ke(v) = f

                                    v = Pop(Stack); v=>CE; //Lấy v ra khỏi Stack và đưa vào CE

                        }

            }

Bước 3 (Trả lại kết quả)           Lật ngược các đỉnh đã được lưu trong CE ta nhận được đường đi Euler.

CODE

#include <conio.h>

#include <stdio.h>

#include <iostream.h>

#include <fstream.h>

/*********/

int *CE;

struct stack{

            int* value;

            int k;

} *STACK;

/*********/

void create(stack *s,int size){

            s->value = new int[size];

            s->k = 0;

}

void push(stack *s,int value){

            s->value[s->k] = value;

            s->k++;

}

int pop(stack *s){

            s->k--;

            return(s->value[s->k]);

}

int top(stack *s){

            return s->value[s->k-1];

}

int empty(stack *s){

            return(!s->k);

}

/*********/

void euler(int **matrix,int n){

            /* Khoi tao */

            int i,topValue,k=0;

            push(STACK,0);

            //

            while(!empty(STACK)){

                        topValue=top(STACK);

                        for(i=0;i<n;i++){

                                    if(matrix[topValue][i] != 0){

                                                push(STACK,i);

                                                matrix[topValue][i]=0;

                                                break;

                                    }

                        }

                        if(i==n){

                                    topValue = pop(STACK);

                                    CE[k] = topValue;

                                    k++;

                        }

            }

            //IN KQ

            printf("

Chu trinh Euler :

");

            for(i=k-1;i>=0;i--){

                        printf("%d ",CE[i]+1);

            }

}

void main(){

            clrscr();

            int **a,k,i,j,stackSize = 0;

            FILE *in;

            in = fopen("input.txt","r");

            //Doc chi so mang va tao mang 2 chieu

            fscanf(in,"%d",&k);

            a = new int*[k];

            for(i=0;i<k;i++){

                        a[i] = new int[k];

            }

            //Doc gia tri mang

            for(i=0;i<k;i++){

                        for(j=0;j<k;j++){

                                    fscanf(in,"%d",&a[i][j]);

                        }

            }

            //In mang ma tran

            for(i=0;i<k;i++){

                        for(j=0;j<k;j++){

                                    printf("%d ",a[i][j]);

                        }

                        printf("

");

            }

            //Tinh toan co stack

            for(i=0;i<k;i++){

                        for(j=0;j<k;j++){

                                    if(a[i][j] != 0){

                                                stackSize++;

                                    }

                        }

            }

            //Tao stack va mang CE

            create(STACK,stackSize);

            CE = new int[stackSize+1];

            //

            euler(a,k);

            getch();

}