form1.frm

关于图的算法

VERSION 5.00
Object = "{F9043C88-F6F2-101A-A3C9-08002B2F49FB}#1.2#0"; "comdlg32.ocx"
Object = "{831FDD16-0C5C-11D2-A9FC-0000F8754DA1}#2.0#0"; "mscomctl.ocx"
Object = "{5E9E78A0-531B-11CF-91F6-C2863C385E30}#1.0#0"; "MSFLXGRD.OCX"
Begin VB.Form Form1 
   Caption         =   "图的相关实验"
   ClientHeight    =   5385
   ClientLeft      =   165
   ClientTop       =   450
   ClientWidth     =   6060
   LinkTopic       =   "Form1"
   ScaleHeight     =   5385
   ScaleWidth      =   6060
   StartUpPosition =   1  'CenterOwner
   Begin VB.CheckBox Check1 
      Appearance      =   0  'Flat
      BackColor       =   &H80000004&
      Caption         =   "允许自动复制对称点数据"
      ForeColor       =   &H80000008&
      Height          =   255
      Left            =   3510
      TabIndex        =   8
      Top             =   5070
      Width           =   2415
   End
   Begin VB.TextBox Text3 
      Appearance      =   0  'Flat
      BackColor       =   &H00FFFF80&
      Height          =   255
      Left            =   1950
      TabIndex        =   7
      Text            =   "Text3"
      Top             =   2700
      Width           =   795
   End
   Begin VB.TextBox Text2 
      Appearance      =   0  'Flat
      Height          =   285
      Left            =   2310
      TabIndex        =   6
      Text            =   "Text2"
      Top             =   5040
      Width           =   1095
   End
   Begin VB.TextBox Text1 
      Appearance      =   0  'Flat
      Height          =   285
      Left            =   930
      TabIndex        =   4
      Text            =   "Text1"
      Top             =   5040
      Width           =   495
   End
   Begin MSFlexGridLib.MSFlexGrid MSFlexGrid1 
      Height          =   2595
      Left            =   0
      TabIndex        =   2
      ToolTipText     =   "鼠标双击即可改变/切换邻接矩阵的值，鼠标右键用来输入权值"
      Top             =   2430
      Width           =   6045
      _ExtentX        =   10663
      _ExtentY        =   4577
      _Version        =   393216
      AllowUserResizing=   3
      Appearance      =   0
      BeginProperty Font {0BE35203-8F91-11CE-9DE3-00AA004BB851} 
         Name            =   "MS Sans Serif"
         Size            =   8.25
         Charset         =   0
         Weight          =   400
         Underline       =   0   'False
         Italic          =   0   'False
         Strikethrough   =   0   'False
      EndProperty
   End
   Begin MSComctlLib.ImageList ImageList1 
      Left            =   5460
      Top             =   4770
      _ExtentX        =   1005
      _ExtentY        =   1005
      BackColor       =   -2147483643
      ImageWidth      =   16
      ImageHeight     =   16
      MaskColor       =   12632256
      _Version        =   393216
      BeginProperty Images {2C247F25-8591-11D1-B16A-00C0F0283628} 
         NumListImages   =   2
         BeginProperty ListImage1 {2C247F27-8591-11D1-B16A-00C0F0283628} 
            Picture         =   "Form1.frx":0000
            Key             =   ""
         EndProperty
         BeginProperty ListImage2 {2C247F27-8591-11D1-B16A-00C0F0283628} 
            Picture         =   "Form1.frx":0452
            Key             =   ""
         EndProperty
      EndProperty
   End
   Begin MSComctlLib.TreeView TreeView1 
      Height          =   2370
      Left            =   1650
      TabIndex        =   1
      Top             =   30
      Width           =   4395
      _ExtentX        =   7752
      _ExtentY        =   4180
      _Version        =   393217
      Style           =   7
      ImageList       =   "ImageList1"
      BorderStyle     =   1
      Appearance      =   0
   End
   Begin MSComDlg.CommonDialog CommonDialog1 
      Left            =   4980
      Top             =   4710
      _ExtentX        =   847
      _ExtentY        =   847
      _Version        =   393216
   End
   Begin VB.ListBox List1 
      Appearance      =   0  'Flat
      Height          =   2370
      Left            =   0
      TabIndex        =   0
      Top             =   30
      Width           =   1665
   End
   Begin VB.Label Label2 
      Caption         =   "顶点名称："
      Height          =   255
      Left            =   1470
      TabIndex        =   5
      Top             =   5070
      Width           =   1065
   End
   Begin VB.Label Label1 
      Caption         =   "顶点数量："
      Height          =   225
      Left            =   30
      TabIndex        =   3
      Top             =   5070
      Width           =   915
   End
   Begin VB.Menu F 
      Caption         =   "文件"
      Begin VB.Menu nc 
         Caption         =   "新建"
      End
      Begin VB.Menu s1 
         Caption         =   "-"
      End
      Begin VB.Menu fOpen 
         Caption         =   "打开"
      End
      Begin VB.Menu fSave 
         Caption         =   "保存"
      End
      Begin VB.Menu s0 
         Caption         =   "-"
      End
      Begin VB.Menu ex 
         Caption         =   "退出"
      End
   End
   Begin VB.Menu op 
      Caption         =   "操作"
      Begin VB.Menu Tr 
         Caption         =   "连通图、非连通图遍历(深度搜索优先)"
      End
      Begin VB.Menu ts 
         Caption         =   "连通图、非连通图遍历(广度搜索优先)"
      End
      Begin VB.Menu tp 
         Caption         =   "拓扑排序"
      End
      Begin VB.Menu DIJ 
         Caption         =   "最短路径(Dijkstra)"
      End
      Begin VB.Menu Floyd 
         Caption         =   "最短路径(Floyd)"
      End
      Begin VB.Menu AOE 
         Caption         =   "AOE网络"
      End
   End
