Skip to main content

Graph Fundamentals

Essential concepts and representations for working with graph data structures.

Graph representation (adjacency list, matrix)​

  • Adjacency List: List of lists for each vertex
  • Adjacency Matrix: 2D array representation
  • Edge List: List of edges with weights
  • Incidence Matrix: Matrix for vertices and edges

Graph terminology​

  • Vertex/Node: Individual element in graph
  • Edge: Connection between two vertices
  • Weight: Cost or value associated with edge
  • Path: Sequence of vertices connected by edges
  • Cycle: Path that starts and ends at same vertex

Graph traversal (DFS, BFS)​

  • Depth-First Search (DFS): Explore as far as possible before backtracking
  • Breadth-First Search (BFS): Explore all neighbors before moving to next level
  • Recursive DFS: Using recursion for depth-first traversal
  • Iterative DFS: Using stack for depth-first traversal

Connected components​

  • Connected Graph: Path exists between any two vertices
  • Disconnected Graph: Some vertices are not reachable
  • Strongly Connected: Directed graph where all vertices are reachable
  • Weakly Connected: Undirected version is connected

Graph properties​

  • Directed vs Undirected: Direction of edges matters
  • Weighted vs Unweighted: Edges have weights or not
  • Cyclic vs Acyclic: Contains cycles or not
  • Dense vs Sparse: Many or few edges relative to vertices