Eulerian path


1. Introduction

Describe the problem: for the undirected graph G = (V, E) define all the way from the top of stems passing through all vertices each vertex only just over 1 times.
The idea of the algorithm: technical use depth-first search by marking the peak went through during the search.
Description of inputs and outputs of the problem:
Input Data for file File5.inp
- The first line contains the number n is the number of vertices in a graph (0 <n <100)
- Field 2 record peak comes.
- Line i + 2 (1 <= i <= n) contains n number of A [i, 1], A [i, 2], ..., A [i, n] each number separated by a space.
Data output: print screen all the way through the top (if any).

2. Source code:

#include <stdio.h>
#include <conio.h>
#include <iostream.h>
#define Filename "File5.inp"
int Count = 0, NumberOfEdge=0;
int *L;
int **A,n;
int _Start=0;
void Read_File() {
int TopTier;
FILE*f = fopen(Filename,"rb");
fscanf(f,"%d",&n);
cout<<"Matrix corresponding link: \n"<<n<<endl;
*A = new int [n];
for(int i =0;i<n;i++) {
A[i] = new int [n];
TopTier = 0;
for(int j =0;j<n;j++) {
fscanf(f,"%d",&A[i][j]);
cout<<A[i][j]<<" ";
if(A[i][j] == 1)
TopTier++;
}
if(TopTier%2==1)
_Start = i;
NumberOfEdge+=TopTier;
cout<<endl;
}
fclose(f);
NumberOfEdge = NumberOfEdge/2;
L = new int [NumberOfEdge+1];
L[0] = _Start;
}
void PrintPath() {
Count++;
cout<<endl<<_Start+1;
for (int i = 1; i<=NumberOfEdge; i++)
cout<<" -> "<<L[i]+1;
}
//Recursion Function
void Try(int _Edge) {
if(_Edge > NumberOfEdge)
PrintPath();
else {
for(int i = 0; i<n; i++)
if( A[L[_Edge-1]][i]>0){
L[_Edge] = i;
A[L[_Edge-1]][i]=A[i][L[_Edge-1]]=0; //Delete edge;
Try(_Edge+1); //Find next edge;
A[L[_Edge-1]][i]=A[i][L[_Edge-1]]=1; //Restore edge;
L[_Edge] = 0;
}
}
}
void main() {
Read_File();
cout<<"\nPATH: ";
Try(1);
if(Count==0)
cout<<" NOTHING";
delete *A,L;
getch();
}

3. Result:

Euler_Result_2


Advertisements