Posted on by Kalkicode
Code Graph

DFS traversal of directed graph in vb.net

Vb program for DFS traversal of directed graph. Here problem description and explanation.

' Include namespace system
Imports System 
'    Vb.net program for 
'    DFS traversal of directed graph using recursion
Public Class AjlistNode 
    '  Vertices node key
    Public  id As Integer
    Public  [next] As AjlistNode
    Public Sub New(ByVal id As Integer)
        '  Set value of node key
        Me.id = id
        Me.next = Nothing
    
    End Sub

End Class
Public Class Vertices 
    Public  data As Integer
    Public  [next] As AjlistNode
    Public  last As AjlistNode
    Public Sub New(ByVal data As Integer)
        
        Me.data = data
        Me.next = Nothing
        Me.last = Nothing
    
    End Sub

End Class
public Class Graph 
    '  Number of Vertices
    Public  size As Integer
    Public  node As Vertices()
    
    Public Sub New(ByVal size As Integer)
        
        '  Set value
        Me.size = size
        Me.node = New Vertices(size){}
        Me.setData()
    
    End Sub
    '  Set initial node value
    
    Public Sub setData()
        if (Me.size <= 0) Then 
            Console.WriteLine(""& vbLf &"Empty Graph")
        Else 
            Dim index As Integer = 0
            While index < Me.size
                '  Set initial node value
                Me.node(index) = New Vertices(index)
            index += 1
            End While
        End IF

    
    End Sub
    '  Connect two nodes
    
    Public Sub connect(ByVal start As Integer, ByVal last As Integer)
        Dim edge As AjlistNode = New AjlistNode(last)
        if (Me.node(start).[next]  Is  Nothing) Then 
            Me.node(start).[next] = edge
        Else 
            '  Add edge at the end
            Me.node(start).last.[next] = edge
        End IF

        '  Get last edge 
        Me.node(start).last = edge
    
    End Sub
    '   Handling the request of adding new edge
    
    Public Sub addEdge(ByVal start As Integer, ByVal last As Integer)
        if (start >= 0 AndAlso start < Me.size AndAlso 
            last >= 0 AndAlso last < Me.size) Then 
            '  Safe connection
            Me.connect(start, last)
        Else 
            '  When invalid nodes
            Console.WriteLine( vbLf & "Here Something Wrong")
        End IF

    
    End Sub
    
    Public Sub printGraph()
        if (Me.size > 0) Then 
            '  Print graph ajlist Node value
            Dim index As Integer = 0
            While index < Me.size

                Console.Write( vbLf & "Adjacency list of vertex " +
                              index.ToString() + " :")
                Dim temp As AjlistNode = Me.node(index).[next]
                
                while (temp IsNot Nothing) 
                
                    '  Display graph node 
                    Console.Write("  " + Me.node(temp.id).data.ToString())
                    '  visit to next edge
                    temp = temp.[next]
                End While
            index += 1
            End While
        End If

    
    End Sub
    '  Dfs traversal of given node point
    
    Public Sub dfs(ByVal visit As Boolean(),
      			   ByVal point As Integer)
        if (visit(point)) Then 
            '  We already visited this node
            Return
        End If

        '  Set active node visit
        visit(point) = True
        '  Display visiting node point
        Console.Write("  " + point.ToString())
        '  Get node edge  
        Dim temp As AjlistNode = Me.node(point).[next]
        '  Iterate all edges in given node point
        
        while (temp IsNot Nothing) 
        
            Me.dfs(visit, temp.id)
            '  next edge
            temp = temp.[next]
        End While
    
    End Sub
    '  Handles the request of printing dfs sequence
    
    Public Sub printDFS(ByVal point As Integer)
        if (Me.size <= 0 OrElse point < 0 OrElse 
            point >= Me.size) Then 
            Return
        End If

        '  This is node visitor
        Dim visit As Boolean() = New Boolean(Me.size){}
        '  There is no initial node visiting
        Dim i As Integer = 0
        While i < Me.size

            visit(i) = False
        i += 1
        End While
        '  Start traversal
        Me.dfs(visit, point)
    
    End Sub
    
    Public Shared Sub Main(ByVal args As String())
        '  6 implies the number of nodes in graph
        Dim g As Graph = New Graph(6)
        g.addEdge(0, 1)
        g.addEdge(0, 5)
        g.addEdge(1, 1)
        g.addEdge(2, 1)
        g.addEdge(3, 0)
        g.addEdge(3, 3)
        g.addEdge(4, 2)
        g.addEdge(4, 3)
        g.addEdge(5, 1)
        g.printGraph()
        Console.Write(""& vbLf &"DFS :")
        g.printDFS(4)
    
    End Sub

End Class

Output

Adjacency list of vertex 0 :  1  5
Adjacency list of vertex 1 :  1
Adjacency list of vertex 2 :  1
Adjacency list of vertex 3 :  0  3
Adjacency list of vertex 4 :  2  3
Adjacency list of vertex 5 :  1
DFS :  4  2  1  3  0  5

Comment

Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.

New Comment