当前位置:首页 >> 信息与通信 >>

欧拉回路代码


#include <stdio.h>
#include <stdlib.h>
#include <memory.h>

struct street
{
int x, y; /* ending junctions */
int number; /* numbe

r of the street */

int nextx, nexty; /* single linked lists started by junctions[i] */

int prev, next; /* index of previous and next street in the solution */
}
streets[2048];

int junctions[64]; /* index of unused street going to junction with smallest number */

int path(int junction, int *start_street, int *end_street) /* returns ending junction */
{
int street, s;

street = -1;

for(;;)
{
if((s = junctions[junction]) == -1)
{
if(street == -1)
*start_street = -1;

*end_street = street;

return junction;
}

if(streets[s].next == -1) /* unused street */
{
if(street == -1)
{
streets[s].prev = -2;
*start_street = s;
}
else
{
streets[s].prev = street ;
streets[street].next = s;
}

streets[s].next = -2;

junctions[junction] = (streets[s].x == junction)
? streets[s].nextx : streets[s].nexty;

junction = (streets[s].x != junction) ?
streets[s].x : streets[s].y;

street = s;
}
else
{
junctions[junction] = (streets[s].x == junction) ?
streets[s].nextx : streets[s].nexty;
}
}
}

int number_cmp(const void *a, const void *b)
{
return ((struct street *)a)->number - ((struct street *)b)->number;
}

#define min(a, b) (((a) < (b)) ? (a) : (b))

void print(int start_street)
{
int s;

printf("%d", streets[start_street].number);

for(s = streets[start_street].next; s != start_street; s = streets[s].next)
printf(" %d", streets[s].number);

printf("\n");
}

void main()
{
int count, junction, start_street, street, i, s, e, ss;

for(;;)
{
count = 0;

for(;;)
{
scanf("%d%d", &streets[count].x, &streets[count].y);
if(!streets[count].x || !streets[count].y) break;

scanf("%d", &streets[count++].number);
}

if(!count) break;

junction = min(streets[0].x, streets[0].y);

qsort(streets, count, sizeof(streets[0]), number_cmp);

memset(junctions, -1, sizeof(junctions));

for(i = count - 1; i >= 0; i--)
{
streets[i].nextx = junctions[streets[i].x];
junctions[streets[i].x] = i;

streets[i].nexty = junctions[streets[i].y];
junctions[streets[i].y] = i;

streets[i].prev = -1;
streets[i].next = -1;
}

if(path(junction, &start_street, &e) != junction)
goto fail;

streets[start_street].prev = e;
streets[e].next = start_street;

street = start_street;

do
{
again:
if(path(junction, &s, &e) != junction)
goto fail;

if(s != -1 && e != -1)
{
ss = streets[street].prev;

streets[s].prev = ss;
streets[ss].next = s;

streets[street].prev = e;
streets[e].next = street;

goto again;
}

street = streets[street].prev;

junction = (streets[street].x != junction) ?
streets[street].x : streets[street].y;
}
while(street != start_street);

print(start_street);

continue;

fail:
printf("Round trip does not exist.\n");
}
}

相关文章:
欧拉回路
欧拉回路 一、 算法思想 欧拉回路是将图中所有边遍历一遍且仅一遍,并找到图中...代码 #include <iostream> using namespace std; #include<stdlib.h> struct Eule...
欧拉回路
(e)的,这种算法的特点是最后倒序 输出,这个地方需要特别重视一下,在图有欧拉通路或者有欧拉回路的时候 ,我们总可以从一 个合适的点出发,找到一条欧拉路.可以做...
欧拉回路
一、欧拉回路 所谓欧拉回路与哥尼斯堡 7 桥问题相联系的. 在哥尼斯堡 7 桥...欧拉回路代码 2页 免费 欧拉回路与中国邮递员问... 3页 免费 欧拉回路的算法...
欧拉回路解题实例分
欧拉回路解题实例分_计算机软件及应用_IT/计算机_专业资料。题目意思: 给你一个...代码: [cpp] <SPAN style="FONT-SIZE: 18px">#include<iostream> #include...
欧拉回路的算法演示
欧拉回路的算法演示_数学_自然科学_专业资料。欧拉图中欧拉回路的算法,演示,及分析...求欧拉回路,Fleury算法的... 6页 1下载券 欧拉回路代码 2页 免费 第19讲 ...
欧拉回路
欧拉回路_军事/政治_人文社科_专业资料。三、欧拉回路 1、欧拉路:在无孤立顶点...欧拉回路代码 2页 免费 欧拉回路与中国邮递员问... 3页 免费 欧拉回路的算法...
欧拉回路设计报告
欧拉回路设计报告_交通运输_工程科技_专业资料。你值得拥有。合肥学院 计算机科学与技术系课程设计报告 2012 ~2013 学年第 二 学期 课学学专指业导班教生姓 程...
求欧拉回路的Fleury算法
分析总结: Fleury 算法是求欧拉图的十分有效的算法,在执行过程中需要用到类似 ...欧拉回路代码 2页 免费 ACM常用模板 欧拉回路(... 1页 免费 第19讲 欧拉回路...
欧拉回路
欧拉回路 const maxn=100; var g:array[1..maxn,1..maxn] of longint; ...欧拉回路代码 2页 免费 欧拉回路与中国邮递员问... 3页 免费 第19讲 欧拉回路...
欧拉回路的Fleury算法
欧拉回路的Fleury算法_五年级其它课程_其它课程_小学教育_教育专区 暂无评价|0人阅读|0次下载|举报文档 欧拉回路的Fleury算法_五年级其它课程_其它课程_小学教育_...
更多相关标签:
欧拉回路 | 欧拉回路算法 | 求欧拉回路 | 欧拉通路和欧拉回路 | 无向图欧拉回路 | 求欧拉回路算法 | 欧拉回路 证明 | 混合图欧拉回路 |