Graph Algorithms

Number of Islands or Clusters

Graph algorithms[edit]

Further information: Graph theory and Category:Graph algorithms

• Coloring algorithm: Graph coloring algorithm.
• Hopcroft–Karp algorithm: convert a bipartite graph to a maximum cardinality matching
• Hungarian algorithm: algorithm for finding a perfect matching
• Prüfer coding: conversion between a labeled tree and its Prüfer sequence
• Tarjan's off-line least common ancestors algorithm: compute lowest common ancestors for pairs of nodes in a tree
• Topological sort: finds linear order of nodes (e.g. jobs) based on their dependencies.

Graph drawing[edit]

Further information: Graph drawing

• Force-based algorithms (also known as force-directed algorithms or spring-based algorithm)
• Spectral layout

Network theory[edit]

Further information: Network theory

• Network analysis
  • Link analysis
    • Girvan–Newman algorithm: detect communities in complex systems
    • Web link analysis
      • Hyperlink-Induced Topic Search (HITS) (also known as Hubs and authorities)
      • PageRank
      • TrustRank
• Flow networks
  • Dinic's algorithm: is a strongly polynomial algorithm for computing the maximum flow in a flow network.
  • Edmonds–Karp algorithm: implementation of Ford–Fulkerson
  • Ford–Fulkerson algorithm: computes the maximum flow in a graph
  • Karger's algorithm: a Monte Carlo method to compute the minimum cut of a connected graph
  • Push–relabel algorithm: computes a maximum flow in a graph

Routing for graphs[edit]

• Edmonds's algorithm (also known as Chu–Liu/Edmonds's algorithm): find maximum or minimum branchings
• Euclidean minimum spanning tree: algorithms for computing the minimum spanning tree of a set of points in the plane
• Euclidean shortest path problem: find the shortest path between two points that does not intersect any obstacle
• Longest path problem: find a simple path of maximum length in a given graph
• Minimum spanning tree
  • Borůvka's algorithm
  • Kruskal's algorithm
  • Prim's algorithm
  • Reverse-delete algorithm
• Nonblocking Minimal Spanning Switch say, for a telephone exchange
• Shortest path problem
  • Bellman–Ford algorithm: computes shortest paths in a weighted graph (where some of the edge weights may be negative)
  • Dijkstra's algorithm: computes shortest paths in a graph with non-negative edge weights
  • Floyd–Warshall algorithm: solves the all pairs shortest path problem in a weighted, directed graph
  • Johnson algorithm: All pairs shortest path algorithm in sparse weighted directed graph
• Transitive closure problem: find the transitive closure of a given binary relation
• Traveling salesman problem
  • Christofides algorithm
  • Nearest neighbour algorithm
• Warnsdorff's algorithm: A heuristic method for solving the Knight's Tour problem.

Graph search[edit]

Further information: State space search and Graph search algorithm

• A*: special case of best-first search that uses heuristics to improve speed
• B*: a best-first graph search algorithm that finds the least-cost path from a given initial node to any goal node (out of one or more possible goals)
• Backtracking: abandons partial solutions when they are found not to satisfy a complete solution
• Beam search: is a heuristic search algorithm that is an optimization of best-first search that reduces its memory requirement
• Beam stack search: integrates backtracking with beam search
• Best-first search: traverses a graph in the order of likely importance using a priority queue
• Bidirectional search: find the shortest path from an initial vertex to a goal vertex in a directed graph
• Bloom filter: a constant time and memory check to see whether a given element exists in a set. May return a false positive, but never a false negative.
• Breadth-first search: traverses a graph level by level
• Brute-force search: An exhaustive and reliable search method, but computationally inefficient in many applications.
• D*: an incremental heuristic search algorithm
• Depth-first search: traverses a graph branch by branch
• Dijkstra's algorithm: A special case of A* for which no heuristic function is used
• General Problem Solver: a seminal theorem-proving algorithm intended to work as a universal problem solver machine.
• Iterative deepening depth-first search (IDDFS): a state space search strategy
• Jump point search: An optimization to A* which may reduce computation time by an order of magnitude using further heuristics.
• Lexicographic breadth-first search (also known as Lex-BFS): a linear time algorithm for ordering the vertices of a graph
• Uniform-cost search: a tree search that finds the lowest cost route where costs vary
• SSS*: state space search traversing a game tree in a best-first fashion similar to that of the A* search algorithm

Subgraphs[edit]

• Cliques
  • Bron–Kerbosch algorithm: a technique for finding maximal cliques in an undirected graph
  • MaxCliqueDyn maximum clique algorithm: find a maximum clique in an undirected graph
• Strongly connected components
• Path-based strong component algorithm
• Kosaraju's algorithm
• Tarjan's strongly connected components algorithm

-->

find LCA in directed acyclic graph 

-->

class Node {

int label;

List neighbors;

Node(int x) {

label = x;

neighbors = new ArrayList<>();

}

}

public List findLCAINDAG(Node, graph, Node n1, Node n2)