「縦形探索」の編集履歴（バックアップ）一覧はこちら

「縦形探索」(2010/10/22 (金) 00:39:15) の最新版変更点

追加された行は緑色になります。

削除された行は赤色になります。

#asciiart(blockquote){
/***********************************************************
	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)  /* 点 {\tt 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()
}

#asciiart(blockquote){
/***********************************************************
	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()
}