Data Structures Notes

mobiprep (6).png

Data Structures Basic

mobiprep (6).png

Stacks

mobiprep (6).png

Queues

mobiprep (6).png

Linked List

mobiprep (6).png

Sorting

mobiprep (6).png

Tree

mobiprep (6).png

Graphs

mobiprep (6).png

Hashing and Searching

Heading

Q

1

What is BFS?

LRM_EXPORT_207556595493866_20190724_1939

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];

//adjacency matrix
int adjMatrix[MAX][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
void addVertex(char label) {
struct Vertex* vertex = (struct Vertex*) malloc(sizeof(struct Vertex));
vertex->label = label;
vertex->visited = false;
lstVertices[vertexCount++] = vertex;
}

//add edge to edge array
void addEdge(int start,int end) {
adjMatrix[start][end] = 1;
adjMatrix[end][start] = 1;
}

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

//get the adjacent unvisited vertex
int getAdjUnvisitedVertex(int vertexIndex) {
int i;

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

return -1;
}

void breadthFirstSearch() {
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();

//no adjacent vertex found
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
adjMatrix[i][j] = 0;
}

addVertex('S'); // 0
addVertex('A'); // 1
addVertex('B'); // 2
addVertex('C'); // 3
addVertex('D'); // 4

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

printf("\nBreadth First Search: ");

breadthFirstSearch();

return 0;
}
Below image depicts working of BFS algorithm

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

LRM_EXPORT_207556595493866_20190724_1939

Q

2

What is DFS?

LRM_EXPORT_207556595493866_20190724_1939

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
for each v ∈ G.Adj[u]
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
struct node** adjLists;
};

// DFS algo
void DFS(struct Graph* graph, int vertex) {
struct node* adjList = graph->adjLists[vertex];
struct node* temp = adjList;

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

LRM_EXPORT_207556595493866_20190724_1939

Q

3

What is Prims minimum spanning tree?

LRM_EXPORT_207556595493866_20190724_1939

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);
printf("\n Enter the adjacency matrix:\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();
}

LRM_EXPORT_207556595493866_20190724_1939

Q

4

What is Krushkal's spanning tree?

LRM_EXPORT_207556595493866_20190724_1939

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);

printf("\nEnter the adjacency matrix:\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);
}

LRM_EXPORT_207556595493866_20190724_1939

Q

5

Explain Floyd's algorithm.

LRM_EXPORT_207556595493866_20190724_1939

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];

// Adding vertices individually
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);
}

LRM_EXPORT_207556595493866_20190724_1939