様式９ +-------------------------------------+----------------+----------------------+ | ｼｽﾃﾑ名(ｺｰﾄﾞ): ＡＬＧＯＰＡＫ | | システム報告書概要 | +-------------------------------------+ +----------------------+ | ﾓｼﾞｭｰﾙ名(ｺｰﾄﾞ): BICOMPO(A307) | ﾗｲﾌﾞﾗﾘ-登録番号: | +-------------------------------------+---------------------------------------+ | 作成者･学生番号: 増沢善子21SS1159 | 文書作成者･学生番号: 増沢善子21SS1159 | +-------------------------------------+---------------------------------------+ | 作成期間: 62/01/ ー / / | 文書作成期間: 62/02/ ー / / | +-------------------------------------+---------------------------------------+ | 親モジュール: ALGOS | 子モジュール: | +-------------------------------------+---------------------------------------+ | 講義名・課題名: 卒業研究 | 参考文献(著者名、書名、出版社、発行年)| +-------------------------------------+ | | 開発形態: 移植 | SARA BAASE 'COMPUTER ALGORITHMS' | +-------------------------------------+ | | 形式: サブルーチン | ADDISON WESLEY 1978 | +-------------------------------------+---------------------------------------+ | 利用対象者: 一般 | 格納ﾒﾃﾞｨｱ形式: フロッピーディスク | +-------------------------------------+---------------------------------------+ | 目的（問題解説、機能解説−制限事項）| 格納ﾒﾃﾞｨｱ番号、ﾌｧｲﾙ名: BICOMPO.SRC | | +---------------------------------------+ | | 記述言語・走行ＯＳ: TURBO PASCAL | | 連結な無向グラフにおいて、二重連 +---------------------------------------+ | | 走行条件（ハードウェア、ソフトウェア）| | 結成分を発見するサブルーチンプロ | PC-9801 | | | | | グラム。 | MS-DOS | +-------------------------------------+---------------------------------------+ | キーワード（適用分野、手法など） ： | 分類コード（ＣＲコードを使用） ： | | BICONNECTED COMPONENTS OF A GRAPH | | +-------------------------------------+---------------------------------------+ | 呼び出し法: BICOMPO(N:INTEGER; VAR E:MAT; VAR CLIST:LIST; VAR CFDGE:EDGE) | | | +-----------------------------------------------------------------------------+ | 操作手順(ｺﾝﾌﾟﾘｰﾄﾌﾟﾛｸﾞﾗﾑ(ﾒｲﾝﾌﾟﾛｸﾞﾗﾑ)の場合:1.システム起動手順､2.データ入出力 | | 手順と形式､3.終了手順) | | (ｻﾌﾞﾙｰﾁﾝの場合:1.呼び出し形式-引き数の並べ方-､2.親ルーチン､3.子ルー | | チン､4.その他) | | 1. CONST NN=50 | | | | TYPE MAT =ARRAY[1..NN,1..NN] OF INTEGER | | | | LIST=ARRAY[1..NN] OF INTEGER | | | | EDGE=ARRAY[1..2,1..NN] OF INTEGER | | | | BICOMPO(N:INTEGER; VAR E:MAT; VAR CLIST:LIST; VAR CEDGE:EDGE) | | | | N : （入力） 頂点の個数 (1<=N<=NN) | | | | E : （入力） 辺の行列 (0,1) | | | | CLIST : （出力） 出力結果の区分 | | | | CEDGE : （出力） 出力結果の辺の集合 | | | | | | | | | | | | | | | | | | | +-----------------------------------------------------------------------------+ 注. システム１つにつき１枚作成 必要な場合モジュール１つにつき１枚作成(ｲﾝﾀｰﾌｪｰｽ仕様書-様式１-に追加) 様式７ +-------------------------------------+----------------+----------------------+ | システム名: ＡＬＧＯＰＡＫ | | 問題解説 | +-------------------------------------+ +----------------------+ | モジュール名: BICOMPO | ﾗｲﾌﾞﾗﾘ-登録番号: | +-------------------------------------+---------------------------------------+ | 作成者: 星野圭子 | 文書作成者: 星野圭子 | +-------------------------------------+---------------------------------------+ | 作成期間: 60/07/ ー 60/08/ | 文書作成期間: 60/09/ ー 60/10/ | +-------------------------------------+---------------------------------------+ | | | 連結な無向ブラフにおいて、二重連結成分を発見することが、この問題の | | 目的である。 | | 二重連結成分を発見するには、グラフの関節点を見つけることによってで | | きる。 | | | | 連結な無向グラフ Ｇ＝（Ｖ，Ｅ）において 頂点 a が関節点であるとは、 | | 次のような ふたつの頂点 v,w がとれることである。 | | すなわち | | v <> w <> a かつ v と w の間の道は 必ず a を通る。 | | | | | | ＜ 定義 ＞ | | 関節点 a ==> グラフＧから a を取り除くことによって、 | | Ｇが ふたつ以上に分かれてしまう点。 | | | | | | グラフＧにおいて 相異なる任意の３頂点 v,w,a に対して、a を通らない | | vw 間の道がとれるとき、Ｇは 二重連結(BICONNECTED) であるという。 | | | | 連結な無向グラフにおいては、二重連結であるということと、関節点が | | ないということは 同値である。 | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | +-----------------------------------------------------------------------------+ 様式６ +-------------------------------------+----------------+----------------------+ | システム名: ＡＬＧＯＰＡＫ | | アルゴリズム流れ図 | +-------------------------------------+ +----------------------+ | モジュール名: BICOMPO-1 | ﾗｲﾌﾞﾗﾘ-登録番号: | +-------------------------------------+---------------------------------------+ | 作成者: 星野圭子 | 文書作成者: 星野圭子 | +-------------------------------------+---------------------------------------+ | 作成期間: 60/07/ ー 60/08/ | 文書作成期間: 60/09/ ー 60/12/ | +-------------------------------------+---------------------------------------+ | | | ++-------++ +-----+ +-------+ +---------+ | | !!MODULE !! + CONST + + NN + ! 50 ! | | !! !!--+ +--! !--! ! | | !!BICOMP !! ! + + ! + + ! ! | | ++-------++ ! +-----+ ! +-------+ +---------+ | | ! ! +-------+ +---------+ | | ! ! + STACKMAX+ ! 100 ! | | ! !-! !--! ! | | ! + + ! ! | | ! +-------+ +---------+ | | ! +-----+ ++-------++ +--------++ +---------+ | | ! + TYPE + !! STACK !! !ARRAY !! !INTEGER ! | | !-+ +--!! !!--![0..STAC!!--! ! | | ! + + ! !! !! ! KMAX] !! ! ! | | ! +-----+ ! ++-------++ +--------++ +---------+ | | ! ! ++-------++ +--------++ +---------+ | | ! ! !! MAT !! !ARRAY !! !INTEGER ! | | ! !-!! !!--![1..NN, !!--! ! | | ! ! !! !! ! 1..NN] !! ! ! | | ! ! ++-------++ +--------++ +---------+ | | ! ! ++-------++ +--------++ +---------+ | | ! ! !! LIST !! !ARRAY !! !INTEGER ! | | ! !-!! !!--![1..NN] !!--! ! | | ! ! !! !! ! !! ! ! | | ! ! ++-------++ +--------++ +---------+ | | ! ! ++-------++ +--------++ +---------+ | | ! ! !! EDGE !! !ARRAY !! !INTEGER ! | | ! !-!! !!--![1..NN, !!--! ! | | ! !! !! ! 1..2] !! ! ! | | ! ++-------++ +--------++ +---------+ | | ! ++-------++ +-----+ | | ! !!PROCEDU!! !BI-1 ! | | !--!!RE !!--+-----+ | | !!BICOMPO!! +-----+ | | ++-------++ | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | +-----------------------------------------------------------------------------+ 様式６ +-------------------------------------+----------------+----------------------+ | システム名: ＡＬＧＯＰＡＫ | | アルゴリズム流れ図 | +-------------------------------------+ +----------------------+ | モジュール名: BICOMPO-2 | ﾗｲﾌﾞﾗﾘ-登録番号: | +-------------------------------------+---------------------------------------+ | 作成者: 星野圭子 | 文書作成者: 星野圭子 | +-------------------------------------+---------------------------------------+ | 作成期間: 60/07/ ー 60/08/ | 文書作成期間: 60/09/ ー 60/12/ | +-------------------------------------+---------------------------------------+ | | | +-----+ +----+ +-------+ +---------+ | | !BI-1 ! +PARAMA+ + N + !INTEGER ! | | +-----+---+--+ TER +--! !--! ! | | +-----+ ! + + ! + + ! ! | | ! +----+ ! +-------+ +---------+ | | ! ! +-------+ ++-------++ | | ! ! + VAR + !! MAT !! | | ! !-! E !--!! !! | | ! ! + ! !! !! | | ! ! +-------+ ++-------++ | | ! ! +-------+ ++-------++ | | ! ! + VAR + !! LIST !! | | ! !-! CLIST !--!! !! | | ! ! + + !! !! | | ! ! +-------+ ++-------++ | | ! ! +-------+ ++-------++ | | ! ! + VAR + !! EDGE !! | | ! !-! CEDGE !--!! !! | | ! + + !! !! | | ! +-------+ ++-------++ | | ! +----+ +-----+ | | ! + VAR + !BI-2 ! | | !--+ +---+-----+ | | ! + + +-----+ | | ! +----+ | | ! ++-------++ +-----+ | | ! !!FUNCTIO!! !BI-3 ! | | !--!!N !!--+-----+ | | ! !! MIN !! +-----+ | | ! ++-------++ | | ! ++-------++ +-----+ | | ! !!FUNCYIO!! !BI-4 ! | | !--!!N !!--+-----+ | | ! !! BOO !! +-----+ | | ! ++-------++ | | ! ++-------++ +-----+ | | ! !!FUNCTIO!! !BI-5 ! | | !--!!N !!--+-----+ | | ! !! TOP !! +-----+ | | ! ++-------++ | | ! | | ! | | ! | | +--+--+ | | !BI-6 ! | | +-----+ | | +-----+ | | | | | | | | | | | | | +-----------------------------------------------------------------------------+ 様式６ +-------------------------------------+----------------+----------------------+ | システム名: ＡＬＧＯＰＡＫ | | アルゴリズム流れ図 | +-------------------------------------+ +----------------------+ | モジュール名: BICOMPO-3 | ﾗｲﾌﾞﾗﾘ-登録番号: | +-------------------------------------+---------------------------------------+ | 作成者: 星野圭子 | 文書作成者: 星野圭子 | +-------------------------------------+---------------------------------------+ | 作成期間: 60/07/ ー 60/08/ | 文書作成期間: 60/09/ ー 60/12/ | +-------------------------------------+---------------------------------------+ | | | | | +-----+ +--------+ ++-------++ | | !BI-2 ! + EE + !! MAT !! | | +-----+--+--! !--!! !! | | +-----+ ! + + !! !! | | ! +--------+ ++-------++ | | ! +--------+ ++-------++ | | ! + SV; + !! STACK !! | | !--! SE1; !--!! !! | | ! + SE2 + !! !! | | ! +--------+ ++-------++ | | ! +--------+ +--------++ +---------+ | | ! + NUMBER; + ! ARRAY !! !INTEGER ! | | !--! !--! [1..NN]!!--! ! | | ! + BACK + ! !! ! ! | | ! +--------+ +--------++ +---------+ | | ! +--------+ +---------+ | | ! + NUM + !INTEGER ! | | !--! !--! ! | | ! + + ! ! | | ! +--------+ +---------+ | | ! +--------+ +---------+ | | ! + I ; J ; + !INTEGER ! | | !--! K ; C ; !--! ! | | ! + D ; B + ! ! | | ! +--------+ +---------+ | | ! +--------+ +---------+ | | ! + SW ; + !BOOLEAN ! | | !--! !--! ! | | + FLAG + ! ! | | +--------+ +---------+ | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | +-----------------------------------------------------------------------------+ 様式６ +-------------------------------------+----------------+----------------------+ | システム名: ＡＬＧＯＰＡＫ | | アルゴリズム流れ図 | +-------------------------------------+ +----------------------+ | モジュール名: BICOMPO-4 | ﾗｲﾌﾞﾗﾘ-登録番号: | +-------------------------------------+---------------------------------------+ | 作成者: 星野圭子 | 文書作成者: 星野圭子 | +-------------------------------------+---------------------------------------+ | 作成期間: 60/07/ ー 60/08/ | 文書作成期間: 60/09/ ー 60/12/ | +-------------------------------------+---------------------------------------+ | | | | | | | +-----+ +---------+ | | !BI-3 ! !INTEGER ! | | +-----+--+--! ! | | +-----+ ! ! ! | | ! +---------+ | | ! +-----+ +-------+ +---------+ | | ! +PARAMAT+ + + !INTEGER ! | | !--+ ER +-! X , Y !--! ! | | ! + + + + ! ! | | ! +-----+ +-------+ +---------+ | | ! +-------+ +---------+ | | ! !IF + ! MIN:=X ! | | !--! X<=Y +--! ! | | ! + ! ! ! | | +-------+ ! +---------+ | | ! +---------+ | | ! ! MIN:=Y ! | | !-! ! | | ! ! | | +---------+ | | | | +-----+ +---------+ | | !BI-4 ! !BOOLEAN ! | | +-----+-+--! ! | | +-----+ ! ! ! | | ! +---------+ | | ! +-----+ +--------+ | | ! +PARAMAT+ + + | | !--+ ER +---! X , Y ! | | ! + + + + | | ! +-----+ +--------+ | | ! +-------+ +----------+ | | ! !IF NUMBE+ ! BOO:= ! | | !--!R[X]>=NUM+-+-! TRUE ! | | !BER[Y] + ! ! ! | | +-------+ ! +----------+ | | ! +----------+ | | ! ! BOO:= ! | | !-! FALSE ! | | ! ! | | +----------+ | | | | | | | | | | | | | | | | | | | | | +-----------------------------------------------------------------------------+ 様式６ +-------------------------------------+----------------+----------------------+ | システム名: ＡＬＧＯＰＡＫ | | アルゴリズム流れ図 | +-------------------------------------+ +----------------------+ | モジュール名: BICOMPO-5 | ﾗｲﾌﾞﾗﾘ-登録番号: | +-------------------------------------+---------------------------------------+ | 作成者: 星野圭子 | 文書作成者: 星野圭子 | +-------------------------------------+---------------------------------------+ | 作成期間: 60/07/ ー 60/08/ | 文書作成期間: 60/09/ ー 60/12/ | +-------------------------------------+---------------------------------------+ | | | +-----+ +---------+ | | !BI-5 ! !INTEGER ! | | +-----+--+--! ! | | +-----+ ! ! ! | | ! +---------+ | | ! +-----+ +-------+ ++-------++ | | ! +PARAMAT+ + XX + !! STACK !! | | !--+ ER +-! !--!! !! | | ! + + + + !! !! | | ! +-----+ +-------+ ++-------++ | | ! +---------+ | | ! !TOP:= ! | | !--!XX[XX[0]]! | | ! ! | | +---------+ | | | | +-----+ +---------+ | | !BI-7 ! !INTEGER ! | | +-----+--+--! ! | | +-----+ ! ! ! | | ! +---------+ | | ! +-----+ +-------+ ++-------++ | | ! +PARAMAT+ + XX + !!STACK !! | | !--+ ER +--! !-!! !! | | ! + + + + !! !! | | ! +-----+ +-------+ ++-------++ | | ! +---------+ | | ! ! SEC:= ! | | !--! XX[XX[0]! | | ! -1] ! | | +---------+ | | | | +-----+ +-----+ +-------+ ++-------++ | | !BI-8 ! +PARAMAT+ + VAR + !!STACK !! | | +-----+--+--+ER +--! XX !-!! !! | | +-----+ ! + + + + !! !! | | ! +-----+ +-------+ ++-------++ | | ! +-------+ +---------+ | | ! ! IF + + WRITLN + | | !--!XX[0]=0 +----+(No more + | | ! + ! +stack...)+ | | +-------+ ! +---------+ | | ! | | ! +---------+ | | ! ! XX[0]:= ! | | !--! XX[0]-1 ! | | ! ! | | +---------+ | | | | | | | | | | | +-----------------------------------------------------------------------------+ 様式６ +-------------------------------------+----------------+----------------------+ | システム名: ＡＬＧＯＰＡＫ | | アルゴリズム流れ図 | +-------------------------------------+ +----------------------+ | モジュール名: BICOMPO-6 | ﾗｲﾌﾞﾗﾘ-登録番号: | +-------------------------------------+---------------------------------------+ | 作成者: 星野圭子 | 文書作成者: 星野圭子 | +-------------------------------------+---------------------------------------+ | 作成期間: 60/07/ ー 60/08/ | 文書作成期間: 60/09/ ー 60/12/ | +-------------------------------------+---------------------------------------+ | | | +-----+ ++-------++ +-----+ | | !BI-6 ! !!FUNCTIO!! !BI-7 ! | | +-----+--+--!!N !!----+-----+ | | +-----+ ! !! SEC !! +-----+ | | ! ++-------++ | | ! ++-------++ +-----+ | | ! !!PROCEDU!! !BI-8 ! | | !--!!RE !!----+-----+ | | ! !! POP !! +-----+ | | ! ++-------++ | | ! ++-------++ +-----+ | | ! !!PROCEDU!! !BI-9 ! | | !--!!RE !!----+-----+ | | ! !! PUSH !! +-----+ | | ! ++-------++ | | ! ++-------++ +-----+ | | ! !!FUNCTIO!! !BI-10! | | !--!!N !!----+-----+ | | ! !! EMPTY !! +-----+ | | ! ++-------++ | | ! ++-------++ +-----+ | | ! !!FUNCTIO!! !BI-11! | | !--!!N NEXT!!----+-----+ | | ! !!EDGE !! +-----+ | | ! ++-------++ | | ! +--------------------+ | | ! !SV[0]:=0;C:=0;D:=0; ! | | !--!SE1[0]:=0;SE2[0]:=0;! | | !B:=1; FLAG:=TRUE ! | | +---------+----------+ | | ! | | ! | | +----+---++ +---------+ | | !FOR !! ! CLIST[I]! | | !I:=1 TO !!--+--! :=0 ! | | !NN !! ! ! ! | | +----+---++ ! +---------+ | | ! ! +--------++ +--------+ | | ! ! !FOR !! !CEDGE[I,! | | ! !--!J:=1 TO !!---!J]:=0 ! | | ! !2 !! ! ! | | ! +--------++ +--------+ | | ! | | +--+--+ | | !BI-12! | | +-----+ | | +-----+ | | | | | | | | | | | | | +-----------------------------------------------------------------------------+ 様式６ +-------------------------------------+----------------+----------------------+ | システム名: ＡＬＧＯＰＡＫ | | アルゴリズム流れ図 | +-------------------------------------+ +----------------------+ | モジュール名: BICOMPO-7 | ﾗｲﾌﾞﾗﾘ-登録番号: | +-------------------------------------+---------------------------------------+ | 作成者: 星野圭子 | 文書作成者: 星野圭子 | +-------------------------------------+---------------------------------------+ | 作成期間: 60/07/ ー 60/08/ | 文書作成期間: 60/09/ ー 60/12/ | +-------------------------------------+---------------------------------------+ | | | | | +-----+ +-----+ +-------+ ++-------++ | | !BI-9 ! +PARAMAT+ + VAR + !! STACK !! | | +-----+--+--+ER +--+--! XX !---!! !! | | +-----+ ! + + ! + + !! !! | | ! +-----+ ! +-------+ ++-------++ | | ! ! +-------+ +---------+ | | ! ! + DATA + !INTEGER ! | | ! !--! !---! ! | | ! + + ! ! | | ! +-------+ +---------+ | | ! | | ! +-------+ +---------+ | | ! !IF + +WRITELN + | | !---!XX[0]= +-+---+(Stack Ov+ | | !STACKMAX+ ! + erflow) + | | +-------+ ! +---------+ | | ! | | ! +----------------+ | | ! !XX[0]:=XX[0]+1; ! | | !--!XX[XX[0]]:=DATA ! | | ! ! | | +----------------+ | | | | +-----+ +---------+ | | !BI-10! !BOOLEAN ! | | +-----+--+--! ! | | +-----+ ! ! ! | | ! +---------+ | | ! +-----+ +-------+ ++-------++ | | ! +PARAMAT+ + XX + !! STACK !! | | !--+ER +-----! !--!! !! | | ! + + + + !! !! | | ! +-----+ +-------+ ++-------++ | | ! +-------+ +---------+ | | ! !IF + !EMPTY:= ! | | !--! XX[0]=0 +--+--! TRUE ! | | ! + ! ! ! | | +-------+ ! +---------+ | | ! +---------+ | | ! !EMPTY:= ! | | !--! FALSE ! | | ! ! | | +---------+ | | | | | | | | | | | | | | | | | | | +-----------------------------------------------------------------------------+ 様式６ +-------------------------------------+----------------+----------------------+ | システム名: ＡＬＧＯＰＡＫ | | アルゴリズム流れ図 | +-------------------------------------+ +----------------------+ | モジュール名: BICOMPO-8 | ﾗｲﾌﾞﾗﾘ-登録番号: | +-------------------------------------+---------------------------------------+ | 作成者: 星野圭子 | 文書作成者: 星野圭子 | +-------------------------------------+---------------------------------------+ | 作成期間: 60/07/ ー 60/08/ | 文書作成期間: 60/09/ ー 60/12/ | +-------------------------------------+---------------------------------------+ | | | +-----+ +---------+ | | !BI-11! !BOOLEAN ! | | +-----+--+--! ! | | +-----+ ! ! ! | | ! +---------+ | | ! +-----+ +-------+ +---------+ | | ! +PARAMAT+ + I + !INTEGER ! | | !--+ER +-+--! !---! ! | | ! + + ! + + ! ! | | ! +-----+ ! +-------+ +---------+ | | ! ! +-------+ +---------+ | | ! ! + VAR + !INTEGER ! | | ! !--! J !---! ! | | ! + + ! ! | | ! +-------+ +---------+ | | ! +-----+ +-------+ +---------+ | | ! + VAR + + FINED + !BOOLEAN ! | | !--+ +----! !---! ! | | ! + + + + ! ! | | ! +-----+ +-------+ +---------+ | | ! +---------+ | | ! ! J:=0 ! | | !--! ! | | ! ! | | +----+----+ | | ! | | +----+---++ +-------------------+ | | !REPEAT !! !J:=J+1; ! | | ! !!--+--!FINED:=((E[I,J]=1) ! | | ! !! ! ! and (EE[I,J]=0) ! | | +----+---!! ! +--------+----------+ | | ! ! ! | | ! ! +----+--+ +---------+ | | ! ! !UNTIL + ! EXIT ! | | ! !------!FINED or +----! ! | | ! !(J=N) + ! ! | | ! +-------+ +---------+ | | +----+--+ +---------+ | | !IF + !EE[I,J]:=! | | ! FINED +--!1 ; EE[J,! | | ! + !I]:=1 ! | | +----+--+ +---------+ | | ! | | +----+----+ | | !NEXTEDGE ! | | ! :=FINED ! | | ! ! | | +---------+ | | | | | | | | | | | +-----------------------------------------------------------------------------+ 様式６ +-------------------------------------+----------------+----------------------+ | システム名: ＡＬＧＯＰＡＫ | | アルゴリズム流れ図 | +-------------------------------------+ +----------------------+ | モジュール名: BICOMPO-9 | ﾗｲﾌﾞﾗﾘ-登録番号: | +-------------------------------------+---------------------------------------+ | 作成者: 星野圭子 | 文書作成者: 星野圭子 | +-------------------------------------+---------------------------------------+ | 作成期間: 60/07/ ー 60/08/ | 文書作成期間: 60/09/ ー 60/12/ | +-------------------------------------+---------------------------------------+ | | | | | +-----+ | | !BI-12! | | +-----+ | | +--+--+ | | ! | | +----+---++ +--------++ +---------+ | | !FOR !! !FOR !! ! EE[I,J] ! | | ! I:=1 TO!!--! J:=1 TO!!---! :=0 ! | | ! N !! ! N !! ! ! | | +----+---++ +--------++ +---------+ | | ! | | +----+----+ | | !NUMBER[1]! | | ! :=1 ; ! | | !NUM:=2 ! | | +----+----+ | | ! | | +----+----+ | | !PUSH ! | | ! (SV,1) ! | | ! ! | | +----+----+ | | ! | | +----+---++ +---------+ | | !FOR !! !NUMBER[I]! | | ! I:=2 TO!!---! :=0 ! | | ! N !! ! ! | | +----+---++ +---------+ | | ! | | +----+---++ +-----+ | | !WHILE !! !BI-13! | | ! FLAG !!---+-----+ | | ! !! +-----+ | | +--------++ | | | | | | | | +-----+ +------------------------+ +-----------------------+ | | !BI-14! !IF BOO(NUMBER[TOP(SE1)],+ !C:=C+1; ! | | +-----+---!NUMBER[K])and BOO(NUMBER +---!CEDGE[C,1]:=TOP(SE1); ! | | +-----+ ![TOP(SE2)],NUMBER[K]) + !CEDGE[C,2]:=TOP(SE2); ! | | +------------------------+ !B:=C+1; ! | | !POP(SE1) ;POP(SE2); ! | | !SW:=NOT(EMPTY(SE1)) ! | | +-----------------------+ | | | | | | | | | | | | | | | +-----------------------------------------------------------------------------+ 様式６ +-------------------------------------+----------------+----------------------+ | システム名: ＡＬＧＯＰＡＫ | | アルゴリズム流れ図 | +-------------------------------------+ +----------------------+ | モジュール名: BICOMPO-10 | ﾗｲﾌﾞﾗﾘ-登録番号: | +-------------------------------------+---------------------------------------+ | 作成者: 星野圭子 | 文書作成者: 星野圭子 | +-------------------------------------+---------------------------------------+ | 作成期間: 60/07/ ー 60/08/ | 文書作成期間: 60/09/ ー 60/12/ | +-------------------------------------+---------------------------------------+ | | | +-----+ +--------++ +---------+ | | !BI-13! !WHILE !! !PUSH(SE1,! | | +-----+--+--!NEXTEDGE!!--+--!TOP(SV));! | | +-----+ ! !(TOP(SV)!! ! !PUSH(SE2,! | | ! !,J) !! ! !J) ! | | ! +--------++ ! +---------+ | | ! ! +-------+ +----------------------+ | | ! ! !IF + !BACK[TOP(SV)]:= ! | | ! !--!NUMBER[J]+--+--!MIN(BACK[TOP(SV)], ! | | ! ! >0 + ! !NUMBER[J] ! | | ! +-------+ ! +----------------------+ | | ! ! +----------------------+ | | ! ! !NUMBER[J]:=NUM; ! | | ! !--!BACK[J]:=NUMBER[J]; ! | | ! !NUM:=NUM+1;PUSH(SV,J) ! | | ! +----------------------+ | | ! +-------+ +---------+ | | ! !IF + ! K:= ! | | !--! SV[0]>1 +--+--! SEC(SV)! | | ! + ! ! ! | | +-------+ ! +----+----+ | | ! ! | | ! +----+--+ +--------------+ | | ! !IF + !D:=D+1; ! | | ! !BACK[TOP(+--+--!CLIST[D]:=B; ! | | ! !SV)]>=NU+ ! !SW:=NOT(EMPTY ! | | ! !MBER[K]+ ! !(SE1)) ! | | ! +----+-+ ! +------+-------+ | | ! ! ! ! | | ! ! ! +----+---++ +-----+ | | ! ! ! !WHILE !! !BI-14! | | ! ! ! ! SW !!--+-----+ | | ! ! ! ! !! +-----+ | | ! ! ! +--------++ | | ! ! ! +------------+ | | ! ! ! !BACK[K]:= ! | | ! ! !----!MIN(BACK[K],! | | ! ! !BACK[TOP(SV)! | | ! ! +------------+ | | ! +----+----+ | | ! !POP(SV) ! | | ! ! ! | | ! ! ! | | ! +---------+ | | ! +------------+ | | ! !FLAG:=FALSE;! | | !--!CLIST[D+1]:=! | | !B; ! | | +------------+ | | | | | | | | | +-----------------------------------------------------------------------------+ 様式９ +-------------------------------------+----------------+----------------------+ | ｼｽﾃﾑ名(ｺｰﾄﾞ): ＡＬＧＯＰＡＫ | | システム報告書概要 | +-------------------------------------+ +----------------------+ | ﾓｼﾞｭｰﾙ名(ｺｰﾄﾞ): CBICOMPO(P307) | ﾗｲﾌﾞﾗﾘ-登録番号: | +-------------------------------------+---------------------------------------+ | 作成者･学生番号: 増沢善子21SS1159 | 文書作成者･学生番号: 増沢善子21SS1159 | +-------------------------------------+---------------------------------------+ | 作成期間: 62/01/ ー / / | 文書作成期間: 62/02/ ー / / | +-------------------------------------+---------------------------------------+ | 親モジュール: ALGOS | 子モジュール: BICOMPO | +-------------------------------------+---------------------------------------+ | 講義名・課題名: 卒業研究 | 参考文献(著者名、書名、出版社、発行年)| +-------------------------------------+ | | 開発形態: 移植 | SARA BAASE 'COMPUTER ALGORITHMS' | +-------------------------------------+ | | 形式: コンプリート | ADDISON WESLEY 1978 | +-------------------------------------+---------------------------------------+ | 利用対象者: 一般 | 格納ﾒﾃﾞｨｱ形式: フロッピーディスク | +-------------------------------------+---------------------------------------+ | 目的（問題解説、機能解説−制限事項）| 格納ﾒﾃﾞｨｱ番号、ﾌｧｲﾙ名: CBICOMPO.SRC | | +---------------------------------------+ | | 記述言語・走行ＯＳ: TURBO PASCAL | | 連結な無向グラフにおいて、 +---------------------------------------+ | | 走行条件（ハードウェア、ソフトウェア）| | BICOMPONENTを 発見するサブルーチ | PC-9801 | | | | | ン。 | MS-DOS | +-------------------------------------+---------------------------------------+ | キーワード（適用分野、手法など） ： | 分類コード（ＣＲコードを使用） ： | | BICONNECTED COMPONENTS OF A GRAPH | | +-------------------------------------+---------------------------------------+ | 呼び出し法: CBICOMPO | | | +-----------------------------------------------------------------------------+ | 操作手順(ｺﾝﾌﾟﾘｰﾄﾌﾟﾛｸﾞﾗﾑ(ﾒｲﾝﾌﾟﾛｸﾞﾗﾑ)の場合:1.システム起動手順､2.データ入出力 | | 手順と形式､3.終了手順) | | (ｻﾌﾞﾙｰﾁﾝの場合:1.呼び出し形式-引き数の並べ方-､2.親ルーチン､3.子ルー | | チン､4.その他) | | 1. 入力データ形式 : ファイル | | | | N N : 頂点の個数 | | | | N*N 行列 N*N 行列 : 辺のデータ （連結=1,不連結=0） | | | | 出力データ形式 | | | | 各二重連結ごとに 辺の名前を出力する。 | | | | 2. A>B: | | | | B>CBICOMPO | | | | 注） CBICOMPOを 実行すると、テストデータファイル 'TEDGE' についての | | | | 結果が得られる。 | | | | | | | | | | | | | | | | | | | +-----------------------------------------------------------------------------+ 注. システム１つにつき１枚作成 必要な場合モジュール１つにつき１枚作成(ｲﾝﾀｰﾌｪｰｽ仕様書-様式１-に追加)