Keywords for Graph Algorithms

Core Graph Concepts

  • Graph Theory
  • Vertices (Nodes)
  • Edges (Arcs)
  • Directed Graph (Digraph)
  • Undirected Graph
  • Weighted Graph
  • Unweighted Graph
  • Cyclic Graph
  • Acyclic Graph
  • Simple Graph
  • Multigraph
  • Self-Loop
  • Parallel Edges
  • Graph Density
  • Graph Connectivity
  • Graph Isomorphism
  • Subgraph
  • Spanning Subgraph

Graph Representations

  • Adjacency Matrix
  • Adjacency List
  • Edge List
  • Incidence Matrix
  • Compressed Sparse Row (CSR)
  • Forward Star Structure
  • Nested Dissection
  • Graph Visualization
  • NetworkX
  • igraph
  • Graph Database
  • Edge Properties
  • Vertex Properties

Graph Traversal

  • Breadth-First Search (BFS)
  • Depth-First Search (DFS)
  • Iterative Deepening DFS
  • Bidirectional Search
  • Level Order Traversal
  • Preorder Traversal
  • Postorder Traversal
  • Inorder Traversal
  • Tree Traversal
  • Graph Cycle Detection
  • Connected Components
  • Strongly Connected Components
  • Bridge Detection
  • Articulation Points
  • Topological Order

Shortest Path Algorithms

  • Dijkstra's Algorithm
  • Bellman-Ford Algorithm
  • A* Search Algorithm
  • Floyd-Warshall Algorithm
  • Johnson's Algorithm
  • Single-Source Shortest Path
  • All-Pairs Shortest Path
  • Shortest Path Tree
  • Path Reconstruction
  • Negative Weight Edges
  • Negative Cycles
  • Heuristic Function
  • Priority Queue Optimization
  • Potential Function
  • Reduced Costs

Minimum Spanning Tree (MST)

  • Kruskal's Algorithm
  • Prim's Algorithm
  • Borůvka's Algorithm
  • Reverse-Delete Algorithm
  • Spanning Tree
  • Minimum Spanning Forest
  • Cut Property
  • Cycle Property
  • Edge Weight
  • Union-Find Data Structure
  • Disjoint Set Union (DSU)
  • Kruskal's Sorting
  • Prim's Priority Queue
  • MST Verification

Network Flow Algorithms

  • Maximum Flow
  • Ford-Fulkerson Method
  • Edmonds-Karp Algorithm
  • Dinic's Algorithm
  • Push-Relabel Algorithm
  • Goldberg-Tarjan Algorithm
  • Residual Graph
  • Residual Capacity
  • Augmenting Path
  • Cut Capacity
  • Min-Cut Max-Flow Theorem
  • Flow Network
  • Source and Sink
  • Capacity Constraints
  • Flow Conservation
  • Blocking Flow
  • Level Graph

Python Implementation

  • Python Algorithms
  • collections.deque (BFS Queue)
  • recursion (DFS)
  • heapq (Priority Queue)
  • itertools
  • functools.lru_cache
  • NetworkX Library
  • adjacency_list creation
  • adjacency_matrix creation
  • Graph Class Implementation
  • Vertex Class
  • Edge Class
  • Graph Iteration
  • Neighborhood Iteration
  • Degree Calculation

Applications

  • Social Network Analysis
  • Web Page Ranking
  • Route Planning
  • Network Routing
  • Circuit Design
  • Compiler Design (Control Flow)
  • Database Query Optimization
  • Recommendation Systems
  • Fraud Detection
  • Biology (Protein Interactions)
  • Transportation Networks
  • Communication Networks
  • Resource Allocation
  • Game Theory (Game Graphs)
  • Puzzle Solving (Sliding Puzzles)
  • Maze Solving
  • Image Segmentation
Reload?