DepthFirstSearcher

java.lang.Object

dsa.lab11.exercises.DepthFirstSearcher

public class DepthFirstSearcher extends Object

Depth-first search (DFS).

Constructor Summary

Constructors

Constructor

Description

DepthFirstSearcher()
Method Summary

Modifier and Type

Method

Description

static <Vertex, Weight> DepthFirstSearchResult<Vertex>

fullSearch(DirectedGraph<Vertex,Weight> graph)

Perform full depth-first search, starting from every vertex in the graph.

static <Vertex, Weight> DepthFirstSearchResult<Vertex>

search(DirectedGraph<Vertex,Weight> graph, Vertex source)

Perform depth-first search from the given source vertex.

Methods inherited from class java.lang.Object
clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Constructor Details
- DepthFirstSearcher
  
  public DepthFirstSearcher()
Method Details
- search
  
  public static <Vertex, Weight> DepthFirstSearchResult<Vertex> search(DirectedGraph<Vertex,Weight> graph, Vertex source)
  
  Perform depth-first search from the given source vertex.
  Returns both the paths found to all reachable vertices and the order in which they were fully visited.
  
  Type Parameters:
  
  Vertex - the vertex type
  
  Weight - the weight type
  
  Parameters:
  
  graph - the graph
  
  source - the source vertex
  
  Returns:
  
  the result of the search
- fullSearch
  
  public static <Vertex, Weight> DepthFirstSearchResult<Vertex> fullSearch(DirectedGraph<Vertex,Weight> graph)
  
  Perform full depth-first search, starting from every vertex in the graph.
  Essentially runs single-source DFS from each source in turn, re-using the same paths map and visited list (to not re-visit already-visited vertices).
  
  Type Parameters:
  
  Vertex - the vertex type
  
  Weight - the weight type
  
  Parameters:
  
  graph - the graph
  
  Returns:
  
  the result of the search