- 在线时间
- 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>0 [7 X+ f1 A# f' A" v+ l0 D
#include <string.h>4 H9 T; X9 D$ ~& o% Y; A
struct stack+ P' s1 p H0 j+ z% w
{int top , node[210];} f; //顶点的堆栈
! O+ h, c T( J5 q: V" tint a[201][201]; //图的邻接矩阵
1 U3 h" X) q6 s; ]1 L Xint n;/ f" v) V" [0 r
void dfs(int x) //图的深度优先遍历0 [. C1 _+ g- Z* m' u
{int i;
" n; r" [3 p" T8 ]! uf.top ++; f.node[f.top] = x;
: K5 F0 D' P& _+ G; W" Yfor (i = 1; i <= n; i ++)
# @/ M2 w% N8 kif (a[i][x] > 0)
# _- w4 `7 k8 h8 c. b1 V+ Y* y { a[i][x] = 0; a[x][i] = 0; //删除此边5 V; p5 R6 N: X% u, f* L% k, L
dfs(i);% q# @& H! G, a
break; }
" e1 i4 u5 ^: C' b9 ?} h0 s* M5 @* U/ J3 K* v
void Euler(int x) //欧拉路算法
5 u0 D, p, V* H; _2 Q{int i , b;0 i4 {4 m0 X" Y9 x% {
f.top = 0; f.node[f.top] = x; //入栈
2 o& r$ p9 g) x# v- d. ]while (f.top >= 0)) |6 w8 \3 z# B' e
{b = 0;- e. t5 g% i$ p
for (i = 1; i <= n; i ++) + g& ^* P) J) q; S0 S* m: a. L# @
if (a[f.node[f.top]][i] > 0)
4 k7 c2 B9 v1 H4 Z5 h6 J{b = 1; break;}- o" W) [2 X: s* U* F
if (b == 0) //如果没有点可以扩展,输出并出栈# D, ?/ v! V) o b' ?' y
{ printf("%d " , f.node[f.top]);3 p" i' _8 C6 M# c9 q
f.top --;}) |% P* t2 z' q- K
else {f.top --; dfs(f.node[f.top+1]);} //如果有,就DFS/ a$ L# h! \; h- H1 J
}& N: Y% u6 M7 |1 A) G
}
+ @. s8 _2 r' k3 v' C. Nint main()
. |9 J5 v# R4 L9 c/ y0 s$ m{% R @0 |3 T Y: ]9 k3 K
int m , s , t , num , i , j , start;
7 W9 [4 C# B; g+ ^& f' Y+ i! `- U //input# X9 ? w! C+ x! _ w5 X8 X4 {
scanf("%d %d" , &n , &m); //n顶点数 m边数: p/ e$ g% Y$ y; g' C; [$ k7 q* E
memset(a , 0 , sizeof(a));
: `- z" d5 v8 ?" M# z4 n for (i = 0; i < m; i ++)
z9 Q, E" s2 P1 ^- b# b{printf("innput s,t");9 u [) ~- Q/ z* `; ~
scanf("%d %d" , &s , &t);; v9 B% V% t, h% z# b' ^
a[s][t] = 1; a[t][s] = 1;' F" Q0 A5 ~6 N# M) [
}
4 l9 d, ^, T0 u. ?5 T, Z0 K //判断是否存在欧拉回路
% n( B$ ^4 Q% w' T& o" N! rs = 0; start = 1;( }" u8 C/ J) ~! A
for (i = 1; i <= n; i ++)1 Q7 g# b# I# ^# k$ I l6 J5 o
{num = 0;
$ u h0 `) u% K( D/ J# w3 x* H9 y& Zfor (j = 1; j <= n; j ++)4 p# U: N% D! E6 A2 p" R2 n9 {
num += a[i][j];
& z4 b7 W2 Z/ v: _3 x if (num % 2 == 1) & B1 y4 m$ i/ Y" m3 `
{start = i; s ++;}0 p9 O- V `7 n" l
}
! S* [7 ?" k ?( X( F+ x% v9 Vif ((s == 0) || (s == 2))
% p2 i' ~; \* g1 cEuler(start);
1 @$ Y" I. A; Z, A$ o ] else printf("No Euler path\n");
' a+ `( n' V! x& p( ogetchar(); getchar();
7 [3 A+ C" [( l; P2 k9 O ireturn 0; } |
|