Depth First Search (DFS)

Depth First Search is an algorithm that could do a pre-order 202112102054# search on either 202112101956 or 202204112045.

DFS could be used for:

Details

  • If using against an #202204112129 which is not connected or #202204112118 that is not strongly connected, repeatedly call DFS on the unvisited nodes in order to visit all nodes in the graph.

Analysis

  • The work runtime complexity for it is \(O(\vert E \vert \times \vert V \vert)\). This could be improved to \(O(\vert E \vert)\) if the data structure is a 202112101956.

Attention

  • To avoid having an infinite loop, DFS must mark the visited nodes.

Implementation

void Dfs(Vertex V)
{
  Visited[V] = True;
  for each W adjacent to V
    if (!Visited[W])
      Dfs(W);
}
Links to this page
  • Maximum Flow Problem
    Dinic’s algorithm (combination of BFS and #202205021959 resulted in \(O(V^2 E)\))
  • Ford-Fulkerson Algorithm

    Assuming this algorithm be implemented in #202205021959, the time complexity will be \(O(fE)\) where \(f\) denotes the maximum flow and \(E\) denotes the number of edges. However, when meeting the worst case as shown below, if the algorithm repeatedly choosing the edge with the smallest maximum capacity (in this case, edge with a value of maximum capacity of 1), it will need 2000 steps to get the maximum flow. This turn out to be a rather poor performance.

  • Euler Path

    A graph could be determined as an Euler Path by using #202205021959. This will result in a linear runtime complexity.

  • Euler Circuit

    A graph could be determined as an Euler Circuit by using #202205021959. This will result in a linear runtime complexity.

  • Biconnectivity

    If there is a node where its removal will result in a disconnected undirected graph, that node is an articulation point for that graph. The articulation point in the graph could be found using #202205021959 alongside with spanning tree that store back edges (there is a connection between \((v,w)\) but it has been visited).

#graph #algorithm #tree