End
Attribute VB_Name = "Form1"
Attribute VB_GlobalNameSpace = False
Attribute VB_Creatable = False
Attribute VB_PredeclaredId = True
Attribute VB_Exposed = False
Dim VerNum As Integer
Dim CurRow As Integer
Dim St As New Stack
Private Sub Command3_Click()
End
End Sub
Private Sub AOE_Click()
Dim G As New Graph
Dim r As Integer
Dim C As Integer
Dim Rf() As Integer
Dim sR() As String

r = MSFlexGrid1.Rows - 1
If r <= 1 Then Exit Sub

C = r: VerNum = r
G.SetRow r
ReDim Rf(r, r) As Integer
ReDim sR(r, r) As String

For i = 1 To r
    For j = 1 To C
        MSFlexGrid1.Row = i
        MSFlexGrid1.Col = j
        A = Val(MSFlexGrid1.Text)
        G.SetA A, i - 1, j - 1
    Next j
Next i
For i = 0 To r - 1
    MSFlexGrid1.Col = 0
    MSFlexGrid1.Row = i + 1
    s = MSFlexGrid1.Text
    G.SetV s, i
Next i
G.AOE

End Sub
Private Sub DIJ_Click()
Dim G As New Graph
Dim r As Integer
Dim C As Integer
Dim D() As Integer     '到各点的距离
Dim sPath() As String  '到各点的路径

r = MSFlexGrid1.Rows - 1
If r <= 1 Then Exit Sub

C = r: VerNum = r
G.SetRow r
ReDim D(r) As Integer
ReDim Path(r) As Integer
ReDim sPath(r) As String

For i = 1 To r
    For j = 1 To C
    MSFlexGrid1.Row = i
    MSFlexGrid1.Col = j
    A = Val(MSFlexGrid1.Text)
    G.SetA A, i - 1, j - 1
    Next j
Next i
For i = 0 To r - 1
    MSFlexGrid1.Col = 0
    MSFlexGrid1.Row = i + 1
    s = MSFlexGrid1.Text
    G.SetV s, i
Next i
'这个地方总是第0个顶点到其它顶点的距离
G.Dijkstra 0, D, Path, sPath

'-----------------------------------------------------------
'假如你要计算任意顶点到其他顶点的距离，用这个：
'Vn = MSFlexGrid1.Col
'Vn = Vn - 1
'G.Dijkstra Vn, D, Path, sPath
'就是鼠标点MSFlexGrid1上的任意位置，列将被认为是起始顶点。
'-----------------------------------------------------------

List1.Clear
For i = 1 To r
    List1.AddItem Str(D(i)) + "   " + sPath(i)
Next i
End Sub

Private Sub ex_Click()
End
End Sub
Private Sub Floyd_Click()
Dim G As New Graph
Dim r As Integer
Dim C As Integer
Dim Rf() As Integer
Dim sR() As String

r = MSFlexGrid1.Rows - 1
If r <= 1 Then Exit Sub

C = r: VerNum = r
G.SetRow r
ReDim Rf(r, r) As Integer
ReDim sR(r, r) As String

For i = 1 To r
    For j = 1 To C
    MSFlexGrid1.Row = i
    MSFlexGrid1.Col = j
    A = Val(MSFlexGrid1.Text)
    G.SetA A, i - 1, j - 1
    Next j
