Search Algorihtm

DFS

void DFS(const vector<vector<int>>& G, int u, vector<int>& depth, vector<int>& parent) {
    for (int v : G[u]) {
        if (depth[v] == INT_MAX) {
            depth[v] = depth[u] + 1;
            parent[v] = u;
            DFS(G, v, depth, parent);
        }
    }
}

void DFS_Main(const vector<vector<int>>& G, int s) {
    vector<int> depth(G.size(), INT_MAX);
    vector<int> parent(G.size(), -1);
    depth[s] = 0;
    DFS(G, s, depth, parent);
}

def DFS(G, u, depth, parent):
    for v in G[u]:
        if depth[v] == float('inf'):
            depth[v] = depth[u] + 1
            parent[v] = u
            DFS(G, v, depth, parent)

def DFS_Main(G, s):
    depth = {u: float('inf') for u in G}
    parent = {u: None for u in G}
    depth[s] = 0
    DFS(G, s, depth, parent)

# Example usage:
# G is the graph represented as a dictionary where keys are vertex identifiers and values are lists of adjacent vertices.
# G = {0: [1, 2], 1: [2 2: [0, 3], 3: [3]}
# DFS_Main(G, 0)

BFS

struct V {
    int d = 1e9; // Represents ∞
    V* p = nullptr;
};

void BFS(vector<vector<V*>>& g, V* s) {
    s->d = 0;
    queue<V*> q({s});
    while (!q.empty()) {
        V* u = q.front(); q.pop();
        for (V* v : g[u])
            if (v->d == 1e9) {
                v->d = u->d + 1;
                v->p = u;
                q.push(v);
            }
    }
}

from collections import deque

class V:
    def __init__(self):
        self.d = float('inf')
        self.p = None

def BFS(g, s):
    s.d = 0
    q = deque([s])
    while q:
        u = q.popleft()
        for v in g[u]:
            if v.d == float('inf'):
                v.d = u.d + 1
                v.p = u
                q.append(v)

Shortest Path Problem

• A path is a sequence of adjacent vertices
• The shortest path problem:
  • Given two vertices $s$ and $t$, find the path with the smallest distance among all paths from $s$ to $t$

Dijkstra’s Algorithm

• Solves the shortest path problem for a graph with non-negative edge path costs, producing a shortest path tree
• Requires all edge weights to be non-negative
• Employs a min-heap Q on the vertices with their d values as keys
• The set S stores the vertices whose shortest paths from s have been found
• Time complexity: $O( (|V|+|E| ) \log |V| )$

1  function Dijkstra(Graph, source):
2      dist[source] ← 0                           // Initialization
3
4      create vertex priority queue Q
5
6      for each vertex v in Graph.Vertices:
7          if v ≠ source
8              dist[v] ← INFINITY                 // Unknown distance from source to v
9              prev[v] ← UNDEFINED                // Predecessor of v
10
11         Q.add_with_priority(v, dist[v])
12
13
14     while Q is not empty:                      // The main loop
15         u ← Q.extract_min()                    // Remove and return best vertex
16         for each neighbor v of u:              // Go through all v neighbors of u
17             alt ← dist[u] + Graph.Edges(u, v)
18             if alt < dist[v]:
19                 dist[v] ← alt
20                 prev[v] ← u
21                 Q.decrease_priority(v, alt)
22
23     return dist, prev