The Essentials of Graphs

A graph is a non-linear data structure that represents relationships between entities. It consists of:

• Vertices (nodes) – the entities.
• Edges (connections) – the relationships between them.

Types of Graphs

• Directed vs Undirected:
• Weighted vs Unweighted:
• Cyclic vs Acyclic:

Real-World Uses of Graphs in Applications

• Social Networks: Users (nodes) and their relationships (edges).
• Navigation Systems: Locations (nodes), roads (edges with distance/time).
• Recommendation Engines: Products and user interests as graphs.
• Dependency Resolution: Package managers or build tools use graphs to resolve dependencies.

Java Example: Simple Graph Implementation

Here's a basic undirected, unweighted graph using an adjacency list.

import java.util.*;

class Graph {
    private Map<String, List<String>> adjList = new HashMap<>();

    // Add a vertex
    public void addVertex(String vertex) {
        adjList.putIfAbsent(vertex, new ArrayList<>());
    }

    // Add an edge (undirected)
    public void addEdge(String src, String dest) {
        adjList.get(src).add(dest);
        adjList.get(dest).add(src);
    }

    // Print graph
    public void printGraph() {
        for (String vertex : adjList.keySet()) {
            System.out.println(vertex + " -> " + adjList.get(vertex));
        }
    }
}

public class Main {
    public static void main(String[] args) {
        Graph g = new Graph();
        g.addVertex("A");
        g.addVertex("B");
        g.addVertex("C");

        g.addEdge("A", "B");
        g.addEdge("A", "C");
        g.addEdge("B", "C");

        g.printGraph();
    }
}        

OUTPUT:
A -> [B, C]
B -> [A, C]
C -> [A, B]
        

Example Use Case: Social Network Friend Suggestion

• Nodes: Users
• Edges: Friend connections
• Suggest friends by finding friends of friends (2-level depth search).