- 在线时间
- 9 小时
- 最后登录
- 2012-10-15
- 注册时间
- 2010-3-30
- 听众数
- 3
- 收听数
- 0
- 能力
- 0 分
- 体力
- 80 点
- 威望
- 0 点
- 阅读权限
- 20
- 积分
- 53
- 相册
- 0
- 日志
- 0
- 记录
- 1
- 帖子
- 53
- 主题
- 0
- 精华
- 0
- 分享
- 0
- 好友
- 4
升级   50.53% 该用户从未签到
- 自我介绍
- 数学的一个懵懂者。
|
#include <stdio.h>; \" `/ W: U4 {' w8 B! y' U' g: M
#include <string.h>
$ G; _: I3 o4 V7 k; ?3 H) ]7 W! q4 ^struct stack
" F( l# X' K/ k# @, z. c0 _! c{int top , node[210];} f; //顶点的堆栈) F* Z4 b2 M+ i2 A& n
int a[201][201]; //图的邻接矩阵4 b9 C; a& q" P
int n;2 {. k: J" T/ c n$ p
void dfs(int x) //图的深度优先遍历6 z# y% a& U3 x, L% Y% |
{int i;
4 T7 `3 j, \4 tf.top ++; f.node[f.top] = x;& M: e6 X6 L. Z5 R1 Q0 n& \( x
for (i = 1; i <= n; i ++)+ I8 N7 B3 a9 L4 e* g+ j
if (a[i][x] > 0)
7 T) i9 v3 F6 ]6 A( n3 L { a[i][x] = 0; a[x][i] = 0; //删除此边
) e0 C, t) a% j' [) zdfs(i);6 V7 |7 _2 n% q
break; }9 Z" Y' a7 Z# E7 z$ n9 D8 ]
}0 _2 }: A z+ D. o6 c/ I
void Euler(int x) //欧拉路算法$ j* `8 a' A8 q N
{int i , b;+ e. O/ H$ U, e1 ?) [1 h' U
f.top = 0; f.node[f.top] = x; //入栈5 h: M0 ]0 q' H% ~
while (f.top >= 0)
; g o- X$ {3 `' G* p" c$ D{b = 0;! R8 A, |4 I0 _
for (i = 1; i <= n; i ++)
: ]+ v5 @' V7 W, r) Cif (a[f.node[f.top]][i] > 0) " v7 e4 a: j, I; H" M
{b = 1; break;}' F% H+ H y" _4 n; f$ U
if (b == 0) //如果没有点可以扩展,输出并出栈
, U8 O/ u( x3 F2 x) {{ printf("%d " , f.node[f.top]);% W4 l' ~6 ~ C' j' [3 W0 \! g0 S
f.top --;}
5 }& p8 F6 V" f6 k, l5 N l9 Nelse {f.top --; dfs(f.node[f.top+1]);} //如果有,就DFS# v, I d) s- h, [0 e7 i
}
2 `3 k/ m" `! X# L' G; i}
8 D6 A# \$ ^) i( {! a8 nint main()$ M6 T1 L! X( X% E; l
{* j) x7 o' F7 U1 y( J9 ^
int m , s , t , num , i , j , start;
% @3 C& I. O% I //input
' N7 ]6 n; J |/ R+ Hscanf("%d %d" , &n , &m); //n顶点数 m边数/ N% S! [# @# W; L5 x
memset(a , 0 , sizeof(a));
8 Y! |6 h) S3 h/ h for (i = 0; i < m; i ++) T. B& v+ x# g& T i1 d* G7 J
{printf("innput s,t");0 V i3 V$ S! ]5 h7 j' z
scanf("%d %d" , &s , &t);
; z2 t" Z% ~; r a[s][t] = 1; a[t][s] = 1;
6 `1 y# _- q5 T! _( ^2 A1 v}
. n3 N, Q, V0 `+ d8 E0 j$ E+ p9 P/ c //判断是否存在欧拉回路- z Q- }# g0 E" v' X
s = 0; start = 1;
" M7 X1 q7 ^/ A; ?* k1 h. E for (i = 1; i <= n; i ++)
7 K. j2 }( H6 m6 Z$ l0 f; D' }: \{num = 0;
: v! r; }7 M" _7 M3 c1 H& yfor (j = 1; j <= n; j ++)
" U0 `2 I, ~# G/ q num += a[i][j];2 R# p0 ^, ^1 ^
if (num % 2 == 1)
6 e/ Q0 B2 @4 }! S{start = i; s ++;}
+ ~4 z' z2 s s* ^} q* q* [5 z+ t! L6 M6 Z- s
if ((s == 0) || (s == 2))
( F9 ^3 N; |4 z+ \7 HEuler(start);' c0 I. p( n9 P1 [% \
else printf("No Euler path\n");& n% s# N) \0 M. Z
getchar(); getchar();
8 f& S2 |, U4 e6 m% m% _return 0; } |
|