Next i
For i = 0 To r - 1
    MSFlexGrid1.Col = 0
    MSFlexGrid1.Row = i + 1
    s = MSFlexGrid1.Text
    G.SetV s, i
Next i
G.Floyd Rf, sR

For i = 1 To r
    MSFlexGrid1.ColWidth(i) = 1800
Next i

For i = 1 To r
    For j = 1 To C
        MSFlexGrid1.Row = i
        MSFlexGrid1.Col = j
        MSFlexGrid1.Text = Str(Rf(i - 1, j - 1)) + "：" + sR(i - 1, j - 1)
    Next j
Next i
End Sub

Private Sub fOpen_Click()
Dim A As Integer
Dim Fname As String
List1.Clear

CommonDialog1.ShowOpen
Fname = CommonDialog1.FileName
If Len(Fname) = 0 Then Exit Sub
Open Fname For Input As #1
Input #1, r, C

MSFlexGrid1.Rows = r + 1
MSFlexGrid1.Cols = C + 1

For i = 0 To r
    MSFlexGrid1.ColWidth(i) = 800
Next i

r = r - 1: C = C - 1
For i = 0 To r
    For j = 0 To C
    Input #1, A
    
    MSFlexGrid1.Row = i + 1
    MSFlexGrid1.Col = j + 1
    MSFlexGrid1.Text = Str(A)
    
    Next j
Next i
For i = 0 To r
    Input #1, s
    
    MSFlexGrid1.Col = 0
    MSFlexGrid1.Row = i + 1
    MSFlexGrid1.Text = s
    
    MSFlexGrid1.Row = 0
    MSFlexGrid1.Col = i + 1
    MSFlexGrid1.Text = s
    
Next i
Close #1
TreeView1.Nodes.Clear
End Sub

Private Sub Form_Load()
Text1.Text = ""
Text2.Text = ""
Text3.Text = ""
Text3.Visible = False
End Sub
Private Sub fSave_Click()
Dim r As Integer
Dim C As Integer
Dim Fname As String
CommonDialog1.ShowSave
Fname = CommonDialog1.FileName
r = MSFlexGrid1.Rows - 1
If r <= 1 Then Exit Sub
C = r
Open Fname For Output As #1
Print #1, r, C
For i = 1 To r
    For j = 1 To C
    MSFlexGrid1.Row = i
    MSFlexGrid1.Col = j
    A = Val(MSFlexGrid1.Text)
    Print #1, A;
    Next j
    Print #1,
Next i

For i = 0 To r - 1
    MSFlexGrid1.Col = 0
    MSFlexGrid1.Row = i + 1
    s = MSFlexGrid1.Text
    Print #1, s
Next i
Close #1
End Sub

Private Sub MSFlexGrid1_DblClick()
Dim r As Integer
Dim C As Integer
r = MSFlexGrid1.RowSel
C = MSFlexGrid1.ColSel

n = Val(MSFlexGrid1.Text)
If n = 0 Then
    n = 1
Else
    n = 0
End If
MSFlexGrid1.Col = C
MSFlexGrid1.Row = r
MSFlexGrid1.Text = Str(n)
End Sub

Private Sub MSFlexGrid1_MouseDown(Button As Integer, Shift As Integer, x As Single, y As Single)
If Button <> 2 Then Exit Sub
Text3.Top = MSFlexGrid1.CellTop + MSFlexGrid1.Top
Text3.Left = MSFlexGrid1.CellLeft
Text3.Width = MSFlexGrid1.CellWidth
Text3.Height = MSFlexGrid1.CellHeight
Text3.Font.Name = MSFlexGrid1.CellFontName
Text3.Font.Size = MSFlexGrid1.CellFontSize
Text3.Text = MSFlexGrid1.Text

Text3.Visible = True
End Sub
Private Sub nc_Click()
MSFlexGrid1.Clear
List1.Clear
TreeView1.Nodes.Clear
End Sub

Private Sub Text1_KeyPress(KeyAscii As Integer)
If KeyAscii <> 13 Then Exit Sub
s = Text1.Text
If Not IsNumeric(s) Then Exit Sub
n = Val(s)

MSFlexGrid1.Rows = n + 1
MSFlexGrid1.Cols = n + 1

For i = 0 To n
    MSFlexGrid1.ColWidth(i) = 300
Next i

For i = 1 To n
    For j = 1 To n
    MSFlexGrid1.Row = i
    MSFlexGrid1.Col = j
    MSFlexGrid1.Text = 0
    Next j
