graph.cls

关于图的算法

VERSION 1.0 CLASS
BEGIN
  MultiUse = -1  'True
  Persistable = 0  'NotPersistable
  DataBindingBehavior = 0  'vbNone
  DataSourceBehavior  = 0  'vbNone
  MTSTransactionMode  = 0  'NotAnMTSObject
END
Attribute VB_Name = "Graph"
Attribute VB_GlobalNameSpace = False
Attribute VB_Creatable = True
Attribute VB_PredeclaredId = False
Attribute VB_Exposed = False
Private Parent As String                '生成树的子树父结点
Private Result() As String              '遍历的结果
Private A() As Integer                  '有向图的邻接矩阵，可以有权值
Private E() As Integer                  '无向图的邻接矩阵
Private V() As String                   '图的顶点矩阵
Private sPath() As String               'Floyd的最短路走的过程
Private Row As Integer                  '邻接矩阵的行数
Private Col As Integer                  '邻接矩阵的列数
Private Visited() As Integer            '顶点访问标志数组，1：访问过；0：未访问
Private ResultTree As TreeView          '图的遍历结果、生成树的显示控件对象
Private Qu As Queue                     '广度优先遍历需要的队列对象
Private MyStack As Stack                '拓扑排序中需要的栈对象
Private SG As Stack
Private TG As Stack
Private VE() As Integer
Private VL() As Integer
Private TreeNum As Integer
Private Const MaxWeight = 10000         '最短路计算用的，就是说最大距离这么大的话，就认为是距离无群大，不通！
Private Sub Class_Initialize() '初始化类
Row = 0
Col = 0
TreeNum = 0
ReDim E(Row, Col) As Integer
ReDim V(Row) As String
Set ResultTree = Nothing
Set Qu = New Queue
Set MyStack = New Stack
Set SG = New Stack
Set TG = New Stack
End Sub
'**************************************************************************
'设置该图的邻接矩阵行数，实际也是列数                                        *
'**************************************************************************
Public Sub SetRow(ByVal r As Integer)
    Row = r
    Col = r
    ReDim E(Row, Col) As Integer
    ReDim A(Row, Col) As Integer
    ReDim V(Row) As String
    ReDim Visited(Row) As Integer
    ReDim Result(Row) As String
    ReDim sPath(Row, Col) As String
    ReDim VE(Row) As Integer
    ReDim VL(Row) As Integer
    Row = Row - 1
    Col = Col - 1
End Sub
'**************************************************************************
'方法：设置无向图邻接矩阵E的第r行、第c列的值，r,c从0开始计数                  *
'**************************************************************************
Public Sub SetE(ByVal EA As Integer, ByVal r As Integer, ByVal C As Integer)
    E(r, C) = EA
End Sub
'**************************************************************************
'方法：设置有向图、有向含权图邻接矩阵E的第r行、第c列的权值，r,c从0开始计数     *
'**************************************************************************
Public Sub SetA(ByVal EA As Integer, ByVal r As Integer, ByVal C As Integer)
    A(r, C) = EA
End Sub
Property Set SetResultTree(ByVal t As TreeView)
    Set ResultTree = t
End Property
'**************************************************************************
'                           深度优先搜索遍历图                             *
'程序总是设置从邻接矩阵的第0行开始执行                                      *
'结果要显示在ResultTree控件上，这是个TreeView类型的对象                     *
'生成Visited数组，记录下每个顶点上经过的次数                                *
'生成Result数组，就是遍历图的线性结果                                       *
'**************************************************************************
Public Sub DepthTraverse()
Dim tStatus As Boolean
    If ResultTree Is Nothing Then Exit Sub
    ResultTree.Nodes.Clear
    'TreeView是个操作速度比较慢的控件，要等着它清空以前的结点！
    While ResultTree.Nodes.Count > 0
        ResultTree.Nodes.Clear
    Wend
    
    tStatus = True
    While tStatus
        tStatus = False
        '找到有不为0元素的行，结果在m中，也就是说，从m开始遍历
        '对连通图，m仅仅有一个值，对非连通图，则可能要遍历多次，所以m也是多个值
        For m = 0 To Row
            For i = 0 To Col
                If E(m, i) <> 0 Then tStatus = True: Exit For
            Next i
            If tStatus Then Exit For
        Next m
                
        If tStatus Then
            '实际上，你假设这里m=0就明白了，自然第一个顶点是这个遍历树的根
            '对于非连通图，TreeNum>1,就是说有TreeNum个生成树
            TreeNum = TreeNum + 1
            Visited(m) = 1
            Parent = V(m)
            sCaption = V(m)
            sNode = V(m)
            '在TreeView控件中显示这个根！遍历结果数组中记录下顶点名称
            Set Tnode = ResultTree.Nodes.Add(, , sNode, sCaption, 2, 1)
            Result(m) = V(m)
            
            'For i = 0 To Row  '这是一种遍历方向，但我们教材中比较喜欢下列方向
            For i = Row To 0 Step -1
                If E(m, i) <> 0 Then
                    DTrave m, Row
                    Parent = V(m)
                    Visited(m) = Visited(m) + 1
                End If
            Next i
        End If
    Wend
End Sub
'**************************************************************************
'属性：设置第n个顶点的名称                                                  *
'**************************************************************************
Public Sub SetV(ByVal Vs As String, ByVal n As Integer)
    V(n) = Vs
