Skip to content

Algorithms realted to Graphs

Shortest Path Problem

  • Find the shortest path from node A to node B in the given graph.
  • Find shortest path from node A to all other nodes

  • Dijkstra Algorithm

  • Bellman's Ford Algorithm

Shortest Path Problem for all node

  • Determine the shortest paths from node A to all other nodes in the graph.
  • Find shortest path from all node to all other nodes

  • Floyd Warshall

  • Johnson's Algorithm

Hamiltonian Cycle

  • Determine if a path exists that visists each city once.

Traveling Salesman Problem (TSP)

  • What is the shortest path that visits all nodes in the graph exactly once and returns to the starting node?
  • Determine the shotest path of a hamiltoninan cycle.

Minimum Spanning Tree

  • Find the minimum spanning tree of the given graph.
  • Kruskal Algorithm
  • Prim algorithms
  • Brovuka'a Algorithm

Connectivity Testing

  • Is the graph connected, or are there disconnected components?

  • Kosaraju's algorithm

  • Tarjans Algorithm

Cycle Detection

  • Does the graph contain any cycles?

Graph Coloring

  • What is the minimum number of colors required to color the nodes of the graph such that no two adjacent nodes have the same color?

Bipartite Graph Detection

  • Is the given graph bipartite?

Eulerian Path/Circuit

  • Does the graph contain an Eulerian path or circuit?

Planarity Testing

  • Is the graph planar, meaning it can be drawn on a plane without any edge crossings?

Graph Diameter

  • What is the diameter of the graph, i.e., the longest shortest path between any two nodes?

Centrality Measures

  • Which node is the most central in the graph according to the betweenness centrality?