数学建模社区-数学中国
标题:
求助关于求图割点的代码,哪里错了?怎么改正啊?
[打印本页]
作者:
ganquanlife
时间:
2013-3-3 14:54
标题:
求助关于求图割点的代码,哪里错了?怎么改正啊?
function [nc] = ncutf(g)
$ j( e. K9 a- J0 E6 J" g6 o
%求割点的算法 g为邻接矩阵 nc为割点的集合
: X/ w$ V2 S) _) g; ]& b
n=size(g,1);
$ a% j: D: L7 q" Q* W$ ~
if n>=3
# N b0 P- n" B/ a' j
a=sum(g);
* h# V8 f& s8 c8 K0 k, T- Z% k4 R
b=sum(a==2);
- Z0 C t( p" z2 O
if b==n
5 a$ u2 p! I2 |. M6 y5 Z
fprintf('本图为圈,无割点。n')
+ f+ Q o$ ?) w
nc=0;
( b* S& k( E( B' C" L8 B' J m6 X
end
% _" ^+ k( [% k6 U$ z2 ^
else
) M7 g- r) j$ t; s0 G' a2 Z# F
[w,k]=dfs3(g);
7 `- n% h! M$ w* d+ ^
%nc=[];
" Q9 s4 d) Y- B1 h6 {0 e# @( l1 Z
nc=isncf(w,k);
- J' L, |7 w; m+ N
n=size(g,1);
+ T7 l D% g, C9 V
for i=1:n
; d" ? X2 m! P6 p' Q7 ]
for j=1:n
/ T$ ^0 v7 U6 P* o8 D7 U
if w(i,j)>1
$ u9 O8 f0 E. x4 T! }& ~
if k(i)>k(j)
3 k# `$ Q N; ]( s; p! J4 N& J2 d
g(i,j)=2;
3 L, r5 V0 O* k+ B
else
; Z) z+ D1 L" h
g(i,j)=3;
6 G* u# {' v/ j# Y7 S$ v$ Y
end
( R- q6 T+ F* F
end
3 o/ {# q. |9 |* D
end
2 J" |1 U3 v0 |# ]/ ^1 J8 \, B( S
end
! F3 T- T! u" m t, I$ y1 l1 M2 t* \0 S) r
; f2 k2 X5 e6 X1 Q8 r
for i=1:n
; P9 M5 @3 F7 r5 u: b$ ^
f1=find(g(i,
==2);
! r$ m/ n: Z# l/ \
f2=find(g(i,
==3);
! R# j2 o6 J2 I9 x* m0 E; J* ^; L5 G
f=union(f1,f2);
, k% r5 {0 _# \! [) O- F
l(i)=min([k(f) k(i)]);
/ V; [6 K J! _, Q8 F% g" G
end
. P+ n: X& ^5 n& ^0 s% \2 K
/ @9 k' I$ ]# o- e2 A) y$ b# P
for i=1:n
( r% s P1 ~2 ~" x& i3 T. k
for j=1:n
4 F$ e2 e5 N5 y" d: j
if g(i,j)==3 & k(i)>1&l(j)>=k(i)
) _' g6 A$ L$ y6 S) Z
nc=union(i,nc);
/ q- E$ M/ Y) N5 J
end
% l [; N) q9 @' i9 D9 G
end
2 W4 E5 c: |# |* h( I# Z
end
3 h5 u i0 d( k3 f
end
/ c: Z8 O# Q, f( x2 v! t( h$ q
end
- O7 u: L+ z2 a/ E7 K5 X* E1 k7 C
" M& n6 Z! q- i/ x5 H
/ j) {5 U `. Q+ i) z* _1 P/ R7 |
function nc=isncf(w,k)
+ b0 x. T9 V' R+ u' p% c
nc=[];
9 d# H1 a3 \: q
t=zeros(size(w));
( H) A; r8 z; f8 e9 T$ _
n=size(w,1);
1 }0 w6 N$ O, ^6 o) E
a=find(w~=0);
; L" s" M G9 G; n9 ?7 Z
for i=1:length(a)
$ {6 ^& i+ k+ F) q7 E
d(i)=w(a(i));
) k* {+ n- U% ^" T
if a(i)/n>floor(a(i)/n)
2 G1 n* X) V, E6 j. a) k: \% }$ M
t(i)=floor(a(i)/n)+1;
7 v9 ~) P7 J9 }9 ~( @, D
else
0 { u, u7 L- ~2 P% @0 n
t(i)=floor(a(i)/n);
' S* k" \$ j! [: D; C, u; Z D% u
end
& L! k4 |$ ^' D3 y: H- w6 o* d* |
t1(i)=mod(a(i),n);
( Q( t% a; A* R G
if t1(i)==0
1 R! @- a2 a$ w
t1(i)=n;
6 u5 I, S# y9 I6 J8 Z7 ?9 T
end
4 M* w" y% X9 @0 B+ E6 X8 C" c
end
# p5 |8 k. L5 K
[b,c]=sort(d);
" c2 `: s* D# s% T# ^! o8 e: O5 M
p=[1];pc=0;
5 N1 J- X" W' e; a$ b
for i=1:length(a)
6 ]* G3 f, ?- B+ Y
if k(t1(c(i)))<k(t(c(i)))
* w- h7 q" @) V
p=union(p,t(c(i)));
! i- s% f7 e8 ~: e
t(t1(c(i)),t(c(i)))=3;
1 @9 x% l. z" i# Q0 c
end
. j1 n/ u( Q& m3 g: R6 B! g3 ^
if pc==0
3 J0 h0 A) y* P7 |" U' \: N
tc=isempty(setdiff([1:n],p));
3 d5 n5 b: J4 b3 M9 V7 J% E
if tc
9 `+ ]0 `& Z, O
t0=sum(t(1,
==3);
; `/ n n( O1 \( q* x/ O/ H
if t0>=2
$ k, o* n! r2 u3 q: ^
nc=union(nc,1);
4 V" V" \8 f% _+ n8 h$ U
end
+ }: {' P" d5 o! ?3 Y
break;
5 P; g( Y: B& t! Q
end
9 s$ B; q, m! u k
end
8 Y0 c) q; k4 n/ J8 _/ l- P
end
5 H) ?6 m. J! f9 |1 }6 A, ~5 R
" f8 p: A1 Z: L; x* o. {; F+ m
( i% n1 V( Y `/ {1 ] Y* l) z
end
作者:
ganquanlife
时间:
2013-3-3 15:03
如果没法改正,另外编一个求割点的代码也行阿
欢迎光临 数学建模社区-数学中国 (http://www.madio.net/)
Powered by Discuz! X2.5