Interview site: three kinds of questions

A topological sort

In graph theory , A topological sort （Topological Sorting） It's a directed acyclic graph （DAG, Directed Acyclic Graph） The linear sequence of all vertices of . And the sequence must satisfy the following two conditions ：

• Every vertex appears and only once .
• If there is one from the top A To the top B The path of , So the vertices in the sequence A Appear at the top B In front of .

Directed acyclic graph （DAG） There's topology sort , Not DAG Graph has no topological ordering .

Topological sort is usually used to “ Sort ” Tasks with dependencies .

Python Realization

#  Input top Any path of sorting , Used to judge whether a directed graph has rings 
def topSort(n, path):
    """
    DAG Topological ordering of Graphs 
    n: Number of nodes 
    path:  Edge in the picture 
    """
    
    #  Count who is the outgoing node of each node 
    graph = {}
    #  Count the input degree of each node 
    in_dgree = {i:0 for i in range(n)}

    for i, j in path:
        if i in graph:
            graph[i].append(j)
        else:
            graph[i] = [j]
        in_dgree[j] += 1

    #  Set the stack to store the input degree as 0 The node of 
    stack = []

    #  For preservation top Results of sorting 
    res = []
    
    #  The degree of engagement is 0 The node of is pushed onto the stack 
    for t in in_dgree:
        if in_dgree[t] == 0:
            stack.append(t)

    #  In and out of the stack to achieve node input and output 
    while stack:
        m = stack.pop()
        res.append(m)
        if m in graph:
            for k in graph[m]:
                in_dgree[k] -= 1
                if in_dgree[k] == 0:
                    stack.append(k)
    if len(res) == n:
        return res
    return []

path = [(0,3), (0,1), (1,3), (1,2), (2,4), (3,2), (3,4)]
n = 5
rt = topSort(n, path)
print(rt)

The shortest path of a single source node

Introduce :  Algorithm ： utilize Dijkstra The algorithm solves the shortest path from Beijing to Hainan _& Eternal Galaxy & The blog of -CSDN Blog

python Realization

def shortestPath(path, n):
    """
    path: (start, end, weight)
    n:  Number of nodes 
    """
    #  Store the shortest path from the source node to other nodes and the current parent node (parent, distance)
    dst = [(-1, float("inf")) for _ in range(n)]

    #  Set whether the node has been accessed 
    visited = [False for _ in range(n)]

    #  Use adjacency matrix to store graph 
    graph = [[float("inf") for _ in range(n)] for _ in range(n)]

    for i, j, w in path:
        graph[i][j] = w

    #  Used to save the parent node of each node 
    parent = [-1 for _ in range(n)]


    #  Calculate the shortest path from the source node to other nodes 
    for i in range(1, n):
        if graph[0][i] != float("inf"):
            dst[i] = (0, graph[0][i])

    visited[0] = True

    #  Find the shortest path 
    for _ in range(n):
        middle = -1
        mindst = float("inf")
        cur_parent = -1
        #  solve dst Medium minimum distance 
        for i in range(n):
            if not visited[i] and dst[i][1] != float("inf"):
                if dst[i][1] < mindst:
                    mindst = dst[i][1]
                    middle = i
                    cur_parent = dst[i][0]

        if cur_parent != -1:
            visited[middle] = True
            parent[middle] = cur_parent
            #  to update dst middle distance 
            for i in range(n):
                if not visited[i] and graph[middle][i] != float("inf"):
                    if dst[middle][1] + graph[middle][i] < dst[i][1]:
                        dst[i] = (middle, dst[middle][1] + graph[middle][i])

    #  Go back 
    for i in range(1, n):
        k = i
        path = [k]
        while parent[k] != -1:
            path.insert(0, parent[k])
            k = parent[k]
        print("path:{}, dst={}".format(path, dst[i][1]))

# 0-1-3
# 0-2-3
#   1-2

path = [(0,1,2),(0,2,1),(2,3,6),(1,3,4),(1,2,4)]
n = 4
shortestPath(path, n)

Depth first traversal of graphs

python Realization

 

def graphDFSTravel(path, n, start_node):
    """
     Depth first traversal algorithm of graph ( Adjacency matrix is used for storage )
    path:  Store the edges in the graph 
    n:  Number of nodes 
    start_node:  Start node 
    """
    visited = [False for _ in range(n)]
    res = []

    #  Use adjacency matrix to store graph 
    graph = [[float("inf") for _ in range(n)] for _ in range(n)]
    for i, j in path:
        graph[i][j] = 1
        graph[j][i] = 1

    #  Store traversal results 
    res = []

    #  Depth first traversal node 
    def dfs(i):
        if i >= 0 and i < n and not visited[i]:
            res.append(i)
            visited[i] = True
            for k in range(n):
                if float(graph[i][k]) != float('inf'):
                    dfs(k)
    dfs(start_node)
    return res

path = [(0,1),(0,4),(1,3),(0,2)]
n = 5
res = graphDFSTravel(path, n, 0)
print(res)