数学建模社区-数学中国
标题:
求助关于求图割点的代码，哪里错了？怎么改正啊？
[打印本页]
作者:
ganquanlife
时间:
2013-3-3 14:54
标题:
求助关于求图割点的代码，哪里错了？怎么改正啊？
function [nc] = ncutf(g)
, F: V# u; {9 y( Q- j$ `) {6 C6 u* V6 |
%求割点的算法 g为邻接矩阵 nc为割点的集合
% T- N! Q$ }6 q; a- h
n=size(g,1);
: M& v$ C2 Y! x4 E+ W! z+ t! O
if n>=3
+ R0 t* G! t+ _0 U9 `" b7 _4 P
a=sum(g);
% {, r1 u; V* M* g2 i' E2 j
b=sum(a==2);
4 x% c+ c! X5 v& ]/ e) r1 A& r
if b==n
" w, E) X; }+ A
fprintf('本图为圈，无割点。n')
5 \/ z$ y* b; p% w, W
nc=0;
$ p7 f0 w1 ?& i$ ~" e& q& K" s
end
+ q6 I; a j8 a( _# x1 o6 `% Q6 Q
else
, k# I! k! P9 n2 m& T9 x/ H
[w,k]=dfs3(g);
1 c6 c4 r( r+ k% f0 E7 {
%nc=[];
0 e, j( s8 h+ e3 k0 N5 d
nc=isncf(w,k);
; `9 x8 k- F+ b) l3 I, L7 B
n=size(g,1);
+ p+ C5 {% B, F$ D* C+ J
for i=1:n
# @# P R* E( K: E2 {% x
for j=1:n
g' }/ t2 n/ e
if w(i,j)>1
- }2 U; }. j; C& X
if k(i)>k(j)
" T+ C# P9 _- `7 f
g(i,j)=2;
; E5 p, ~; E" E9 Q. @
else
/ b2 ?, ]/ [% i) {
g(i,j)=3;
% \$ a: {; T, A/ k
end
) O2 Z3 V( M' g3 `0 s4 E* s
end
' o: ]0 j$ A( r3 g1 P4 \
end
j$ V8 O: @% e: R5 \4 a
end
Y5 n2 ~% }! e, P. H4 a
- k: ?5 w* b: e8 n+ g
for i=1:n
5 u, Q. c( m' @ [/ O. g0 x2 D
f1=find(g(i,
==2);
0 k: E% r( d! L+ i, F" Y. V& u
f2=find(g(i,
==3);
9 C- F' U4 B) ?2 l) A/ j" G2 V$ L
f=union(f1,f2);
- z% D( Z3 w9 Z( [
l(i)=min([k(f) k(i)]);
2 w+ O& b) r0 F7 [9 A: K9 G
end
4 U0 c r3 h# A+ `
* {5 q+ Y& d: f
for i=1:n
6 g9 N M/ C1 \6 }4 Y
for j=1:n
: O* I& H! _3 b3 ~8 J" r9 C
if g(i,j)==3 & k(i)>1&l(j)>=k(i)
; h+ G& U$ o0 G+ g+ j
nc=union(i,nc);
2 r4 m# S! r( S; G4 ^! a; n
end
; `8 U$ r- C( _) a% F8 h
end
t4 W' ]( n( B+ O3 R" J
end
: ]/ ^% V! ^3 y7 {" N& a5 {4 b
end
! E, n1 g1 m2 [% H
end
; R m* o: g. b. t; {5 d: a% m
3 M/ g6 u$ o( W2 j+ f* x2 m# e3 G
' o" l. O, z) x; n. {8 h! q
function nc=isncf(w,k)
7 x' u$ I. Y6 W( Q- [, I
nc=[];
/ |9 C" x, f3 R- q1 i5 \( R
t=zeros(size(w));
, H1 G& E8 ^; x2 B
n=size(w,1);
: z" [6 m- t, r+ [+ O' l8 r0 W
a=find(w~=0);
3 D0 O4 ]+ g; | j9 T
for i=1:length(a)
! ~6 A' I8 V, r# r; r$ q: Y Z
d(i)=w(a(i));
+ @# P4 h+ X3 d: D N" U
if a(i)/n>floor(a(i)/n)
1 h3 }- n- [2 H/ j) {- `4 F
t(i)=floor(a(i)/n)+1;
$ ^. h. S' Y" C' X" B5 R8 g; ]
else
/ L- w+ _7 j3 J
t(i)=floor(a(i)/n);
% C: _2 G( e2 s: {
end
3 M/ Q5 L/ \9 m4 k4 Q
t1(i)=mod(a(i),n);
6 p6 y6 H$ e Q1 ` [
if t1(i)==0
! p8 g0 e& y; R1 B! g4 X
t1(i)=n;
5 S- a. x" q; R' r
end
4 \( @* G4 J+ D% \% G* c$ O
end
# `: n0 z* p% U0 X6 b0 u6 O
[b,c]=sort(d);
( F5 ]3 T/ T' k- [6 X" v: i) }
p=[1];pc=0;
) X8 D) z6 q3 H7 J
for i=1:length(a)
7 ]9 V! a3 `' w! j8 o5 J/ X; c
if k(t1(c(i)))<k(t(c(i)))
! y) `5 R+ h( u8 k4 b
p=union(p,t(c(i)));
/ X; P4 Y( A4 C5 w; r8 F
t(t1(c(i)),t(c(i)))=3;
& z& T% t# n( u2 c5 [' O6 T4 O Z
end
1 h7 ?5 U, H: J* G7 S1 \" q
if pc==0
: \# v- u' F& b- D
tc=isempty(setdiff([1:n],p));
" h/ ]+ m8 T! \, `2 P0 N- k
if tc
$ t. P; e$ X; q
t0=sum(t(1,
==3);
& ~ l* E' a9 r/ ?" h7 A( A
if t0>=2
/ F8 ` Q3 x/ C4 s" J
nc=union(nc,1);
* d; `* A$ T8 y' d0 b- O
end
* H% ^) Y6 ~" ^6 H
break;
* I2 \6 T3 ?' n0 C k* Q5 \* G' S' c
end
/ _2 A1 j: f' T2 ?* n- k, l) X. \- ^
end
1 u0 b6 }5 ]: |0 V8 Z! b1 p
end
" u7 r/ P9 ~# q: n# h- v. s
$ K/ u" l2 P9 }8 K& u* I# n4 ]
/ Q$ z( }# H3 M0 m! W' b
end
作者:
ganquanlife
时间:
2013-3-3 15:03
如果没法改正，另外编一个求割点的代码也行阿
欢迎光临 数学建模社区-数学中国 (http://www.madio.net/)
Powered by Discuz! X2.5
==2);==3);9 C- F' U4 B) ?2 l) A/ j" G2 V$ L==3);