Graph

Graph

A graph is a non-linear data structure that consists of a set of vertices (nodes) and a set of edges that connect these vertices. Graphs are widely used to model real-world problems such as social networks, maps, computer networks, and more.

Key Components of a Graph

1. Vertices (Nodes):
   • Represent entities or objects (e.g., people, cities, computers).
   • Also called nodes.
2. Edges:
   • Represent relationships or connections between vertices.
   • Can be directed (one-way) or undirected (two-way).
3. Weight (optional):
   • A value assigned to an edge, representing the cost, distance, or strength of the relationship.

Types of Graphs

1. Directed Graph (Digraph):
   • Edges have a direction (e.g., A → B).
   • Represents one-way relationships (e.g., web page links).
2. Undirected Graph:
   • Edges have no direction (e.g., A — B).
   • Represents two-way relationships (e.g., friendships in a social network).
3. Weighted Graph:
   • Edges have weights (e.g., A —(5)— B).
   • Represents relationships with associated costs (e.g., distances between cities).
4. Unweighted Graph:
   • Edges have no weights (e.g., A — B).
   • Represents relationships without associated costs.
5. Cyclic Graph:
   • Contains at least one cycle (a path that starts and ends at the same vertex).
6. Acyclic Graph:
   • Contains no cycles (e.g., trees are acyclic graphs).
7. Connected Graph:
   • There is a path between every pair of vertices.
8. Disconnected Graph:
   • Some vertices are not connected to others.

Graph Representation

Graphs can be represented in two main ways:

1. Adjacency Matrix

• A 2D array of size V x V (where V is the number of vertices).
• matrix[i][j] = 1 if there is an edge between vertex i and vertex j; otherwise, 0.
• For weighted graphs, matrix[i][j] stores the weight of the edge.
• Example

    A  B  C
A   0  1  0
B   1  0  1
C   0  1  0

Represents an undirected graph with edges: A — B and B — C.

Pros:

• Easy to implement.
• Efficient for dense graphs (many edges).

Cons:

• Consumes more space (O(V^2)).
• Inefficient for sparse graphs (few edges).

2. Adjacency List

• An array of lists (or linked lists).
• Each vertex has a list of its adjacent vertices.

Example:

A -> B
B -> A -> C
C -> B

Represents the same undirected graph as above.

Pros:

• Space-efficient for sparse graphs (O(V + E)).
• Easy to traverse neighbors of a vertex.

Cons:

• Slightly more complex to implement.
• Less efficient for dense graphs.

Graph Traversal Algorithms

1. Depth-First Search (DFS):
   • Explores as far as possible along each branch before backtracking.
   • Uses a stack (or recursion) to keep track of vertices to visit.
2. Breadth-First Search (BFS):
   • Explores all neighbors at the present depth before moving to the next level.
   • Uses a queue to keep track of vertices to visit.

Common Graph Algorithms

1. Shortest Path:
   • Finds the shortest path between two vertices.
   • Algorithms: Dijkstra’s (for weighted graphs), Bellman-Ford (for graphs with negative weights), Floyd-Warshall (for all pairs).
2. Minimum Spanning Tree (MST):
   • Finds a subset of edges that connects all vertices with the minimum total edge weight.
   • Algorithms: Kruskal’s, Prim’s.
3. Topological Sorting:
   • Orders vertices in a directed acyclic graph (DAG) such that for every directed edge u → v, u comes before v.
4. Cycle Detection:
   • Detects if a graph contains a cycle.
   • Algorithms: DFS, Union-Find.
5. Strongly Connected Components (SCC):
   • Finds subsets of vertices where every vertex is reachable from every other vertex in the subset.
   • Algorithm: Kosaraju’s, Tarjan’s.

Applications of Graphs

1. Social Networks:
   • Vertices represent users, and edges represent friendships.
2. Maps and Navigation:
   • Vertices represent locations, and edges represent roads with weights as distances.
3. Computer Networks:
   • Vertices represent devices, and edges represent connections.
4. Recommendation Systems:
   • Vertices represent products or users, and edges represent interactions or preferences.
5. Dependency Resolution:
   • Vertices represent tasks, and edges represent dependencies (e.g., in project management).

Example: Graph Representation in Code

Adjacency List Representation

#include <stdio.h>
#include <stdlib.h>

// Structure for a node in the adjacency list
struct Node {
    int vertex;
    struct Node* next;
};

// Structure for the graph
struct Graph {
    int numVertices;
    struct Node** adjLists;
};

// Function to create a new node
struct Node* createNode(int v) {
    struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
    newNode->vertex = v;
    newNode->next = NULL;
    return newNode;
}

