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?