Graph Terminology (Vertex, Edge, Directed, Weighted)

Introduction to Graphs: Essential Terminology

Welcome to the fascinating world of Graphs! Unlike the linear data structures we've covered (Arrays, Linked Lists, Stacks, Queues) and the hierarchical structure of Trees, Graphs are a more general-purpose data structure that can represent complex relationships and networks. They are incredibly versatile and are used to model everything from social networks and road maps to computer networks and dependencies in project management.

---

1. What is a Graph?

At its core, a graph is a non-linear data structure consisting of two main components:

• Vertices (Nodes): These are the fundamental entities or points in the graph. They represent objects, locations, people, or any item you want to model.
• Edges: These are the connections or relationships between vertices. An edge indicates that there is a direct link or interaction between two vertices.

Think of a social network:

• Vertices: Each person in the network is a vertex.
• Edges: A "friendship" or "connection" between two people is an edge.

---

2. Key Graph Terminology

To effectively discuss and work with graphs, it's important to understand the standard terminology:

• Directed vs. Undirected Graphs:

  • Undirected Graph: Edges have no direction. If an edge connects vertex A and vertex B, it means the relationship is bidirectional (you can go from A to B, and from B to A). Example: Facebook friendships.
  • Directed Graph (Digraph): Edges have a specific direction. An edge from A to B means you can go from A to B, but not necessarily from B to A. Example: Twitter followers (A follows B, but B might not follow A back).

• Weighted vs. Unweighted Graphs:

  • Unweighted Graph: All edges are considered equal; there's no cost or value associated with traversing an edge. Example: A simple map showing connections between cities.
  • Weighted Graph: Each edge has a numerical value (weight or cost) associated with it. This weight can represent distance, time, cost, capacity, etc. Example: A road map where edge weights are distances between cities.

• Adjacent Vertices: Two vertices are adjacent if they are directly connected by an edge.

• Degree of a Vertex:

  • Undirected Graph: The number of edges connected to a vertex.
  • Directed Graph:
    • In-degree: The number of incoming edges to a vertex.
    • Out-degree: The number of outgoing edges from a vertex.

• Path: A sequence of vertices connected by edges. The length of a path is the number of edges it contains.

• Cycle: A path that starts and ends at the same vertex, with no repeated edges or intermediate vertices.

• Connected Graph (Undirected): A graph where there is a path between every pair of vertices.

• Strongly Connected Graph (Directed): A directed graph where there is a path from every vertex to every other vertex.

---

3. Graph Representations

Choosing the right way to store a graph in memory is crucial as it significantly impacts the performance of graph algorithms. The choice depends on the graph's properties (like density) and the operations you need to perform.

3.1. Adjacency Matrix

• Concept: An N x N matrix (where N is the number of vertices) where matrix[i][j] stores information about the edge from vertex i to vertex j. For unweighted graphs, this could be 1 (or true) if an edge exists and 0 (or false) otherwise. For weighted graphs, it stores the weight of the edge (or infinity if no edge exists).

• Time Complexity:

  • Add Edge: O(1)
  • Check for Edge: O(1)
  • Iterate Neighbors of a Vertex: O(N)

• Space Complexity: O(N^2)

• Use Cases: Best for dense graphs (where the number of edges is close to N^2), or when you need to check for the existence of an edge in constant time. Algorithms like Floyd-Warshall are a good fit.

3.2. Adjacency List

• Concept: An array (or map) of lists, where each index i corresponds to a vertex and the list at that index contains all the vertices adjacent to vertex i. For weighted graphs, the list can store pairs of [neighbor, weight].

• Time Complexity:

  • Add Edge: O(1) (on average)
  • Check for Edge: O(degree(u)), where degree(u) is the number of neighbors of vertex u.
  • Iterate Neighbors of a Vertex: O(degree(u))

• Space Complexity: O(N + M), where N is the number of vertices and M is the number of edges.

• Use Cases: Excellent for sparse graphs (where M is much smaller than N^2). Most common graph algorithms like Breadth-First Search (BFS) and Depth-First Search (DFS) run more efficiently with adjacency lists.

3.3. Edge List

• Concept: A simple list of all the edges in the graph. Each element in the list is a pair (for unweighted graphs) or a triplet (for weighted graphs) representing an edge (u, v, weight).

• Time Complexity:

  • Add Edge: O(1)
  • Check for Edge: O(M)
  • Iterate Neighbors of a Vertex: O(M)

• Space Complexity: O(M)

• Use Cases: Useful when you need to iterate over all edges, or for certain algorithms like Kruskal's for finding Minimum Spanning Trees, where sorting edges by weight is the main operation.

---

Key Takeaway: Graphs are powerful data structures for modeling relationships. Understanding fundamental terms like vertices, edges, and the distinctions between directed/undirected and weighted/unweighted graphs is crucial. The choice of representation—Adjacency Matrix for dense graphs, Adjacency List for sparse graphs, or Edge List for edge-centric operations—is a fundamental design decision that affects algorithm efficiency.