|
|
深さ優先の再帰呼び出しによるグラフ探索です。
PUBLIC NUMERIC A(20,20),DISTANCE(20),VISITED(20),INDEX(100),SIZE,INF,TRUE,FALSE,START
PUBLIC NUMERIC MININDEX(100),MINDISTANCE,MAXINDEX(100),MAXDISTANCE
PUBLIC STRING NODE$(26)
MAT READ NODE$
DATA A,B,C,D,E,F,G,H,I,J,K,L,M,N,O,P,Q,R,S,T,U,V,W,X,Y,Z
LET INF=100000000
LET MINDISTANCE=INF
LET MAXDISTANCE=-INF
LET TRUE=1
LET FALSE=0
RESTORE 10
READ SIZE
FOR I=1 TO SIZE ! 隣接行列読み込み
FOR J=1 TO SIZE
READ S$
IF S$="INF" THEN
LET A(I,J)=INF
ELSE
LET A(I,J)=VAL(S$)
END IF
NEXT J
NEXT I
LET START=8
LET GOAL=2
IF START<1 OR GOAL<1 OR START>SIZE OR GOAL>SIZE OR START=GOAL THEN
PRINT "ERROR !!"
STOP
END IF
CALL VISIT(START,GOAL)
PRINT REPEAT$("-",60)
LET K=START
DO
PRINT NODE$(K);" → ";
LET K=MININDEX(K)
LOOP UNTIL K=GOAL
PRINT NODE$(GOAL);" MIN DISTANCE";MINDISTANCE
!LET K=START
!DO
! PRINT NODE$(K);" → ";
! LET K=MAXINDEX(K)
!LOOP UNTIL K=GOAL
!PRINT NODE$(GOAL);" MAX DISTANCE";MAXDISTANCE
10 DATA 10 ! 有向グラフ
DATA INF, 1, 4,INF, 5,INF, 2,INF, 2,INF
DATA INF,INF, 3,INF,INF, 4,INF,INF,INF,INF
DATA 3,INF,INF, 2,INF,INF, 1,INF,INF, 1
DATA INF,INF, 2,INF,INF,INF,INF, 3,INF,INF
DATA INF, 2,INF,INF,INF, 2,INF,INF,INF, 1
DATA 1,INF, 4,INF, 1,INF, 5,INF,INF,INF
DATA INF, 3,INF,INF,INF, 6,INF, 5,INF,INF
DATA 1,INF,INF, 3,INF,INF,INF,INF, 5,INF
DATA INF, 2,INF, 5,INF, 2,INF, 3,INF, 2
DATA 1,INF, 4, 3,INF,INF, 5,INF,INF,INF
20 DATA 8 ! 無向グラフ(対角成分に対して対称。A(I,J)とA(J,I)が同値)
DATA INF, 1, 1,INF,INF,INF, 1, 1
DATA 1,INF, 1,INF, 1,INF,INF,INF
DATA 1, 1,INF, 1,INF, 1, 1,INF
DATA INF,INF, 1,INF, 1,INF, 1, 1
DATA INF, 1,INF, 1,INF, 1,INF,INF
DATA INF,INF, 1,INF, 1,INF, 1,INF
DATA 1,INF, 1, 1,INF, 1,INF, 1
DATA 1,INF,INF, 1,INF,INF, 1,INF
30 DATA 10 ! 有向グラフ
DATA INF, 2,INF, 1,INF, 4, 6,INF, 7,INF
DATA INF,INF,INF, -2, 1,INF,INF, 2,INF, 1
DATA -3,INF,INF,INF, 1,INF, -1,INF, 2,INF
DATA INF, 2,INF,INF,INF,INF, 1,INF,INF, 3
DATA INF,INF, -1,INF,INF, 2,INF, 3, 4,INF
DATA 4,INF,INF,INF, 2,INF,INF, 1,INF, 5
DATA INF, 1,INF, 2,INF, 1,INF, 5,INF,INF
DATA 2,INF,INF, 4,INF, 3,INF,INF, 2, 4
DATA INF,INF, 4,INF, 4,INF, -2,INF,INF,INF
DATA 1,INF, 3,INF, 6,INF, 1,INF,INF,INF
END
EXTERNAL SUB VISIT(I,GOAL)
IF I=GOAL THEN
LET K=START
DO
PRINT NODE$(K);" → ";
LET K=INDEX(K)
LOOP UNTIL K=GOAL
PRINT NODE$(GOAL);" DISTANCE";DISTANCE(GOAL)
IF MINDISTANCE>DISTANCE(GOAL) THEN
MAT MININDEX=INDEX
LET MINDISTANCE=DISTANCE(GOAL)
END IF
! IF MAXDISTANCE<DISTANCE(GOAL) THEN
! MAT MAXINDEX=INDEX
! LET MAXDISTANCE=DISTANCE(GOAL)
! END IF
ELSE
!IF MINDISTANCE>DISTANCE(I) THEN
FOR J=1 TO SIZE
IF I<>J AND A(I,J)<>INF AND VISITED(J)=FALSE THEN
LET VISITED(I)=TRUE
LET DISTANCE(J)=DISTANCE(I)+A(I,J)
LET INDEX(I)=J
CALL VISIT(J,GOAL)
LET VISITED(I)=FALSE
LET INDEX(I)=0
LET DISTANCE(J)=0
END IF
NEXT J
!END IF
END IF
END SUB
|
|