End Sub
'**************************************************************************
'从第m个顶点开始，深度优先搜索遍历图                                        *
'm实际是邻接矩阵的行                                                       *
'r是邻接矩阵最大行或者列                                                   *
'**************************************************************************
Private Sub DTrave(ByVal m As Integer, ByVal r As Integer)
Dim i As Integer
    'For i = 0 To R  '这是一种遍历方向，但我们教材中比较喜欢下列方向
    For i = r To 0 Step -1
        '意思很明白了：找有不为0的列，就是下次要去的行
        If E(m, i) <> 0 Then
            E(m, i) = 0: E(i, m) = 0
            If Visited(i) = 0 Then
                Result(i) = V(i)
                '在C语言中，下面这句话是printf(),现在我们要把该结点顶点名称加在treeView上
                Set Tnode = ResultTree.Nodes.Add(Parent, tvwChild, V(i), V(i), 1, 2)
            End If
            m = i
            Parent = V(m)
            '这个地方，Visited(i)++，就是以后分析关节点的依据，要不我们不知道在这个顶点上
            '来过几次
            Visited(i) = Visited(i) + 1
            DTrave m, r
        End If
    Next i
End Sub
'**************************************************************************
'                           广度优先搜索遍历图                             *
'程序总是设置从邻接矩阵的第0行开始执行                                      *
'结果要显示在ResultTree控件上，这是个TreeView类型的对象                     *
'生成Visited数组，记录下每个顶点上经过的次数                                *
'生成Result数组，就是遍历图的线性结果                                       *
'**************************************************************************
Public Sub BreadthTraverse()
Dim tStatus As Boolean
    If ResultTree Is Nothing Then Exit Sub
    ResultTree.Nodes.Clear
    'TreeView是个操作速度比较慢的控件，要等着它清空以前的结点！
    While ResultTree.Nodes.Count > 0
        ResultTree.Nodes.Clear
    Wend

    tStatus = True
    m = 0
    While tStatus
        tStatus = False
        '找到有不为0元素的行，结果在m中，也就是说，从m开始遍历
        '对连通图，m仅仅有一个值，对非连通图，则可能要遍历多次，所以m也是多个值
        For m = 0 To Row
            For i = 0 To Col
                If E(m, i) <> 0 Then tStatus = True: Exit For
            Next i
            If tStatus Then Exit For
        Next m
        '下面的算法和教材中的介绍一致，也是逐个顶点取邻接顶点，然后进队列
        If tStatus Then
            '对于非连通图，TreeNum>1,就是说有TreeNum个生成树
            TreeNum = TreeNum + 1
            Visited(m) = 1
            Parent = V(m)
            sCaption = V(m)
            sNode = V(m)
            Qu.Append m
            Set Tnode = ResultTree.Nodes.Add(, , sNode, sCaption, 2, 1)
            Result(m) = V(m)
            BTrave m, Row
        End If
    Wend
End Sub
'**************************************************************************
'从第m个顶点开始，执行广度优先搜索遍历                                       *
'm：实际是邻接矩阵的行；                                                    *
'r：邻接矩阵最大行列数                                                      *
'**************************************************************************
Private Sub BTrave(ByVal m As Integer, ByVal r As Integer)
Dim i As Integer

While Not Qu.IsQueueEmpty()
    m = Qu.GetHead
    For i = r To 0 Step -1
        If E(m, i) <> 0 Then
            E(m, i) = 0: E(i, m) = 0
            Qu.Append i
            
            If Visited(i) = 0 Then
                Result(i) = V(i)
                Set Tnode = ResultTree.Nodes.Add(V(m), tvwChild, V(i), V(i), 1, 2)
            End If
            '这里，m顶点有几个邻接顶点，就是有几个子树
            Visited(i) = 1
            Visited(m) = Visited(m) + 1
        End If
    Next i
Wend
End Sub
'**************************************************************************
'方法：返回第n个遍历结果，因为图的遍历结果是树，所以这个方法意义不大           *
'**************************************************************************
Public Function GetResult(ByVal n As Integer) As String
    GetResult = Result(n)
End Function
'**************************************************************************
'属性：返回顶点个数                                                        *
'**************************************************************************
Property Get GetVertexNumber() As Integer
    GetVertexNumber = Row + 1
End Property
'**************************************************************************
'给出关节点，基本算法就是遍历图的过程中，统计各个顶点上走过的次数              *
'这实际就是看Visited数组中的值了                                            *
'**************************************************************************
Public Function Articulation(ByVal n As Integer) As String
Dim i As Integer
    'i实际就是到这个顶点上走过的次数，一开始访问总是设置为1，所以
    '这个值减1就是该顶点下生成树子树的数目，例如i=3，下面的子树即为2
    '如果一个顶点下有两个以上的子树，则该点为关节点.
    '但对于非连通图，每个连通分量的根结点都是关节点了，所以要自己根据具体图来分析
    i = Visited(n)
    If TreeNum = 1 Then
        i = i - 1
    End If
    If i > 1 Then
        Articulation = V(n) + ":" + Str(Visited(n) - 1) + "个子树"
        Exit Function
    End If
Articulation = ""
End Function
'**************************************************************************
'Floyd最短路计算，就是逐个顶点之间的最短距离                                 *
'这个算法很经典，就是j到k的距离，可以理解为j到i、再由i到k的距离               *
'所以使用一个三重循环，就可以确定逐个点到点的最短距离                         *
'**************************************************************************
Public Sub Floyd(ByRef Res() As Integer, ByRef sP() As String)
Dim i As Integer
Dim j As Integer
Dim k As Integer

For i = 0 To Row
    For j = 0 To Row
        If i <> j And A(i, j) = 0 Then A(i, j) = MaxWeight
    Next j