A graph is a non-linear data structure that represents a set of objects (called vertices or nodes) and the connections (called edges) between them. Graphs are widely used in computer science to model and solve problems involving networks, relationships, and traversals, such as in social networks, road maps, and network routing.
Terminology in Graphs
- Vertex (Node): A fundamental unit in a graph representing an entity.
- Example: Cities in a road network.
- Edge: A connection between two vertices, representing a relationship or link.
- Example: Roads between cities.
- Degree of a Vertex:
- In-degree: Number of incoming edges to a vertex.
- Out-degree: Number of outgoing edges from a vertex.
- Path: A sequence of vertices connected by edges.
- Cycle: A path where the start and end vertices are the same.
- Connected Graph: A graph where there is a path between any two vertices.
- Weighted Graph: A graph where edges have weights (e.g., distance or cost).
- Directed Graph (Digraph): Edges have a direction (from one vertex to another).
- Undirected Graph: Edges have no direction; connections are bidirectional.
Types of Graphs
- Undirected Graph:
- Edges have no direction.
- Example: A friendship network where the connection is mutual.
- Directed Graph (Digraph):
- Edges have a direction.
- Example: Web links where one page links to another.
- Weighted Graph:
- Edges have weights representing cost, distance, or other values.
- Example: Road networks with distances as weights.
- Unweighted Graph:
- Edges do not have weights.
- Example: A basic social network graph.
- Cyclic Graph:
- Contains at least one cycle.
- Example: A road loop.
- Acyclic Graph:
- Contains no cycles.
- Example: A tree is a special type of acyclic graph.
- Complete Graph:
- Every vertex is connected to every other vertex.
- Example: A network where everyone is connected to everyone else.
Representation of Graphs
Graphs can be represented in multiple ways, depending on the requirements:
1. Adjacency Matrix
- A 2D array where the cell (i, j) indicates the presence of an edge between vertex iii and vertex jjj.
- For weighted graphs, the matrix stores weights instead of just 1 (edge) or 0 (no edge).
Example:
markdown
Copy code
Adjacency Matrix for an undirected graph:
0 1 1
1 0 1
1 1 0
2. Adjacency List
- An array of lists where each list represents the vertices connected to a specific vertex.
- Efficient in terms of space for sparse graphs.
Example:
Adjacency List:
0: 1, 2
1: 0, 2
2: 0, 1
3. Edge List
- A list of all edges in the graph.
- Each edge is represented as a pair (u, v) or triplet (u, v, w) for weighted graphs.
Example:
Edge List:
(0, 1)
(0, 2)
(1, 2)
Applications of Graphs
- Social Networks:
- Represent users as vertices and their connections as edges.
- Web Search:
- Model webpages and hyperlinks as a directed graph.
- Transportation Networks:
- Represent cities and roads for route planning.
- Computer Networks:
- Model devices and connections for network routing.
- Biology:
- Represent genetic relationships and protein interactions.
Operations on Graphs
- Traversal:
- Visiting all the vertices or edges in the graph.
- Breadth-First Search (BFS) and Depth-First Search (DFS) are common traversal techniques.
- Search:
- Finding a path between two vertices or checking the existence of a specific edge.
- Shortest Path:
- Calculating the minimum distance or cost between two vertices.
- Algorithms: Dijkstra’s Algorithm, Bellman-Ford Algorithm, etc.
- Minimum Spanning Tree (MST):
- Finding the subset of edges that connects all vertices with the minimum total weight.
- Algorithms: Kruskal’s Algorithm, Prim’s Algorithm.
Basic C Code for Graph Representation
1. Using Adjacency Matrix
#include <stdio.h>
#define MAX 10
void displayGraph(int graph[MAX][MAX], int vertices) {
printf(“Adjacency Matrix:\n”);
for (int i = 0; i < vertices; i++) {
for (int j = 0; j < vertices; j++) {
printf(“%d “, graph[i][j]);
}
printf(“\n”);
}
}
int main() {
int graph[MAX][MAX] = {0};
int vertices = 4;
// Add edges
graph[0][1] = 1;
graph[1][0] = 1;
graph[1][2] = 1;
graph[2][1] = 1;
graph[2][3] = 1;
graph[3][2] = 1;
displayGraph(graph, vertices);
return 0;
}
2. Using Adjacency List
#include <stdio.h>
#include <stdlib.h>
struct Node {
int vertex;
struct Node* next;
};
struct Graph {
int numVertices;
struct Node** adjLists;
};
struct Node* createNode(int vertex) {
struct Node* newNode = malloc(sizeof(struct Node));
newNode->vertex = vertex;
newNode->next = NULL;
return newNode;
}
struct Graph* createGraph(int vertices) {
struct Graph* graph = malloc(sizeof(struct Graph));
graph->numVertices = vertices;
graph->adjLists = malloc(vertices * sizeof(struct Node*));
for (int i = 0; i < vertices; i++) {
graph->adjLists[i] = NULL;
}
return 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;
}
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(4);
addEdge(graph, 0, 1);
addEdge(graph, 0, 2);
addEdge(graph, 1, 2);
addEdge(graph, 2, 3);
printGraph(graph);
return 0;
}
Conclusion
Graphs are powerful data structures for solving a wide variety of real-world problems. Their flexibility in representation and the ability to model relationships between entities make them essential for applications in various fields, such as networking, navigation, and AI.