縦形探索 - abwiki @ ウィキ (ActiveBasic非公式wiki)

/***********************************************************
dfs.c -- 縦形探索
***********************************************************/
Declare Function printf CDECL Lib"msvcrt" (fmt As *Byte, ...) As Long


#console
const NMAX =100 /* 点の数の上限 */
Dim adjacent[NMAX, NMAX] As Byte /* 隣接行列 */

Dim n As Long
n=7
/* 点の数 (例) */
Dim data[ELM(10)] = [ 1, 2, 2, 3, 1, 3, 2, 4, 5, 7 ] As Long /* データ (例) */

Dim visited[NMAX] As Byte /* 訪れたなら1 */

Function Cnot(i As Long) As Long
If i Then
Cnot = 0
Else
Cnot = 1
End If

End Function


Sub readgraph() /* グラフ入力 */
Dim i As Long, j As Long, k As Long

For i=1 To n
For j=1 To n
adjacent[i,j] = 0
Next
Next

For k=0 To 9
If (k mod 2) = 0 Then
i = data[k]
Else
j = data[k]
adjacent[i,j] = 1
adjacent[j,i] = 1
End If
Next
printf(Ex"隣接行列:\n")
For i=1 To n
For j=1 To n
printf(Ex" %d", adjacent[i,j])
Next
printf(Ex"\n")
Next
End Sub



Sub visit(i As Long) /* 点 i を訪れる (再帰的) */
Dim j As Long

printf(Ex" %d", i)
visited[i] = 1
For j=1 To n
If adjacent[i,j] And Cnot(visited[j]) Then visit(j)
Next
End Sub



Sub main()
Dim i As Long, count As Long

readgraph() /* グラフのデータを読む */
For i=1 To n
visited[i] = 0 /* まだどこも訪れていない */
Next
printf(Ex"連結成分:\n")
count = 0
For i=1 To n /* 連結成分を数える */
If Cnot(visited[i]) Then
count = count + 1
printf(Ex"%3d:", count)
visit(i)
printf(Ex"\n")
End If
Next
End Sub
main()