Graph

class GraphNode:
    def __init__(self, val):
        self.val = val
        self.neighbors = []

BFS

def traverse(graph):
    visited = set()

    def bfs(node):
        if node in visited:
            return
        visited.add(node)
        queue = [node]
        while queue:
            next_queue = []
            for cur in queue:
                for neighbor in cur.neighbors:
                    if neighbor not in visited:
                        visited.add(neighbor)
                        next_queue.append(neighbor)
            queue = next_queue

    for v in graph:
        bfs(v)

DFS

def traverse(graph):
    visited = set()

    def dfs(node):
        if node in visited:
            return
        visited.add(node)
        for neighbor in node.neighbors:
            dfs(neighbor)

    for v in graph:
        dfs(v)

Topological Sort - DFS

def topological_order(graph):
    order = []
    cycle = []
    visited = set()
    visiting = set()

    def dfs(node):
        if cycle or (node in visited):
            return
        if node in visiting:
            cycle.append(1)
            return
        visiting.add(node)
        for neighbor in node.neighbors:
            dfs(neighbor)
        visiting.remove(node)
        visited.add(node)
        order.append(node)

    for v in graph:
        dfs(v)

    if cycle:
        return []

    order.reverse()
    return order

Problems

results matching ""

    No results matching ""