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