一 求有向图中强连通分量.doc

一 求有向图中强连通分量(1) 功能求有向图中强连通分量(2) 调用方式先输入顶点个数（29），点“确定”后将出现顶点图示，再将每条有向边按起始点、终点输入。每输入一条边起、终点后，按“输入”确认，就可在图形中显示该边。当所有边输入完毕后，点“终了”键结束。将在现有图形上画出(3) 算法说明算法步骤如下：1、 在二维数组pm中形成图的邻接矩阵。2、 利用warshell算法计算图的路径矩阵，并存放在pm中：For k = 1 To p 计算pm For j = 1 To p For i = 1 To p If pm(i, k) = 1 And pm(k, j) = 1 Then pm(i, j) = 1 End If Next i Next j Next k3、 计算cm矩阵：For i = 1 To p 计算cm For j = 1 To p If pm(i, j) = 1 And pm(j, i) = 1 Then cm(i, j) = 1 End If Next j Next i4、依次检查cm各行，(4) 程序清单Dim ans As StringDim PI As DoubleDim pm(10, 10), cm(10, 10), om(10, 10), i, j, k, p, a, c, d, n, b(10), s(10, 10), x(10), y(10) As IntegerFunction arrow(i, j) Line (x(i), y(i)-(x(j), y(j), QBColor(0) t = Atn(y(i) - y(j) / (x(i) - x(j) If x(j) x(i) Then t = t + PI End If Me.DrawWidth = 2 Line (x(j), y(j)-(x(j) + 40 * Cos(t + PI / 16), y(j) + 40 * Sin(t + PI / 16), QBColor(0) Line (x(j), y(j)-(x(j) + 40 * Cos(t - PI / 16), y(j) + 40 * Sin(t - PI / 16), QBColor(0) Me.DrawWidth = 1End FunctionPrivate 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 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 SubPrivate 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 p Or j p Then 判断顶点合法 c = MsgBox(顶点有误，请从新输入, 0) Text2.Text = Text3.Text = End If If c = 0 Then 画边 om(i, j) = 1 a = arrow(i, j) Text2.Text = Text3.Text = End If End SubPrivate Sub Command3_Click() n = 0 For i = 1 To p om(i, i) = 1 For j = 1 To p pm(i, j) = om(i, j) Next j Next i For k = 1 To p 计算pm For j = 1 To p For i = 1 To p If pm(i, k) = 1 And pm(k, j) = 1 Then pm(i, j) = 1 End If Next i Next j Next k For i = 1 To p 计算cm For j = 1 To p If pm(i, j) = 1 And pm(j, i) = 1 Then cm(i, j) = 1 End If Next j Next i For i = 1 To p 计算sn If cm(i, i) = 1 Then n = n + 1 For j = i To p If cm(i, j) = 1 Then b(n) = b(n) + 1 s(n, b(n) = j cm(j, j) = 0 End If Next j End If Next i For i = 1 To n 画出强连通分支 For j = 1 To b(i) For k = 1 To b(i) If om(s(i, j), s(i, k) = 1 Then If s(i, j) = s(i, k) Then FillColor = QBColor(i) FillStyle = 0 Circle (x(s(i, j), y(s(i, j), 10, QBColor(i) Else Line (x(s(i, j), y(s(i, j)-(x(s(i, k), y(s(i, k), BackColor Me.DrawWidth = 2 Line (x(s(i, j), y(s(i, j)-(x(s(i, k), y(s(i, k), QBColor(i) Me.DrawWidth = 1 End If End If Next k Next j Next i ans = n Label4.Caption = 共有 + ans + 个强连通分支End SubSub Form_Load() PI = 3.14 For i = 0 To 9 初始化