Graphsearch

BFS

def BFS(self, s):
 
    # Mark all the vertices as not visited
    visited = [False] * (max(self.graph) + 1)

    # Create a queue for BFS
    queue = []

    # Mark the source node as 
    # visited and enqueue it
    queue.append(s)
    visited[s] = True

    while queue:

        # Dequeue a vertex from 
        # queue and print it
        s = queue.pop(0)
        print (s, end = " ")

        # Get all adjacent vertices of the
        # dequeued vertex s. If a adjacent
        # has not been visited, then mark it
        # visited and enqueue it
        for i in self.graph[s]:
            if visited[i] == False:
                queue.append(i)
                visited[i] = True
 

DFS

def DFSUtil(self, v, visited):
 
    # Mark the current node as visited
    # and print it
    visited.add(v)
    print(v, end=' ')
 
    # Recur for all the vertices
    # adjacent to this vertex
    for neighbour in self.graph[v]:
        if neighbour not in visited:
            self.DFSUtil(neighbour, visited)
 
# The function to do DFS traversal. It uses
# recursive DFSUtil()
def DFS(self, v):

    # Create a set to store visited vertices
    visited = set()

    # Call the recursive helper function
    # to print DFS traversal
    self.DFSUtil(v, visited)

最短路径算法

单点最短路径算法： bellman-ford 算法，基本思路就是每次更新从起点到v的距离，如果起点到u再到v的路程短，那么就更新。

 for i from 1 to size(vertices)-1:
       for each edge (u, v) with weight w in edges:
           if distance[u] + w < distance[v]:
               distance[v] := distance[u] + w

Dijkstra’s 算法，这也是单点最短路径算法，基本思路是每次从q中取最小的节点，之后更新从该点到其他的点的距离。

function Dijkstra(G, w, s)
    for each vertex v in V[G]        // 初始化
           d[v] := infinity           // 將各點的已知最短距離先設成無窮大
    d[s] := 0                        // 因为出发点到出发点间不需移动任何距离，所以可以直接将s到s的最小距离设为0
     S := empty set
     Q := set of all vertices
     while Q is not an empty set      // Dijkstra演算法主體
        u := Extract_Min(Q)
        S.append(u)
        for each edge outgoing from u as (u,v)
            if d[v] > d[u] + w(u,v)  // 拓展边（u,v）。w(u,v)为从u到v的路径长度。
                d[v] := d[u] + w(u,v)  // 更新路径长度到更小的那个和值。

A*

---

Backlinks

• Algo (my_note)