top of page

## Data Structures Notes

Data Structures Basic

Stacks

Queues

Sorting

Tree

Graphs

Hashing and Searching

Q

1

What is BFS?

Ans

BFS is a tree or graph traversal algorithm in which it starts with root node or 'search key' and visits all neighbour nodes of the same depth level before moving to next depth level.
To implement this algorithm, we need to use the Queue . All the adjacent vertices are added into the queue, when all adjacent vertices are completed, one item is removed from the queue and start traversing through that vertex again.
Algorithm:
Algorithm BFS(G, key) is
declare Q as queue
label key as discovered
Q.enqueue(key)
while Q is not empty do
v = Q.dequeue()
if v is the key then
return v
for all edges from v to w in G.adjacentEdges(v) do
if w is not labeled as discovered then
label w as discovered
w.parent= v
Q.enqueue(w)
C Program to implement BFS

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

#define MAX 5

struct Vertex {
char label;
bool visited;
};

//queue variables

int queue[MAX];
int rear = -1;
int front = 0;
int queueItemCount = 0;

//graph variables

//array of vertices
struct Vertex* lstVertices[MAX];

//vertex count
int vertexCount = 0;

//queue functions

void insert(int data) {
queue[++rear] = data;
queueItemCount++;
}

int removeData() {
queueItemCount--;
return queue[front++];
}

bool isQueueEmpty() {
return queueItemCount == 0;
}

//graph functions

//add vertex to the vertex list
struct Vertex* vertex = (struct Vertex*) malloc(sizeof(struct Vertex));
vertex->label = label;
vertex->visited = false;
lstVertices[vertexCount++] = vertex;
}

}

//display the vertex
void displayVertex(int vertexIndex) {
printf("%c ",lstVertices[vertexIndex]->label);
}

int i;

for(i = 0; i<vertexCount; i++) {
if(adjMatrix[vertexIndex][i] == 1 && lstVertices[i]->visited == false)
return i;
}

return -1;
}

int i;

//mark first node as visited
lstVertices[0]->visited = true;

//display the vertex
displayVertex(0);

//insert vertex index in queue
insert(0);
int unvisitedVertex;

while(!isQueueEmpty()) {
//get the unvisited vertex of vertex which is at front of the queue
int tempVertex = removeData();

while((unvisitedVertex = getAdjUnvisitedVertex(tempVertex)) != -1) {
lstVertices[unvisitedVertex]->visited = true;
displayVertex(unvisitedVertex);
insert(unvisitedVertex);
}

}

//queue is empty, search is complete, reset the visited flag
for(i = 0;i<vertexCount;i++) {
lstVertices[i]->visited = false;
}
}

int main() {
int i, j;

for(i = 0; i<MAX; i++) // set adjacency {
for(j = 0; j<MAX; j++) // matrix to 0
}

addEdge(0, 1); // S - A
addEdge(0, 2); // S - B
addEdge(0, 3); // S - C
addEdge(1, 4); // A - D
addEdge(2, 4); // B - D
addEdge(3, 4); // C - D

return 0;
}
Below image depicts working of BFS algorithm

image source: https://www.tutorialspoint.com/

Q

2

What is DFS?

Ans

DFS is a graph traversal algorithm in which itstarts with key node and explore all the nodes along the branch before backtracking.
It starts by putting any one of the graph node on top of a stack and then takes top item of the stack and add it to the visited list. After that it creates a list of vertex's adjacent nodes and add them to the top of the stack if they aren't visited. It keeps repeating previous steps until the stack is empty.
DFS recursive implementation:
DFS(G, u)
u.visited = true
if v.visited == false
DFS(G,v)

init() {
For each u ∈ G
u.visited = false
For each u ∈ G
DFS(G, u)
}

C Program to implement DFS:

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

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

struct node* createNode(int v);

struct Graph {
int numVertices;
int* visited;

// We need int** to store a two dimensional array.
// Similary, we need struct node** to store an array of Linked lists
};

