/***********************************************************
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()
