Lecture 7: Graph
Md. Nazmul Abdal
Lecturer
Department of CSE
University of Liberal Arts Bangladesh (ULAB)
Introduction
⚫ A graph data structure is a collection of nodes that have data and are
connected to other nodes.
⚫ More precisely, a graph is a data structure (V, E) that consists of
⚫ A collection of vertices V
⚫ A collection of edges E, represented as ordered pairs of vertices (u,v)
⚫ In the graph,
⚫ V = {0, 1, 2, 3}
⚫ E = {(0,1), (0,2), (0,3), (1,2)}
⚫ G = {V, E}
Terminologies
Adjacency: A vertex is said to be adjacent to another vertex if
there is an edge connecting them. Vertices 2 and 3 are not
adjacent because there is no edge between them.
Path: A sequence of edges that allows you to go from vertex A to
vertex B is called a path. 0-1, 1-2 and 0-2 are paths from vertex 0
to vertex 2.
Directed Graph: A graph in which an edge (u,v) doesn't
necessarily mean that there is an edge (v, u) as well. The edges in
such a graph are represented by arrows to show the direction of
the edge.
Undirected Graph
⚫ An undirected graph is a graph in which the edges do not point in any
direction (ie. the edges are bidirectional).
⚫ A connected graph is a graph in which there is always a path from a
vertex to any other vertex.
Spanning Tree
⚫ A spanning tree is a sub-graph of an undirected connected graph, which
includes all the vertices of the graph with a minimum possible number of
edges. If a vertex is missed, then it is not a spanning tree.
⚫ The edges may or may not have weights assigned to them.
Minimum Spanning Tree
⚫ A minimum spanning tree is a spanning tree in which the sum of the
weight of the edges is as minimum as possible.
Depth First Search (DFS)
⚫ Depth first Search or Depth first traversal is a recursive algorithm for
searching all the vertices of a graph or tree data structure.
⚫ A standard DFS implementation puts each vertex of the graph into one of
two categories:
⚫ Visited
⚫ Not Visited
⚫ The DFS algorithm works as follows:
1. Start by putting any one of the graph's vertices on top of a stack.
2. Take the top item of the stack and add it to the visited list.
3. Create a list of that vertex's adjacent nodes. Add the ones which
aren't in the visited list to the top of the stack.
4. Keep repeating steps 2 and 3 until the stack is empty.
Depth First Search (DFS)
Depth First Search (DFS)
Depth First Search (DFS)
Depth First Search (DFS)
Depth First Search (DFS)
Implementation
#include <stdio.h> // DFS algo
#include <stdlib.h> void DFS(struct Graph* graph, int vertex) {
struct node { struct node* adjList = graph->adjLists[vertex];
int vertex; struct node* temp = adjList;
struct node* next; graph->visited[vertex] = 1;
}; printf("Visited %d \n", vertex);
struct node* createNode(int v); while (temp != NULL) {
struct Graph { int connectedVertex = temp->vertex;
int numVertices; if (graph->visited[connectedVertex] == 0) {
int* visited; DFS(graph, connectedVertex);
// We need int** to store a two-dimensional array. }
// Similary, we need struct node** to store an array of temp = temp->next;
Linked lists }
struct node** adjLists; }
};
Implementation
// Create a node
struct node* createNode(int v) { // Add edge
struct node* newNode = malloc(sizeof(struct node)); void addEdge(struct Graph* graph, int src, int dest) {
newNode->vertex = v; // Add edge from src to dest
newNode->next = NULL; struct node* newNode = createNode(dest);
return newNode; newNode->next = graph->adjLists[src];
}
graph->adjLists[src] = newNode;
// Create graph
// Add edge from dest to src
struct Graph* createGraph(int vertices) {
struct Graph* graph = malloc(sizeof(struct Graph));
newNode = createNode(src);
graph->numVertices = vertices; newNode->next = graph->adjLists[dest];
graph->adjLists = malloc(vertices * sizeof(struct node*)); graph->adjLists[dest] = newNode;
graph->visited = malloc(vertices * sizeof(int)); }
int i;
for (i = 0; i < vertices; i++) {
graph->adjLists[i] = NULL;
graph->visited[i] = 0;
}
return graph;
}
Implementation
int main() {
// Print the graph
struct Graph* graph = createGraph(4);
void printGraph(struct Graph* graph) {
addEdge(graph, 0, 1);
int v;
addEdge(graph, 0, 2);
for (v = 0; v < graph->numVertices; v++) {
addEdge(graph, 1, 2);
struct node* temp = graph->adjLists[v];
addEdge(graph, 2, 3);
printf("\n Adjacency list of vertex %d\n ", v);
while (temp) {
printGraph(graph);
printf("%d -> ", temp->vertex);
temp = temp->next;
DFS(graph, 2);
}
printf("\n");
return 0;
}
}
}
Breadth First Search (BFS)
⚫ Breadth First Traversal or Breadth First Search is a recursive algorithm
for searching all the vertices of a graph or tree data structure.
⚫ A standard BFS implementation puts each vertex of the graph into one of
two categories:
⚫ Visited
⚫ Not Visited
⚫ The algorithm works as follows:
1. Start by putting any one of the graph's vertices at the back of a queue.
2. Take the front item of the queue and add it to the visited list.
3. Create a list of that vertex's adjacent nodes. Add the ones which
aren't in the visited list to the back of the queue.
4. Keep repeating steps 2 and 3 until the queue is empty.
Breadth First Search (BFS)
Breadth First Search (BFS)
Breadth First Search (BFS)
Breadth First Search (BFS)
Breadth First Search (BFS)
Implementation
#include <stdio.h> struct node* createNode(int);
#include <stdlib.h> struct Graph {
#define SIZE 40 int numVertices;
struct queue { struct node** adjLists;
int items[SIZE]; int* visited;
int front; };
int rear; // BFS algorithm
}; void bfs(struct Graph* graph, int startVertex) {
struct queue* createQueue(); struct queue* q = createQueue();
void enqueue(struct queue* q, int); graph->visited[startVertex] = 1;
int dequeue(struct queue* q); enqueue(q, startVertex);
void display(struct queue* q); while (!isEmpty(q)) {
int isEmpty(struct queue* q); printQueue(q);
void printQueue(struct queue* q); int currentVertex = dequeue(q);
struct node { printf("Visited %d\n", currentVertex);
int vertex; struct node* temp = graph->adjLists[currentVertex];
struct node* next;
};
Implementation
while (temp) { // Creating a graph
int adjVertex = temp->vertex; struct Graph* createGraph(int vertices) {
struct Graph* graph = malloc(sizeof(struct Graph));
if (graph->visited[adjVertex] == 0) { graph->numVertices = vertices;
graph->visited[adjVertex] = 1;
enqueue(q, adjVertex); graph->adjLists = malloc(vertices * sizeof(struct
} node*));
temp = temp->next; graph->visited = malloc(vertices * sizeof(int));
}
} int i;
} for (i = 0; i < vertices; i++) {
// Creating a node graph->adjLists[i] = NULL;
struct node* createNode(int v) { graph->visited[i] = 0;
struct node* newNode = malloc(sizeof(struct node)); }
newNode->vertex = v;
newNode->next = NULL; return graph;
return newNode; }
}
Implementation
// Add edge // Check if the queue is empty
void addEdge(struct Graph* graph, int src, int dest) { int isEmpty(struct queue* q) {
// Add edge from src to dest if (q->rear == -1)
struct node* newNode = createNode(dest); return 1;
newNode->next = graph->adjLists[src]; else
graph->adjLists[src] = newNode; return 0;
// Add edge from dest to src }
newNode = createNode(src); // Adding elements into queue
newNode->next = graph->adjLists[dest]; void enqueue(struct queue* q, int value) {
graph->adjLists[dest] = newNode; if (q->rear == SIZE - 1)
} printf("\nQueue is Full!!");
// Create a queue else {
struct queue* createQueue() { if (q->front == -1)
struct queue* q = malloc(sizeof(struct queue)); q->front = 0;
q->front = -1; q->rear++;
q->rear = -1; q->items[q->rear] = value;
return q; }
} }
Implementation
if (isEmpty(q)) {
// Removing elements from queue
printf("Queue is empty");
int dequeue(struct queue* q) {
} else {
int item;
printf("\nQueue contains \n");
if (isEmpty(q)) {
for (i = q->front; i < q->rear + 1; i++) {
printf("Queue is empty"); printf("%d ", q->items[i]);
item = -1; }
} else { }
item = q->items[q->front]; }
q->front++; int main() {
if (q->front > q->rear) { struct Graph* graph = createGraph(6);
printf("Resetting queue "); addEdge(graph, 0, 1);
q->front = q->rear = -1; addEdge(graph, 0, 2);
} addEdge(graph, 1, 2);
} addEdge(graph, 1, 4);
addEdge(graph, 1, 3);
return item;
addEdge(graph, 2, 4);
}
addEdge(graph, 3, 4);
// Print the queue
bfs(graph, 0);
void printQueue(struct queue* q) {
return 0;
int i = q->front;
}
Thank You
