欧拉回路程序

/*--------------------------------------------------------------------

* Project : ETrail - a Eulerian Trail finder

* Module: ETrail.cpp

* Author: Wesley Tseng

* Created : 1999-12-10

* Updated : 1999-12-12

* Notes :

* Copyright : (c) Copyright 1999-2000 by Wesley Tseng

* You may freely copy or redistribute this software, so

* long as there is no profit made from its use, sale

* trade or reproduction. You may not change this copy-

* right notice, and it must be included in any copy made

--------------------------------------------------------------------*/

#include <iostream.h>// cin, cout

#include <process.h>// exit() needs

typedef struct NodeT {

int info

NodeT *next

} *Node

typedef enum {FALSE, TRUE} Boolean

/*--------------------------------------------------------------------

* Subroutine: input() - a adjacency-structure generator

* Notes :

* input : NodeNumber (number of nodes)

* output : head (adjacency-structure)

--------------------------------------------------------------------*/

Node *input(int NodeNumber)

{

Node *head

Node *tail

char dummy

int input1, input2

int register i

Node node1, node2, ptr

head = new Node[NodeNumber]

tail = new Node[NodeNumber]

if(!head || !tail) {

cout <<"Out of memory..." <<endl

exit(1)

}

for(i = 0i <NodeNumberi++)

{

ptr = new NodeT

if(!ptr) {

cout <<"Out of memory..." <<endl

exit(1)

}

head[i] = tail[i] = ptr

head[i]->info = 0

}

cout <<"\nEnter connection pair(s)..."

cout <<"\nInput 0-0 while complete...\n"

for()

{

cin >>input1 >>dummy >>input2

if( (input1 == 0) || (input2 == 0) )

break

if( (input1 >NodeNumber) || (input2 >NodeNumber) ||

(input1 <0) || (input2 <0) || (input1 == input2) )

{

cout <<"Invalid pair..." <<endl

continue

}

input1--

input2--

node1 = new NodeT

node2 = new NodeT

if( (!node1) || (!node2) )

{

cout <<"Out of memory..." <<endl

exit(1)

}

node1->info = input1

node1->next = NULL

node2->info = input2

node2->next = NULL

tail[input1]->next = node2

tail[input1] = node2

head[input1]->info++

tail[input2]->next = node1

tail[input2] = node1

head[input2]->info++

}

return head

}

/*--------------------------------------------------------------------

* Subroutine: notEulerTrail() - Eulerian Trail justifier

* Notes :

* input : head (adjacency-structure)

* NodeNumber (number of nodes)

* output : TRUE -- not a Eulerian Trail

* FALSE -- a Eulerain Trail

--------------------------------------------------------------------*/

Boolean notEulerTrail(Node *head, int NodeNumber)

{

int register i

for(i = 0i <NodeNumberi++)

if((head[i]->info % 2) == 1)

return TRUE

return FALSE

}

/*--------------------------------------------------------------------

* Subroutine: hasBranch() - branch finder

* Notes :

* input : head (adjacency-structure)

* NodeNumber (number of nodes)

* output : the number of node which still has branch

--------------------------------------------------------------------*/

int hasBranch(Node *head, int NodeNumber)

{

int register i

for(i = 0i <NodeNumberi++)

if(head[i]->info != 0)

break

return i

}

/*--------------------------------------------------------------------

* Subroutine: remove() - remove a node from current linked list

* Notes :

* input : head (adjacency-structure)

* me (the node-number to be handled)

* last (the node-number to be removed)

* output : (none)

--------------------------------------------------------------------*/

void remove(Node *head, int me, int last)

{

Node ptr

Node temp

ptr = head[me]

while(ptr->next != NULL)

{

temp = ptr->next

if(temp->info == last)

{

head[me]->info--

ptr->next = temp->next

temp->next = NULL

delete temp

return

}

ptr = temp

}

}