// Function to create a graph
struct Graph* createGraph(int vertices) {
    struct Graph* graph = (struct Graph*)malloc(sizeof(struct Graph));
    graph->numVertices = vertices;
    graph->adjLists = (struct Node**)malloc(vertices * sizeof(struct Node*));

    for (int i = 0; i < vertices; i++) {
        graph->adjLists[i] = NULL;
    }

    return graph;
}

// Function to add an edge to the graph
void addEdge(struct Graph* graph, int src, int dest) {
    // Add edge from src to dest
    struct Node* newNode = createNode(dest);
    newNode->next = graph->adjLists[src];
    graph->adjLists[src] = newNode;

    // For undirected graphs, add edge from dest to src
    newNode = createNode(src);
    newNode->next = graph->adjLists[dest];
    graph->adjLists[dest] = newNode;
}

// Function to print the graph
void printGraph(struct Graph* graph) {
    for (int i = 0; i < graph->numVertices; i++) {
        struct Node* temp = graph->adjLists[i];
        printf("Vertex %d: ", i);
        while (temp) {
            printf("%d -> ", temp->vertex);
            temp = temp->next;
        }
        printf("NULL\n");
    }
}

int main() {
    struct Graph* graph = createGraph(5);

    addEdge(graph, 0, 1);
    addEdge(graph, 0, 2);
    addEdge(graph, 1, 3);
    addEdge(graph, 2, 4);

    printGraph(graph);

    return 0;
}

Output:

Vertex 0: 2 -> 1 -> NULL
Vertex 1: 3 -> 0 -> NULL
Vertex 2: 4 -> 0 -> NULL
Vertex 3: 1 -> NULL
Vertex 4: 2 -> NULL

Code Explanation

1. Node Structure (Linked List)

struct Node {
    int vertex;
    struct Node* next;
};

Represents a node in the adjacency list. Each node contains:

• vertex → Stores the vertex number.
• next → Pointer to the next adjacent vertex (linked list structure).

2. Graph Structure

struct Graph {
    int numVertices;
    struct Node** adjLists;
};

Represents the graph. Contains:

• numVertices → Stores the total number of vertices.
• adjLists → An array of linked lists, where each index represents a vertex and stores a pointer to its adjacency list.

3. Creating a New Node

struct Node* createNode(int v) {
    struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
    newNode->vertex = v;
    newNode->next = NULL;
    return newNode;
}

• Dynamically allocates memory for a new node.
• Sets the vertex value and initializes next to NULL.

4. Creating the Graph

struct Graph* createGraph(int vertices) {
    struct Graph* graph = (struct Graph*)malloc(sizeof(struct Graph));
    graph->numVertices = vertices;
    graph->adjLists = (struct Node**)malloc(vertices * sizeof(struct Node*));

    for (int i = 0; i < vertices; i++) {
        graph->adjLists[i] = NULL;
    }

    return graph;
}

• Allocates memory for the graph.
• Initializes the adjacency list array with NULL (empty list for each vertex).

5. Adding an Edge (Undirected Graph)

void addEdge(struct Graph* graph, int src, int dest) {
    struct Node* newNode = createNode(dest);
    newNode->next = graph->adjLists[src];
    graph->adjLists[src] = newNode;

    newNode = createNode(src);
    newNode->next = graph->adjLists[dest];
    graph->adjLists[dest] = newNode;
}

• Adds an edge between src and dest.
• Since the graph is undirected, we add:
  • dest to the adjacency list of src.
  • src to the adjacency list of dest.

6. Printing the Graph

void printGraph(struct Graph* graph) {
    for (int i = 0; i < graph->numVertices; i++) {
        struct Node* temp = graph->adjLists[i];
        printf("Vertex %d: ", i);
        while (temp) {
            printf("%d -> ", temp->vertex);
            temp = temp->next;
        }
        printf("NULL\n");
    }
}

• Loops through each vertex and prints its adjacency list.

7. Main Function

int main() {
    struct Graph* graph = createGraph(5);

    addEdge(graph, 0, 1);
    addEdge(graph, 0, 2);
    addEdge(graph, 1, 3);
    addEdge(graph, 2, 4);

    printGraph(graph);

    return 0;
}

• Creates a graph with 5 vertices.
• Adds edges

0 - 1
0 - 2
1 - 3
2 - 4

• Prints the adjacency list representation of the graph.

Key Points

• Graphs are versatile data structures used to model relationships between entities.
• They can be represented using adjacency matrices or adjacency lists.
• Common algorithms include DFS, BFS, shortest path, and MST.
• Graphs have applications in social networks, maps, computer networks, and more.