CODEWITHSUNDEEP
pythonalgorithmsearchgraphtree
VDog
VDog

Reputation: 1173

depth first search in an undirected, weighted graph using adjacency matrix?

I don't want the answer, but I'm having trouble keeping track of the nodes. Meaning, say I have nodes 0, 1, 2, 3,4, 5, 6, 7, where 0 is start, and 7 is goal, I made an adjacency matrix like so: 

[
    [0, 3, 0, 0, 4, 0, 0, 0],
    [3, 0, 0, 0, 5, 0, 8, 0],
    [0, 0, 0, 4, 0, 5, 0, 0],
    [0, 0, 4, 0, 0, 0, 0, 14],
    [4, 5, 0, 0, 0, 2, 0, 0],
    [0, 0, 5, 0, 2, 0, 4, 0],
    [0, 8, 0, 5, 0, 4, 0, 0],
    [0, 0, 0, 14, 0, 0, 0, 0]
]

if it's a 0, there is no link between the nodes, otherwise, if it's greater than 1, then the number is the weight of the edge between those nodes.

I'm having trouble identifying what the actual node would be, versus a path.

I can find the goal, but I wouldn't know how to show the path to the goal, and what the total weight would be?

EDIT: Here is what I am trying to achieve (this will not work, but this is the general idea):

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

    stack.append(graph[start])
    visited.append(start)

    while (len(stack) != 0):
        current_node = stack.pop()
        if current_node not in visited:
            visited.append(current_node)

        if current_node = goal:
            return path
        else:
            for nodes in current_node:
                if nodes not in visited:
                    stack.append(nodes)

if the edges were unweighed this would be easier, but I'm basically adding all neighbors of the current node as long as I haven't visited it to the stack, until I find the goal node, and then I want to return the path. but in this case I know it's broken because 1) I'm not sure how to check if it's the goal node, since I'm only storing the nodes neighbors, and 2) not checking for the full path.

Upvotes: 0

Views: 2951

Answers (1)

pseudo_teetotaler
pseudo_teetotaler

Reputation: 1575

Maintain a path variable to store the vertex as u encounter them. When u found end vertex, the path variable will have the path.

Find the pseudo code for reference. Pardon any minor mistake in the code

DFS (vertex start, vertex end, Graph G, list path):
         if(start==end):
              return TRUE
         for vertex in adjacent(start):
            if vertex not in path:     # has not been traversed
               path = path + [vertex]
               a = DFS(vertex, end, G, path)
               if a==TRUE:  # end vertex was found 
                  return TRUE
               path.delete(vertex)  # delete the vertex added,as its not in the path from start to end

Acc. to your code, when u found the goal vertex, the visited stack is contains the element in the path.

I hope it helped.

Upvotes: 1

Related Questions