/*--------------------------------------------------------------------

* Subroutine: Prepare - transform a adjacency-structure to another

*for display the trail

* Notes :

* input : head (adjacency-structure)

* NodeNumber (number of nodes)

* output : EulerTrail (reduced adjacency-structure)

--------------------------------------------------------------------*/

Node *Prepare(Node *head, int NodeNumber)

{

Node *EulerTrail

Node *EulerHead

Node ptr

int register i

int register me

int last

EulerTrail = new Node[NodeNumber]

EulerHead = new Node[NodeNumber]

if( (!EulerTrail) || (!EulerHead) ) {

cout <<"Out of memory..." <<endl

exit(1)

}

for(i = 0i <NodeNumberi++)

{

ptr = new NodeT

if(!ptr) {

cout <<"Out of memory..." <<endl

exit(1)

}

ptr->next = NULL

ptr->info = 0

EulerHead[i] = ptr

}

while( (me = hasBranch(head, NodeNumber)) <NodeNumber)

{

for(i = 0i <NodeNumberi++)

EulerTrail[i] = EulerHead[i]

last = me

while(1) {

remove(head, me, last)

ptr = head[me]->next

if(ptr == NULL)

break

head[me]->next = ptr->next

ptr->next = EulerTrail[me]->next

EulerTrail[me]->next = ptr

EulerTrail[me] = ptr

EulerHead[me]->info++

head[me]->info--

last = me

me = ptr->info

}

}

return EulerHead

}

/*--------------------------------------------------------------------

* Subroutine: Display - show out the trail

* Notes :

* input : EulerTrail (adjacency-structure)

* NodeNumber (number of nodes)

* output : number (number of Eulerain Cycles)

--------------------------------------------------------------------*/

int Display(Node *EulerTrail, int NodeNumber)

{

int number

Node ptr

int first

number = 0

while(1)

{

first = 0

while(EulerTrail[first]->info == 0)

{

first++

if(first == NodeNumber)

return number

}

number++

cout <<endl <<first + 1

ptr = EulerTrail[first]->next

while(ptr != NULL)

{

EulerTrail[first]->info--

EulerTrail[first]->next = ptr->next

first = ptr->info

ptr->next = NULL

cout <<" ->" <<first + 1

ptr = EulerTrail[first]->next

}

}

}

/*--------------------------------------------------------------------

* Subroutine: main() - the main function

* Notes :

* input : (none)

* output : (none)

--------------------------------------------------------------------*/

void main(void)

{

Node *head

Node *EulerTrail

int NodeNumber

int register i

do {

cout <<"Enter the Number of Nodes : "

cin >>NodeNumber

} while (NodeNumber <2)

head = input(NodeNumber)

if(notEulerTrail(head, NodeNumber))

{

cout <<"The graph you inputed is not a Euler Trail...\n"

exit(1)

}

EulerTrail = Prepare(head, NodeNumber)

cout <<"Euler Trail Path is"

i = Display(EulerTrail, NodeNumber)

cout <<endl

if(i != 1)

cout <<"It's not a Eulerain Cycle..." <<endl

}

 输入＆输出

Etrail.exe <Input1.dat

Enter the Number of Nodes :

Enter connection pair(s)...

Input 0-0 while complete...

Euler Trail Path is

1 ->2 ->4 ->3 ->5 ->6 ->4 ->5 ->2 ->3 ->1 Input1.dat内容：

6

1-2

1-3

2-4

2-3

2-5

3-5

4-5

3-4

4-6

6-5

0-0

这里有更详细的下载：http://www.pudn.com/downloads9/doc/detail31913.html

首先要让正明根坦告据欧拉路径的存在条件来判断一个图是否存在欧拉路径,判断条件为如下3条

对于一个无向图，如果它每个点的度都是偶数，那么它存在一条欧拉回路；

如果有且仅有2个点的度为奇数，那么它存在一条欧拉路；

如果清肢超过2个点的度为奇数，那么它就不存在欧拉路了。

然后可以用Fleury算法求欧拉路径,可以参照

http://www.cnblogs.com/Lyush/archive/2013/04/22/3036659.html

---