posts - 12,  comments - 16,  trackbacks - 0
问题描述:
      
给定一个无向图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 阅读(326) 评论(0)  编辑 收藏 引用 所属分类: 图论

只有注册用户登录后才能发表评论。
【推荐】超50万行VC++源码: 大型组态工控、电力仿真CAD与GIS源码库
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理


<2009年8月>
2627282930311
2345678
9101112131415
16171819202122
23242526272829
303112345

常用链接

留言簿(5)

随笔分类

随笔档案

文章档案

Algorithm

搜索

  •  

最新评论

阅读排行榜

评论排行榜