finding the adjacency list and using depth first search algorithm to find possible pairs

<class Graph:
    def __init__(self, num_nodes, edges):
        self.num_nodes = num_nodes
        self.data = [[] for _ in range(num_nodes)]
        for v1, v2 in edges:
            self.data[v1].append(v2)
            self.data[v2].append(v1)

    def __repr__(self):
        return "\n".join(["{} : {}".format(i, neighbors) for (i, neighbors) in enumerate(self.data)])

    def __str__(self):
        return repr(self)



# List with edges
l = [(0, 1),(0, 2),(1, 2),(2, 3)]
graph = Graph(4,l)
graph   # adjacency list


Output:

0 : [1, 2]
1 : [0, 2]
2 : [0, 1, 3]
3 : [2]



loop = []
def dfs(graph,root):
    stack = []
    discovered = [False]*len(graph.data)
    result = []
    stack.append(root)
    
    while len(stack)>0:
        current = stack.pop()
        if not discovered[current]:
            discovered[current]=True
            result.append(current)
            for node in graph.data[current]:
                if not discovered[node]:
                    stack.append(node)
    return result

loop.append(dfs(graph,0))
loop


Output:

[[0, 2, 3, 1]]


res = []
def pair_consecutive_elements(lst):
    result = [[lst[i], lst[i + 1]] for i in range(len(lst) - 1)]
    return result
for i in loop:
    res.append(pair_consecutive_elements(i))

res

Output:

[[[0, 2], [2, 3], [3, 1]]]



About the Author



Silan Software is one of the India's leading provider of offline & online training for Java, Python, AI (Machine Learning, Deep Learning), Data Science, Software Development & many more emerging Technologies.

We provide Academic Training || Industrial Training || Corporate Training || Internship || Java || Python || AI using Python || Data Science etc





 PreviousNext