Next i
CurRow = 0
End Sub

Private Sub Text2_KeyPress(KeyAscii As Integer)
If KeyAscii <> 13 Then Exit Sub

If CurRow + 1 >= MSFlexGrid1.Cols Then Exit Sub

MSFlexGrid1.Row = 0
MSFlexGrid1.Col = CurRow + 1
MSFlexGrid1.Text = Text2.Text

MSFlexGrid1.Row = CurRow + 1
MSFlexGrid1.Col = 0
MSFlexGrid1.Text = Text2.Text

CurRow = CurRow + 1

Text2.SelStart = 0
Text2.SelLength = Len(Text2.Text)
Text2.SetFocus
End Sub
Private Sub Text3_KeyPress(KeyAscii As Integer)
If KeyAscii <> 13 Then Exit Sub
MSFlexGrid1.Text = Text3.Text
If Check1.Value = 0 Then Text3.Visible = False: Exit Sub
C = MSFlexGrid1.Col
r = MSFlexGrid1.Row
MSFlexGrid1.Row = C
MSFlexGrid1.Col = r
MSFlexGrid1.Text = Text3.Text
Text3.Visible = False
End Sub
Private Sub tp_Click()
Dim G As New Graph
Dim r As Integer
Dim C As Integer
Dim Result(200) As String

r = MSFlexGrid1.Rows - 1
If r <= 1 Then Exit Sub
C = r: VerNum = r
'ReDim Result(r + 1) As String

G.SetRow r
For i = 1 To r
    For j = 1 To C
    MSFlexGrid1.Row = i
    MSFlexGrid1.Col = j
    A = Val(MSFlexGrid1.Text)
    G.SetA A, i - 1, j - 1
    If A > 1 Then A = 1
    G.SetE A, i - 1, j - 1
    Next j
Next i
For i = 0 To r - 1
    MSFlexGrid1.Col = 0
    MSFlexGrid1.Row = i + 1
    s = MSFlexGrid1.Text
    G.SetV s, i
Next i
Set G.SetResultTree = TreeView1
G.TopoSort Result
List1.Clear
For i = 0 To r
    List1.AddItem Result(i)
Next i
End Sub

Private Sub Tr_Click()
Dim G As New Graph
Dim r As Integer
Dim C As Integer
TreeView1.Nodes.Clear
r = MSFlexGrid1.Rows - 1
If r <= 1 Then Exit Sub
C = r: VerNum = r
G.SetRow r
For i = 1 To r
    For j = 1 To C
    MSFlexGrid1.Row = i
    MSFlexGrid1.Col = j
    A = Val(MSFlexGrid1.Text)
    G.SetA A, i - 1, j - 1
    If A > 1 Then A = 1
    G.SetE A, i - 1, j - 1
    Next j
Next i
For i = 0 To r - 1
    MSFlexGrid1.Col = 0
    MSFlexGrid1.Row = i + 1
    s = MSFlexGrid1.Text
    G.SetV s, i
Next i
Set G.SetResultTree = TreeView1
G.DepthTraverse
List1.Clear
List1.AddItem "遍历结果"
n = G.GetVertexNumber
For i = 0 To n
    List1.AddItem G.GetResult(i)
Next i
List1.AddItem "关节点"
For i = 0 To n
    s = G.Articulation(i)
    If Len(s) > 0 Then List1.AddItem s
Next i
End Sub

Private Sub ts_Click()
Dim G As New Graph
Dim r As Integer
Dim C As Integer
TreeView1.Nodes.Clear
r = MSFlexGrid1.Rows - 1
If r <= 1 Then Exit Sub
C = r: VerNum = r
G.SetRow r
For i = 1 To r
    For j = 1 To C
    MSFlexGrid1.Row = i
    MSFlexGrid1.Col = j
    A = Val(MSFlexGrid1.Text)
    G.SetA A, i - 1, j - 1
    If A > 1 Then A = 1
    G.SetE A, i - 1, j - 1
    Next j
Next i
For i = 0 To r - 1
    MSFlexGrid1.Col = 0
    MSFlexGrid1.Row = i + 1
    s = MSFlexGrid1.Text
    G.SetV s, i
Next i
Set G.SetResultTree = TreeView1
G.BreadthTraverse
List1.Clear
List1.AddItem "遍历结果"
n = G.GetVertexNumber
For i = 0 To n
    List1.AddItem G.GetResult(i)
Next i
List1.AddItem "关节点"
For i = 0 To n
    s = G.Articulation(i)
    If Len(s) > 0 Then List1.AddItem s
Next i
End Sub