Question

Python3 question.

Suppose that a graph represent as adjacency matrix, how could it perform DFS by using stack.

Graph is a undirect and unweighted graph.

Answer 1

# do comment if any problem arises

# Code

#this implementation uses list as stacks

# this function returns all vertices connected with given vertex that are not visited till now

def find_next(graph, visited):

    vertices = []

    # for all vertices in graph

    for vertex in range(len(graph)):

        # if vertex is connected to given vertex and not visited till now

        if graph[vertex] == True and vertex not in visited:

                # then add it to vertices

                vertices.append(int(vertex))

    return vertices

def dfs(graph, start, visited=[]):

    #if vertex is already visited then return

    if start in visited:

        return

    #add to visited vertices

    visited.append(start)

    #print current vertex

    print(start, end=' ')

    #this list stores all connected vertices to start which are not in visited

    next_v = find_next(graph[start], visited)

    for next in next_v:

        dfs(graph, next, visited)

    return visited

graph = [[0, 1, 1, 0, 0],

         [1, 0, 0, 1, 0],

         [1, 0, 0, 0, 1],

         [0, 1, 0, 0, 0],

         [0, 0, 1, 0, 0]]

# graphical representation of graph

#           0

#          /  \

#         1    2

#        /      \

#       3        4

# call dfs with starting vertex 0

dfs(graph, 0)

Output: