- 在线时间
- 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>/ B& Z& [& I# m- Y
#include <string.h>4 U+ G" a5 ?5 S s+ v- w
struct stack5 s3 g) H3 Q- Y* ^) i
{int top , node[210];} f; //顶点的堆栈
4 d/ r- M" I6 j7 H: I" ^int a[201][201]; //图的邻接矩阵
4 W h4 ~: w; y2 Q% M( ?int n;' I; Q: X% R; Y+ X! u& o9 K2 H. O) |
void dfs(int x) //图的深度优先遍历9 z |6 r" ?' v( D: C4 p- Y
{int i;8 s, @9 O6 b, A
f.top ++; f.node[f.top] = x;
& z N0 g7 r8 H8 Efor (i = 1; i <= n; i ++); |2 L0 S9 }, R7 z) N, a
if (a[i][x] > 0)7 s1 u% O* ^4 O0 G
{ a[i][x] = 0; a[x][i] = 0; //删除此边" ~8 p. X2 o' p% T1 z* {/ F: Y
dfs(i);" {; z5 F; A6 x; Y; a7 z
break; }
5 B' \: n/ j- C& C5 _# R$ r9 R6 z: o3 j! u}
- W/ r; e e1 R' V/ Q! bvoid Euler(int x) //欧拉路算法- e2 E+ E& U6 [+ ]$ `5 ~6 v) M
{int i , b;
, U# S' P' w0 r4 |f.top = 0; f.node[f.top] = x; //入栈7 d5 J% \" n, M% U/ @
while (f.top >= 0)( A$ v! b" V& z2 q
{b = 0;
. ]" o) Q# l& p" m" Z1 m0 Z7 ]+ w8 M for (i = 1; i <= n; i ++) % |& L2 d* |7 n- | h4 M- A
if (a[f.node[f.top]][i] > 0)
, i3 e5 {+ @& V( W{b = 1; break;}
" o& A' v0 \& j( L4 { if (b == 0) //如果没有点可以扩展,输出并出栈
! D3 N7 t/ O$ g2 P{ printf("%d " , f.node[f.top]);" O% W7 G* V- I4 Z* m
f.top --;}) ^1 Q% v- G, K, x: \
else {f.top --; dfs(f.node[f.top+1]);} //如果有,就DFS
& [: k* h4 n4 o% n) u) s} N0 ?9 d* I3 G! q' J5 v
}' o) m( L) j3 ~) R
int main()
/ n$ z: k0 G. p: Y; L; O1 Q{
9 s% n- I( A) ?! t8 S# ^8 O3 Hint m , s , t , num , i , j , start;8 N. ]7 R- [. y I0 _' s
//input
" t0 t% T% I9 W5 P2 q" hscanf("%d %d" , &n , &m); //n顶点数 m边数1 b# M, O, o. ^# z0 O
memset(a , 0 , sizeof(a));7 i! o8 z, n: K/ b0 U7 G8 J& i% O' w' H
for (i = 0; i < m; i ++)
3 I. N. i. u( q. I Q{printf("innput s,t");! v$ ?1 d# w0 g' t# |6 \( b+ H
scanf("%d %d" , &s , &t);
- ]7 ]8 W( a4 C0 U6 X: s" m a[s][t] = 1; a[t][s] = 1;: T& G. z# v* Z4 f3 g, R
}
1 C6 S4 X9 l, E4 l //判断是否存在欧拉回路+ d$ E1 h) z9 T
s = 0; start = 1;
% J, R* I# x: t0 @4 p for (i = 1; i <= n; i ++)1 X# w7 _! S+ [7 E9 m0 g6 n
{num = 0;
$ O$ e/ L+ }: s S) Ufor (j = 1; j <= n; j ++)
! u% ]- C2 p( i w5 J num += a[i][j];* N5 k/ o8 \- S# {
if (num % 2 == 1) # s% ^$ ` U7 }* I6 N2 p) B
{start = i; s ++;}4 v/ r: X: w/ _: H9 |8 @
}
# q8 b- h# B' v+ L3 Oif ((s == 0) || (s == 2))
% S6 X" i0 o0 W4 Z! W( {5 sEuler(start);
9 k0 V0 _+ s* e' m9 q else printf("No Euler path\n");* b, ~( w% W$ `5 \5 Q d
getchar(); getchar();1 u: K* `: @/ J0 J7 D. L
return 0; } |
|