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

欧拉回路代码


#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");
}
}

相关文章:
欧拉回路代码
7页 2下载券 欧拉回路的Fleury算法 7页 1下载券 算法合集之《欧拉回路性... 41页 免费 欧拉回路的算法演示 2页 2下载券喜欢此文档的还喜欢 ...
求欧拉回路,Fleury算法的C语言实现
欧拉回路,Fleury算法的C语言实现_IT/计算机_专业资料。ACM 算法 数据结构欧拉(Euler)通路/回路 1、基本概念: 、基本概念: (1)定义 欧拉通路 (欧拉迹)—通过...
欧拉回路的判定_设计文档
软件设计文档 I 文档管理信息表项目名称 版本 内容 关键字 参考文档 创建时间 创建人 最新发布日期 欧拉回路判定 编写代码 欧拉回路 数据结构课本(C 语言版) 文档...
欧拉回路
欧拉回路 一、 算法思想 欧拉回路是将图中所有边遍历一遍且仅一遍,并找到图中...代码 #include <iostream> using namespace std; #include<stdlib.h> struct Eule...
欧拉回路解题实例分
欧拉回路解题实例分_计算机软件及应用_IT/计算机_专业资料。题目意思: 给你一个...代码: [cpp] <SPAN style="FONT-SIZE: 18px">#include<iostream> #include...
欧拉回路
欧拉回路_军事/政治_人文社科_专业资料。三、欧拉回路 1、欧拉路:在无孤立顶点...欧拉回路代码 2页 免费 欧拉回路与中国邮递员问... 3页 免费 欧拉回路的算法...
数据结构与算法课程设计的心得体会之欧拉回路
数据结构与算法课程设计的心得体会之欧拉回路_工学_高等教育_教育专区。合肥学院...只要我们足够的冷静的分析错误的大概位子处的代码, 不难找出错误的原因, 消除 ...
图论实验代码
图论实验报告(代码) 学号:1241902129 姓名:肖尧 1.写一个程序,输入一个图,一...8 3.写一个程序,输入一个图,确定是否是欧拉图,如果是欧拉图,输出欧拉回路。...
欧拉回路的Fleury算法
欧拉回路的Fleury算法_五年级其它课程_其它课程_小学教育_教育专区 暂无评价|0人阅读|0次下载|举报文档 欧拉回路的Fleury算法_五年级其它课程_其它课程_小学教育_...
更多相关标签:
欧拉回路 | 欧拉回路算法 | 求欧拉回路 | 无向图欧拉回路 | 有向图的欧拉回路 | 欧拉回路c | 欧拉通路和欧拉回路 | 求欧拉回路算法 |