Class GraphAlgorithms

java.lang.Object

org.episteme.core.mathematics.discrete.GraphAlgorithms

public class GraphAlgorithms
extends Object

Graph algorithms including traversal, shortest paths, and connectivity.

Implements classic graph algorithms for analyzing graph structures and finding optimal paths.

References

• Edsger W. Dijkstra, "A Note on Two Problems in Connexion with Graphs", Numerische Mathematik, Vol. 1, 1959, pp. 269-271
• Thomas H. Cormen et al., "Introduction to Algorithms", 3rd Edition, MIT Press, 2009 (comprehensive coverage of graph algorithms)

Since:

1.0

Author:

Silvere Martin-Michiellot, Gemini AI (Google DeepMind)

Constructor Summary

Constructors

Constructor	Description
GraphAlgorithms()

Method Summary

Modifier and Type	Method	Description
static <V> List<V>	breadthFirstSearch(Graph<V> graph, V start)	Performs breadth-first search from a starting vertex.
static <V> List<V>	depthFirstSearch(Graph<V> graph, V start)	Performs depth-first search from a starting vertex.
static <V> boolean	isConnected(Graph<V> graph)	Checks if the graph is connected (for undirected graphs).
static <V> List<V>	shortestPath(Graph<V> graph, V start, V end)	Finds shortest path using Dijkstra's algorithm (unweighted = BFS).

Methods inherited from class Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Constructor Details

GraphAlgorithms

public GraphAlgorithms()

Method Details

breadthFirstSearch

public static <V> List<V> breadthFirstSearch(Graph<V> graph,
 V start)

Performs breadth-first search from a starting vertex.

Type Parameters:

V - vertex type

Parameters:

graph - the graph

start - starting vertex

Returns:

list of vertices in BFS order

depthFirstSearch

public static <V> List<V> depthFirstSearch(Graph<V> graph,
 V start)

Performs depth-first search from a starting vertex.

Type Parameters:

V - vertex type

Parameters:

graph - the graph

start - starting vertex

Returns:

list of vertices in DFS order

isConnected

public static <V> boolean isConnected(Graph<V> graph)

Checks if the graph is connected (for undirected graphs).

Type Parameters:

V - vertex type

Parameters:

graph - the graph

Returns:

true if connected

shortestPath

public static <V> List<V> shortestPath(Graph<V> graph,
 V start,
 V end)

Finds shortest path using Dijkstra's algorithm (unweighted = BFS).

Type Parameters:

V - vertex type

Parameters:

graph - the graph

start - starting vertex

end - ending vertex

Returns:

shortest path or empty list if no path exists