問題描述:
給定一個無向圖G,一條路徑經過圖G的每一條邊,且僅經過一次,這條路徑稱為歐拉路徑(Eulerian Tour),如果歐拉路徑的起始頂點和終點是同一頂點,則稱為歐拉回路(Eulerian circuit).
算法:
無向圖G存在歐拉路徑的充要條件:圖G是連通的,且至多除兩個點外(可以為0個,連接圖不可能有且僅有一個頂點的度為奇數)其它所有頂點的度為偶數.
無向圖G存在歐拉回路的充要條件:圖G是連通的且所有頂點的度為偶數;
算法描述:
1 tour: 數組,用于存儲歐拉路徑,反序輸出即為歐拉路徑
2 pos: int
3
find_eulerian_circuit()
4 {
5 pos=0;
6 find_circuit(1);
7 }
8
find_eulerian_tour()
9 {
10 find a vertex i ,the degree of which is odd
11 pos=0;
12 find_circuit(i);
13 }
14
find_circuit(vertex i)
15 {
16 while(exist j,(i,j) is the edge of G)
17 {
18 remove edge(i,j);
19 find_circuit(j);
20 }
21 tour[pos++]=i;
22 }
23
USACO 3.2 Riding the fence,就是一個求歐拉路徑的問題.
問題描述:
Farmer John owns a large number of fences that must be repaired annually. He traverses the fences by riding a horse along each and every one of them (and nowhere else) and fixing the broken parts.
Farmer John is as lazy as the next farmer and hates to ride the same fence twice. Your program must read in a description of a network of fences and tell Farmer John a path to traverse each fence length exactly once, if possible. Farmer J can, if he wishes, start and finish at any fence intersection.
Every fence connects two fence intersections, which are numbered inclusively from 1 through 500 (though some farms have far fewer than 500 intersections). Any number of fences (>=1) can meet at a fence intersection. It is always possible to ride from any fence to any other fence (i.e., all fences are "connected").
Your program must output the path of intersections that, if interpreted as a base 500 number, would have the smallest magnitude.
There will always be at least one solution for each set of input data supplied to your program for testing.
PROGRAM NAME: fence
INPUT FORMAT
|
Line 1:
|
The number of fences, F (1 <= F <= 1024)
|
|
Line 2..F+1:
|
A pair of integers (1 <= i,j <= 500) that tell which pair of intersections this fence connects.
|
SAMPLE INPUT (file fence.in)
9
1 2
2 3
3 4
4 2
4 5
2 5
5 6
5 7
4 6
OUTPUT FORMAT
The output consists of F+1 lines, each containing a single integer. Print the number of the starting intersection on the first line, the next intersection's number on the next line, and so on, until the final intersection on the last line. There might be many possible answers to any given input set, but only one is ordered correctly.
SAMPLE OUTPUT (file fence.out)
1
2
3
4
2
5
4
6
5
7
解答:簡單的歐拉路徑問題,圖采用鄰接表存儲,附原碼
/*
ID: kuramaw1
PROG: fence
LANG: C++
*/
#include <fstream>
using std::ifstream;
using std::ofstream;
using std::endl;
#ifdef _DEBUG
#include <iostream>
using std::cout;
#endif
#define MAX_V 500
#define MAX_EDGE 1025
#define MAX(a,b) ((a)>(b)?(a):(b))
struct grapha
{
struct node
{
short v;
node * next;
node(const short _v=-1):v(_v),next(NULL)
{
}
};
struct ver
{
node * r;
short d;//degree
ver():d(0)
{
r=new node();
}
~ver()
{
node * n=r;
while(n!=NULL)
{
node * t=n;
n=n->next;
delete t;
}
}
inline void add_neighbor(const short &v)
{
node * t=new node(v);
node * p=r;
node * n=p->next;
while(n!=NULL && v>n->v)
{
p=n;
n=n->next;
}
p->next=t;
t->next=n;
d++;
}
inline void remove_neighbor(const short &v)
{
node * p=r;
node * n=p->next;
while(n!=NULL && v!=n->v)
{
p=n;
n=n->next;
}
if(n!=NULL)
{
p->next=n->next;
delete n;
d--;
}
}
};
ver v[MAX_V];
short n;
short * tour;
short pos;
grapha():n(0),tour(NULL)
{
}
void add_edge(const short &_u,const short &_v)
{
v[_u-1].add_neighbor(_v-1);
v[_v-1].add_neighbor(_u-1);
short t=MAX(_u,_v);
if(t>n)
n=t;
}
void find_tour(const short &s)
{
while(v[s].d>0)
{
short j=v[s].r->next->v;
v[s].remove_neighbor(j);
v[j].remove_neighbor(s);
find_tour(j);
}
tour[pos++]=s+1;
}
void Eulerian_tour(short * _tour)
{
tour=_tour;
pos=0;
bool b=false;
for(int i=0;i<n;i++)
if(v[i].d % 2!=0)
{
find_tour(i);
b=true;
break;
}
if(!b)
find_tour(0);
}
};
grapha g;
short tour[MAX_EDGE];
short f;
int main()
{
ifstream in("fence.in");
in>>f;
for(short i=0;i<f;i++)
{
short u,v;
in>>u>>v;
g.add_edge(u,v);
}
//do
g.Eulerian_tour(tour);
//out
ofstream out("fence.out");
for(int i=f;i>=0;i--)
out<<tour[i]<<endl;
out.close();
}
posted on 2009-08-12 21:18
kuramawzw 閱讀(591)
評論(0) 編輯 收藏 引用 所屬分類:
圖論