From: harada@nttica.ntt.jp (Ikuo   Harada)
Newsgroups: fj.sci.math
Subject: Re: Graph
Date: 31 Jul 92 05:08:36 GMT
Distribution: fj
Organization: NTT LSI Laboratories, Kanagawa, Japan.
In-reply-to: ohkita@meis.sony.co.jp's message of 27 Jul 92 22:48:53 GMT

$@86ED!w#L#S#I8&!%#N#T#T$G$9(J$@!#(J

In article <OHKITA.92Jul28074853@iota.meis.sony.co.jp> ohkita@meis.sony.co.jp (Tsuyoshi Okita) writes:

 >$@L58~%0%i%U!J$3$3$G$NDj5A!'%N!<%I$H%"!<%/$+$i$J$j!"%N!<%I$H%"!<%/$N$_$,(J
 >$@@\B3$7!"%"!<%/$KJ}8~(J$@$O$J$$$b$N!K$G%"!<%/$,#39`0J>e$N4X78!J#39`4X78!"#5(J
 >$@9`4X78$J$I!K$r$b$D>l9g$K$3$l$rI=8=$9$kJ}K!$H$7$F(J
 >	  $@!&#39`0J>e$N4X78$r#29`4X78$K%j%@%/%7%g%s$7$F9TNs$GI=$9J}K!(J
 >$@$H$$$&$N$,$H$j$"$($:$"$j$^$9!#(J

  $@$A$g$C$H[#Kf2a$.$F$h$/$o$+$j$^$;$s$,!"!V(J{a,b,c,d}$@$N(J4$@9`4X78$r!"(J{a,b},
{b,c}, {c,d}, {a,c}, {b,d}$@$N$h$&(J$@$K$J%/%j!<%/$KJQ49$9$k!#!W$H$$$&Iw$K2r<a(J
$@$7$F$*$-$^$7$g$&!#9TNs$b!"NY@\9TNs$r;H$&$H;W$$$^$7$g$&!#C"$7(J$@!"%"!<%/$OB?(J
$@=E;^$K$7$F!"(JA[i,j]$@MWAG$KK\?t$rF~$l$F$*$+$J$$$H!":o=|$N;~:$$j$^$9!#(J

 >
 >$@L\E*$O$3$N%G!<%?(J$@9=B$$r;H$C$F!"C5:w!"A^F~!":o=|!"%3%T!<$J$I$r$7$?$$$H;W$C(J
 >$@$F$$$^$9!#(J

  $@C5:w$H8@$C$F$b?'!9$"$j$^$9!#(J$@C5:w$NL\E*$O2?$G$9$+!)C5:w$N%"%k%4%j%:%`$,(J
$@$-$^$l$P!"<+A3$K7h$^$k$G$7$g$&!#(JDFS(Depth First Search)$@$J$i(J$@!"(J

procedure DFS(s)
begin
  /* $@$3$3$K%W%j%*!<%@$N=hM}$,F~$k(J */
  for i = 1, n do /* n$@$O8=:_$N%N!<%I?t(J */
    if(A[s,i] <> 0 and node i has not been visited yet)then begin
      DFS(i) ;
      /* $@$3$3$K%$(J$@%s%*!<%@$N=hM}$,F~$k(J */
    end
  /* $@$3$3$K%]%9%H%*!<%@$N=hM}$,F~$k(J */
end ;

$@$_$?$$$J46$8!#%0%i%U$,O"(J$@7k$G$J$$>l9g$b9M$($F!">/$79)IW$,$$$k$+$bCN$l$^$;(J
$@$s$1$I!#(J

 >$@2?$+NI$$J}K!$rCN$C$F$$$i$C$7$c$kJ}$,$*$i(J$@$l$?$i65$($F$/$@$5$$!#$*4j$$$7(J
 >$@$^$9!#(J

  $@NI$$J}K!$C$F!"$"$k$N$G$7$g$&$+!#Dj5A$K$7$?$,$C$F!"C1=c$JJ}(J$@K!$O!"0J2<$N(J
$@DL$j$K$J$j$^$9$M!#(J

  $@A^F~$O!"%N!<%I(Jand/or$@%"!<%/$N$G$9$M!#NY@\9TNs$NDj5A$+$i<+L@$N$h$&$J(J$@5$$,(J
$@$7$^$9!#2C$($?$$%O%$%Q!<%"!<%/Cf$NA4$F$ND:E@$NAH9g$;$K$D$$$F!"%"!<%/$NA^(J
$@F~$r$9$k$3$H$K$J$k$G$7$g(J$@$&!#%"!<%/(J{i,j}$@$NA^F~$O!"(JA[i,j]++$@!#%N!<%I$NA^F~$O9T!"(J
$@Ns$r0l$DA}$d$9I,MW$,$"$j$^$9!#%"!<%/$N:o=|$O!"(JA[i,j]--$@!#%N!<%I$N:o=|$O!"(J
$@$=$N%N!<%I$K@\B3$9$kA4%"!<%/$r:o=|$7$?8e!"9TNs$r5M$a$k!#(J

  $@%3%T!<$O$I$&$$$&(J$@A`:n$+NI$/$o$+$i$J$$!#%5%V%0%i%U$rA*$s$G!"?7$7$$%3%s%]!<(J
$@%M%s%H$H$7$FDI2C$9$k$N$+$J!#$=$l$J$i!"%5%V%0(J$@%i%U$NNY@\9TNs(JB$@$r:n$C$F!"85!9$N(J
A$@$N:G8e(J($@A0$G$bNI$$$1$I(J)$@$KIU$1$k$3$H$K$J$kLu$G$9$M!#(J

   $@(.(,(,(,(,(,(,(J$@(,(,(,(,(,(,(/(J
   $@(-(#(!(!(!(!(!(!($!!!!!!!!(-(J
   $@(-("!!!!!!!!!!!!("!!!!!!!!(-(J
   $@(-("!!!!!!!!!!!!("!!(J$@!!!!!!(-(J
   $@(-("85$N#A$N9TNs("!!#0!!!!(-(J
   $@(-("!!!!!!!!!!!!("!!!!!!!!(-(J
   $@(-("!!!!!!!!!!!!("!!!!!!!!(J$@(-(J
   $@(-(&(!(!(!(!(!(!(%!!!!!!(J  $@(-(J
   $@(-(J               $@(#(!(!($(J $@(-(J
   $@(-(J     $@#0(J        $@("#B!!("(J $@(-(J
   $@(-(J   	    $@("!!!!("(J $@(-(J
   $@(-(J               $@(&(!(!(%(J $@(-(J
   $@(1(,(,(,(,(,(,(,(,(,(,(,(,(0(J

  $@$_$?$$$K$9$k(J$@$3$H$K$J$j$^$9$M!#9TNs$r5M$a$?$jL@$1$?$j$9$k$N$,LLE]$J$N$G$9(J
$@$+!)(J

  $@$3$N$h$&$K!"%N!<%I$N=PF~$j$,B?$$(J$@>l9g$O!"9TNs$N49$o$j$K@~7A%j%9%H$r;H$&(J($@NY(J
$@@\%j%9%H$H8F$S$^$9(J)$@J}$,07$$0W$$$H;W$$$^$9!#%"!<%/$NA^F~$,!"(J$@@\B3Aj<j$r(Jcons$@$9(J
$@$k46$8$K$J$j$^$9!#(J

  $@%"!<%/$K@\B3$9$k%N!<%I$,#28D$K8B$i$J$$$N$O%O%$%Q!<%0%i%U$H8F$V(J$@$h$&$G$9(J
$@$,!"$3$l$r!"%"!<%/$N=89g$b?7$?$K%N!<%I$H$7$F!"85$N%"!<%/$H%N!<%I$N@\B34X(J
$@78$r?7$7$$%N!<%I4V$N(J$@NY@\4X78(J($@%"!<%/(J)$@$H;W$&$H!"(JBipartite$@%0%i%U$H$_$J$9$3$H$b(J
$@=PMh$^$9!#(J

  $@%"!<%/$r9T!"%N!<%I$rNs$KBP1~$5$;(J$@$l$P@\B39TNs$G$9(J($@9T$HNs$OIaDL5U$+$b(J)$@!#(J
$@0l$D$N9T$K#28D0J>e$NHsNm$r5v$;$P!"%O%$%Q!<%0%i%U$r$=$N$^$^I=$;(J$@$^$9$M!#(J

  $@Ev$jA0$N0lHLO@$K$J$j$^$9$,!"L\E*(J($@<B9T$7$?$$%"%k%4%j%:%`(J)$@$K1~$8$F9)IW$7(J
$@$J$$$H2?$,NI$$$+$O(J$@H=CG=PMh$J$$$G$7$g$&!#(J
--
NTT LSI Laboratories		     |	NTT LSI$@8&5f=j(J $@@_7W%7%9%F%`8&5fIt(J
LSI Design System Laboratory	     |	
harada@nttica.ntt.jp		     |	$@86ED0i@8(J
Xref: sparky fj.sci.math:464 fj.ai:618