Understanding Graphs in Data Structures

Sep 11, 2024

Review flashcards

Introduction to Graphs in Data Structures

Overview

  • Graphs are a type of non-linear data structure.
  • Consists of vertices (nodes) and edges (connections).

Key Concepts

  • Vertices: Nodes in a graph.
  • Edges: Connections between vertices.
  • Graph Representation:
    • Set of vertices and edges.

Terminologies

  • Adjacent Vertices: Vertices connected directly by an edge.
  • Adjacent Edges: Edges with a common vertex.
  • Degree: Number of vertices adjacent to a vertex.
  • Path: Sequence of vertices where consecutive vertices are adjacent.
  • Cycle: Path with the first and last vertices being the same.
  • Walk: Sequence of vertices and edges to traverse from one vertex to another.

Types of Graphs

Finite Graph

  • Finite number of vertices and edges.

Infinite Graph

  • Infinite number of vertices and edges.

Trivial Graph

  • Only one vertex, no edges.

Simple Graph

  • One edge between each vertex.

Multi Graph

  • Multiple edges between a pair of vertices.

Null Graph

  • Multiple vertices, no edges.

Complete Graph

  • Each vertex connected with all other vertices.

Pseudograph

  • Contains at least one self-loop.

Directed Graph

  • Edges with direction.

Regular Graph

  • All vertices have the same degree.

Weighted Graph

  • Edges have weights representing traversal cost.

Connected Graph

  • All pairs of vertices are connected.

Disconnected Graph

  • Not all pairs of vertices are connected.

Cyclic Graph

  • Contains at least one cycle.

Acyclic Graph

  • No cycles.

Graph Representation Methods

Adjacency Matrix

  • Sequential representation.
  • Uses 0s and 1s or weights for connections.
  • Undirected Graphs: Non-directional connections.
  • Directed Graphs: Directional connections.

Adjacency List

  • Linked representation.
  • List of neighbors for each vertex.
  • Directed Graphs: Implemented using linked lists or arrays.

Graph Traversal

Methods

Breadth First Search (BFS)

  • Starts at root node, explores neighbors.
  • Uses queue data structure.

Depth First Search (DFS)

  • Goes deep, backtracks from dead ends.
  • Uses stack data structure.

Applications of Graphs

  • Websites (e.g., Google Maps).
  • Social Media (e.g., Facebook).
  • Security Systems.
  • Software Programming.

Conclusion

  • Graphs are essential in various applications and understanding their structure is crucial in data structures.