// DFS algo
void DFS(struct Graph* graph, int vertex) {

graph->visited[vertex] = 1;
printf("Visited %d \n", vertex);

Q

3

What is Prims minimum spanning tree?

Ans

Prims minimum spanning tree algorithm is a greedy algorithm. This algorithm is used to find minimum cost spanning tree by using greedy approach.
It maintains two sets of vertices one contains vertices already included in MST and other one contains vertices that is not included yet.
At each step it selects minimum cost edge and moves to other end of the edge to select another MST.

Steps in Prims Algorithm:
1.Remove all the loops and parallel edges.(keep the edges with least cost).
2.Choose any node as a root node and add it to the spannin tree
3.Add another vertex which is not in spanning tree and has least weight edge connected with the spanning tree.
4.Repeat previous step until all the vertices of the graph added to the spanning tree
5. Print the cost.

C code to implement Prims Algorithm
#include<stdio.h>
#include<conio.h>
int a,b,u,v,n,i,j,ne=1;
int visited[10]= {
0
}
,min,mincost=0,cost[10][10];
void main() {
clrscr();
printf("\n Enter the number of nodes:");
scanf("%d",&n);
for (i=1;i<=n;i++)
for (j=1;j<=n;j++) {
scanf("%d",&cost[i][j]);
if(cost[i][j]==0)
cost[i][j]=999;
}
visited[1]=1;
printf("\n");
while(ne<n) {
for (i=1,min=999;i<=n;i++)
for (j=1;j<=n;j++)
if(cost[i][j]<min)
if(visited[i]!=0) {
min=cost[i][j];
a=u=i;
b=v=j;
}
if(visited[u]==0 || visited[v]==0) {
printf("\n Edge %d:(%d %d) cost:%d",ne++,a,b,min);
mincost+=min;
visited[b]=1;
}
cost[a][b]=cost[b][a]=999;
}
printf("\n Minimun cost=%d",mincost);
getch();
}

Q

4

What is Krushkal's spanning tree?

Ans

Krushkal's spanning tree is a spanning tree which is formed by using krushkal's algorithm, which is a greedy algorithm.
The idea is to make a greedy choice to select smallest weighted edge that does not form a cycle with already constructed MST.

Steps in Krushkal's Algorithm:
1.Remove all the loops and parallel edges from the graph.
2.Arrange all the edges in their increasing order og weight.
3.Add the edge which has least weightage.
4.Repeat step 3 till all the vertices of the graph is added without forming any cycle.

C code :
#include<stdio.h>

#define MAX 30

typedef struct edge
{
int u,v,w;
}edge;

typedef struct edgelist
{
edge data[MAX];
int n;
}edgelist;

edgelist elist;

int G[MAX][MAX],n;
edgelist spanlist;

void kruskal();
int find(int belongs[],int vertexno);
void union1(int belongs[],int c1,int c2);
void sort();
void print();

void main()
{
int i,j,total_cost;

printf("\nEnter number of vertices:");

scanf("%d",&n);

for(i=0;i<n;i++)
for(j=0;j<n;j++)
scanf("%d",&G[i][j]);

kruskal();
print();
}

void kruskal()
{
int belongs[MAX],i,j,cno1,cno2;
elist.n=0;

for(i=1;i<n;i++)
for(j=0;j<i;j++)
{
if(G[i][j]!=0)
{
elist.data[elist.n].u=i;
elist.data[elist.n].v=j;
elist.data[elist.n].w=G[i][j];
elist.n++;
}
}

sort();

for(i=0;i<n;i++)
belongs[i]=i;

spanlist.n=0;

for(i=0;i<elist.n;i++)
{
cno1=find(belongs,elist.data[i].u);
cno2=find(belongs,elist.data[i].v);

if(cno1!=cno2)
{
spanlist.data[spanlist.n]=elist.data[i];
spanlist.n=spanlist.n+1;
union1(belongs,cno1,cno2);
}
}
}

int find(int belongs[],int vertexno)
{
return(belongs[vertexno]);
}

void union1(int belongs[],int c1,int c2)
{
int i;

for(i=0;i<n;i++)
if(belongs[i]==c2)
belongs[i]=c1;
}

void sort()
{
int i,j;
edge temp;

for(i=1;i<elist.n;i++)
for(j=0;j<elist.n-1;j++)
if(elist.data[j].w>elist.data[j+1].w)
{
temp=elist.data[j];
elist.data[j]=elist.data[j+1];
elist.data[j+1]=temp;
}
}

void print()
{
int i,cost=0;

for(i=0;i<spanlist.n;i++)
{
printf("\n%d\t%d\t%d",spanlist.data[i].u,spanlist.data[i].v,spanlist.data[i].w);
cost=cost+spanlist.data[i].w;
}

printf("\n\nCost of the spanning tree=%d",cost);
}

Q

5

Explain Floyd's algorithm.

Ans

Floyd's algorithm is a dynamic approach to find the shortest path between all the pairs of vertices in a weighted graph. The graph can be directed or undirected graph.
Pseudo Code :
n = no of vertices
A = matrix of dimension n*n
for k = 1 to n
for i = 1 to n
for j = 1 to n
Ak[i, j] = min (Ak-1[i, j], Ak-1[i, k] + Ak-1[k, j])
return A

C program:
#include <stdio.h>

// defining the number of vertices
#define nV 4

#define INF 999

void printMatrix(int matrix[][nV]);

// Implementing floyd warshall algorithm
void floydWarshall(int graph[][nV]) {
int matrix[nV][nV], i, j, k;

for (i = 0; i < nV; i++)
for (j = 0; j < nV; j++)
matrix[i][j] = graph[i][j];

for (k = 0; k < nV; k++) {
for (i = 0; i < nV; i++) {
for (j = 0; j < nV; j++) {
if (matrix[i][k] + matrix[k][j] < matrix[i][j])
matrix[i][j] = matrix[i][k] + matrix[k][j];
}
}
}
printMatrix(matrix);
}

void printMatrix(int matrix[][nV]) {
for (int i = 0; i < nV; i++) {
for (int j = 0; j < nV; j++) {
if (matrix[i][j] == INF)
printf("%4s", "INF");
else
printf("%4d", matrix[i][j]);
}
printf("\n");
}
}

int main() {
int graph[nV][nV] = {{0, 3, INF, 5},
{2, 0, INF, 4},
{INF, 1, 0, INF},
{INF, INF, 2, 0}};
floydWarshall(graph);
}

bottom of page