四、图的遍历程序

图的遍历 (1) 功能 对给定的无向图进行深度优先遍历和广度优先遍历 (2) 调用方式 先输入顶点个数（2～9），点“确定”后将出现顶点图示，再将每条有向边按起始点、终点输入。每输入一条边起、终点后，按“输入”确认，就可在图形中显示该边。当所有边输入完毕后，点“深度优先遍历”键（或“广度优先遍历”键），将在现有图形上依次画出遍历所经过的每条边。 (3) 算法说明 深度优先遍历类似于树的先根遍历，是树的先根遍历的推广。 广度优先遍历类似于树的按层遍历。 (4) 程序 清单 安全隐患排查清单下载最新工程量清单计量规则下载程序清单下载家私清单下载送货清单下载 Dim ans As String Dim PI As Double Dim pm(10, 10), om(10, 10), i, j, k, l, p, m, a, c, d, n, b(10), s(10, 10), x(10), y(10), dsp(20), bsp(20), tmp(20) As Integer Dim linei As Integer Function dfs(j As Integer) Dim l As Integer b(j) = 1 l = j For j = 1 To p 'c = MsgBox(i, 0) If pm(l, j) = 1 And b(j) = 0 Then n = n + 1 dsp(n) = l n = n + 1 dsp(n) = j pm(l, j) = 0 pm(j, l) = 0 dfs (j) End If Next j End Function Function bfs(j As Integer) b(j) = 1 For j = 1 To p 'c = MsgBox(i, 0) If pm(i, j) = 1 Then n = n + 1 bsp(n) = i n = n + 1 bsp(n) = j For k = 1 To p pm(k, j) = 0 'pm(j, k) = 0 Next k bfs (j) End If Next j End Function Private Sub Command1_Click() Cls a = 0 If Not IsNumeric(Text1.Text) Then                '输入顶点个数 a = MsgBox("请输入2-9的整数", 0) Text1.Text = "" Else p = Int(Text1.Text) If p < 2 Or p > 9 Then a = MsgBox("顶点个数有误，请从新输入", 0) Text1.Text = "" End If End If If a = 0 Then                                '依据顶点个数画图 Dim ra As Integer ScaleTop = -1100 ScaleLeft = -700 ScaleHeight = 2000 ScaleWidth = 2000 For i = 1 To p FillColor = QBColor(0) FillStyle = 0 x(i) = Cos(2 * PI * (i - 1) / p) * 500 y(i) = Sin(2 * PI * (i - 1) / p) * 500 Circle (x(i), y(i)), 7, QBColor(0) CurrentX = x(i) * 1.2 CurrentY = y(i) * 1.2 Print i Next i End If End Sub Private Sub Command2_Click() c = 0 If Not IsNumeric(Text2.Text) Or Not IsNumeric(Text3.Text) Then    '输入边的信息 c = MsgBox("顶点必须为数字，请从新输入", 0) Text2.Text = "" Text3.Text = "" Exit Sub Else i = Int(Text2.Text) j = Int(Text3.Text) End If If i < 1 Or i > p Or j < 1 Or j > p Then                    '判断顶点合法 c = MsgBox("顶点有误，请从新输入", 0) Text2.Text = "" Text3.Text = "" Else If pm(i, j) = 1 Or pm(j, i) = 1 Then c = MsgBox("该边已经添加，请输入下一条边：", 0) Text3.Text = "" Text2.Text = "" End If End If If c = 0 Then                                                '画边 k = k + 1 pm(i, j) = 1 pm(j, i) = 1 Line (x(i), y(i))-(x(j), y(j)), QBColor(0) Text2.Text = "" Text3.Text = "" End If End Sub Private Sub Command3_Click() n = 0 For i = 1 To p b(i) = 0 Next i For i = 1 To p If Not (b(i)) Then dfs (i) End If Next i For i = 1 To p * 2 tmp(i) = dsp(i) Next i Timer1.Enabled = True End Sub Private Sub Command4_Click() n = 0 For i = 1 To p b(i) = 0 Next i For i = 1 To p If Not (b(i)) Then bfs (i) End If Next i For i = 1 To p * 2 tmp(i) = bsp(i) Next i Timer1.Enabled = True End Sub Private Sub Command5_Click() tmp(1) = p For i = 2 To 2 * p tmp(i) = p - i / 2 Next i Timer1.Enabled = True End Sub Sub Form_Load() PI = 3.14 linei = 1 For i = 0 To 9                                '初始化 b(i) = 0 For j = 0 To 9 pm(i, j) = 0 s(i, j) = 0 Next j Next i End Sub Private Sub Timer1_Timer() Me.DrawWidth = 2 Line (x(tmp(linei)), y(tmp(linei)))-(x(tmp(linei + 1)), y(tmp(linei + 1))), QBColor(1) Me.DrawWidth = 1 linei = linei + 2 If linei >= 2 * p Then Timer1.Enabled = False linei = 1 End If End Sub (5)    实例 1、输入顶点个数：6 2、依次输入各边：1－2，1―5，2－3，2－5，3－5，3－6，4－5，4－6， 3、点“深度优先遍历”后，将出现如下图形显示：