Graphs

Definition

A graph is a non-linear data structure consisting of a finite set of vertices (or nodes) connected by edges (or lines). It is a mathematical structure used to model pairwise relations between objects in a network.

Main Content

1. Vertices and Edges

• A vertex (plural: vertices) represents a point or an entity in the graph, often referred to as a node.
• An edge represents the relationship or path connecting two vertices.

(A)----(B)
 A and B are vertices
 The line is the edge

2. Directed and Undirected Graphs

• An undirected graph has edges that do not have a direction; the relationship is mutual (e.g., a friendship on Facebook).
• A directed graph (or Digraph) has edges with a specific direction, represented by arrows (e.g., a Twitter follow).

Undirected: (A)--(B)
Directed:   (A)-->(B)

3. Weighted and Unweighted Graphs

• A weighted graph assigns a specific numerical value (weight) to each edge, representing cost, distance, or time.
• An unweighted graph treats all connections as equal, focusing only on the existence of a link.

Weighted: (A)--[5]--(B)
The number 5 represents the cost or distance between A and B

Working / Process

1. Representation of Graphs

• Adjacency Matrix: A 2D array of size V x V where matrix[i][j] = 1 if an edge exists between vertex i and vertex j.
• Adjacency List: An array of lists where each index represents a vertex and contains a list of its neighbors.

2. Traversal Techniques

• Breadth-First Search (BFS): Explores the graph layer by layer, starting from a chosen node, visiting all neighbors before moving deeper.
• Depth-First Search (DFS): Explores as far as possible along each branch before backtracking, using a stack-like behavior.

3. Cycle Detection

• For undirected graphs, a cycle exists if a visited node is encountered again during traversal (excluding the parent).
• For directed graphs, a cycle is detected if a node is visited that is already in the current recursion stack.

Advantages / Applications

• Social Network Analysis: Used to map connections between users, recommend friends, and analyze influence patterns.
• GPS and Navigation Systems: Algorithms like Dijkstra’s are used to find the shortest path between two locations.
• Computer Networking: Used to represent network topologies and optimize data packet routing between servers.

Summary

Graphs are versatile data structures that model complex systems by connecting nodes with edges. By defining relationships through directions and weights, graphs enable efficient pathfinding, network analysis, and data organization. Understanding traversals like BFS and DFS is essential for searching and manipulating these structures effectively.

Important terms to remember: Vertices, Edges, Weighted Graph, Adjacency Matrix, and Traversal.