MOGAJI GABRIEL ROTIMI

R1812D7158691
UU-COM-3005-42931
George Kelveris

Final Assessment

(1.)
 (2.)

Algorithm for insert:

- Assume that the graph has n vertices.
- The graph contains some edges.
- Between the vertex and the new edge, load (i,j).
- Assume that there are n vertices in the existing UNDIRECTED GRAPH.
- PUT VI, VJ
- If either (vi > n or vj > n), then (vi && vj) INCLUDED
- There is no way to PRINT" between vi and vj.
- IF NOT, DO CHOOSE 'a'
- At the end of the adjacency list of vi, insert vi; at the end of the adjacency list of vj, insert
vj.
- STOP

Algorithm for delete:

- Assume that the graph has n vertices.
- The graph contains some edges (i,j).
- Between the vertex and the new edge, load (i,j)
- Suppose that n is the number of vertices in the existing UNDIRECTED GRAPH.
- REMOVE vi, vj
- If either (vi > n or vj > n), then (vi && vj) INCLUDED
- There is no way to PRINT" between vi and vj.
- IF NOT, DO CHOOSE 'a'
- a.remove VI from the list of adjacent VIs b.remove vJ from the list of adjacent vJs
- According to the included criteria, STOP vertex and edge insertion and deletion will
vary.

(3.)
PRIMS ALGO
---------------------
#include <cstring>
#include <iostream>
using namespace std;

#define INF 9999999

#define V 5

int G[V][V] = {
{0, 9, 75, 0, 0},
{9, 0, 95, 19, 42},
{75, 95, 0, 51, 66},
{0, 19, 51, 0, 31},
{0, 42, 66, 31, 0}};

int main() {
int no_edge;

int select[V];

memset(select, false, sizeof(select));

no_edge = 0;

select[0] = true;
int x;
int y;

cout << "Edge"

<< " : "
<< "Weight";
cout << endl;
while (no_edge < V - 1) {

int min = INF;

x = 0;
y = 0;

for (int i = 0; i < V; i++) {

if (select[i]) {
for (int j = 0; j < V; j++) {
if (!select[j] && G[i][j]) { //if not in selected and there is an edge
if (min > G[i][j]) {
min = G[i][j];
x = i;
y = j;
}
}
}
}
}
cout << x << " - " << y << " : " << G[x][y];
cout << endl;
select[y] = true;
no_edge++;
}

return 0;
}

KRUSHKAL ALGO
------------------
#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;

#define edge pair<int, int>

class Graph {
private:
vector<pair<int, edge> > G; // graph
vector<pair<int, edge> > T; // mst
int *parent;
int V;
public:
Graph(int V);
void WeightedEdge(int u, int v, int w);
int find_set(int i);
void union_set(int u, int v);
void krushkal();
void print();
};
Graph::Graph(int V) {
parent = new int[V];
for (int i = 0; i < V; i++)
parent[i] = i;

G.clear();
T.clear();
}
void Graph::WeightedEdge(int u, int v, int w) {
G.push_back(make_pair(w, edge(u, v)));
}
int Graph::find_set(int i) {

if (i == parent[i])
return i;
else

return find_set(parent[i]);
}

void Graph::union_set(int u, int v) {

parent[u] = parent[v];
}
void Graph::kruskal() {
int i, uRep, vRep;
sort(G.begin(), G.end());
for (i = 0; i < G.size(); i++) {
uRep = find_set(G[i].second.first);
vRep = find_set(G[i].second.second);
if (uRep != vRep) {
T.push_back(G[i]);
union_set(uRep, vRep);
}
}
}
void Graph::print() {
cout << "Edge :"
<< " Weight" << endl;
for (int i = 0; i < T.size(); i++) {
cout << T[i].second.first << " - " << T[i].second.second << " : "
<< T[i].first;
cout << endl;
}
}
int main() {
Graph g(6);
g.WeightedEdge(0, 1, 4);
g.WeightedEdge(0, 2, 4);
g.WeightedEdge(1, 2, 2);
g.WeightedEdge(1, 0, 4);
g.WeightedEdge(2, 0, 4);
g.WeightedEdge(2, 1, 2);
g.WeightedEdge(2, 3, 3);
g.WeightedEdge(2, 5, 2);
g.WeightedEdge(2, 4, 4);
g.WeightedEdge(3, 2, 3);
g.WeightedEdge(3, 4, 3);
g.WeightedEdge(4, 2, 4);
g.WeightedEdge(4, 3, 3);
g.WeightedEdge(5, 2, 2);
g.krushkal();
g.print();
return 0;
}

Prisms runs more quickly in dense graphs. KRUSKAL ALSO PERFORMS BETTER IN
SPARSE GRAPH,

PRIMS' TIME COMPLEXITY IS O(V2) WHERE V IS VERTICES, AND IT CAN BE

AMPLIFIEED TO O(E+LOGV) USING FIBONACCI HEAPS, BUT KRUSKAL'S TIME
COMPLEXITY IS O. (E log V).

(4.)

Code :

#include<stdio.h>

#include<stdlib.h>

#define MAX 100

#define initial 1

#define waiting 2

#define visited 3

int n;

int adj[MAX][MAX];

int state[MAX];

int label[MAX];
void create_graph();

void BF_Traval();

void BFS(int v, int component_Num);

int queue[MAX], front = -1,rear = -1;

void insert_queue(int vertex);

int delete_queue();

int isEmpty_queue();

int main()

create_graph();

BF_Traval();

void BF_Traval()

int v, components = 0;

for(v=0;v<n;v++)

state[v] = initial;

components++;

BFS(0, components);

for(v=0; v<n; v++)

{

if(state[v] == initial)

components++;

BFS(v, components);

printf("Number of connected components = %d", components);

if(components == 1)

printf("Connected Graph");

else

printf("Not a Connected Graph");

void BFS(int v, int component_Num)

int i;

insert_queue(v);

state[v] = waiting;

while(!isEmpty_queue())

{
v = delete_queue();

state[v] = visited;

label[v] = component_Num;

printf("Vertex %d Component = %d",v, label[v]);

for(i=0; i<n; i++)

if( adj[v][i] == 1 && state[i] == initial)

insert_queue(i);

state[i] = waiting;

printf("");

void insert_queue(int vertex)

if (rear == MAX-1)

printf("Queue Overflow");

else
{

if(front == -1)

front = 0;

rear = rear+1;

queue[rear] = vertex ;

int isEmpty_queue()

if(front == -1 || front > rear )

return 1;

else

return 0;

int delete_queue()

int del_item;

if (front == -1 || front > rear)

printf("Queue Underflow");
exit(1);

del_item = queue[front];

front = front+1;

return del_item;

void create_graph()

int i,max_edges,origin,destin;

printf("Enter number of vertices : ");

scanf("%d",&n);

max_edges = n*(n-1)/2; /*Undirected graph*/

for(i=1;i<=max_edges;i++)

printf("Enter edge %d( -1 -1 to quit ) : ",i);

scanf("%d %d",&origin,&destin);

if((origin == -1) && (destin == -1))

break;

if( origin >= n || destin >= n || origin<0 || destin<0)

{
printf("Invalid edge!");

i--;

else

adj[origin][destin]=1;

adj[destin][origin]=1;

}
 (5.)

1. Bubble sort:
A straightforward sorting algorithm known as bubble sort, also known as comparison sort,
continually scans the list, compares neighboring elements, and swaps them if they are out of
order. The most straightforward algorithm is also the least effective. But because it represents the
fundamentals of sorting, it is imperative to learn about it.

Algorithm: If an element's order is incorrect, we can check it by comparing neighboring elements

(i.e., a[i] > a[j] for 1 = I j = array size, and vice versa). If so, switch them.
Explanation:
Say we have an n-dimensional array. We perform the above step (swapping) for n - 1 passes in
order to sort this array.

To put it simply, the largest element goes at the extreme right of the arrangement, followed by
the second largest, which goes one position after the last, and so on. The ith largest member is
swapped into its proper position in the array during the ith pass.
According to mathematics, at least one element from the initial set of (n - I + 1) items will
appear at the proper location in the ith pass. The ith (for 1 = I = n - 1) biggest element in the
array will be that one. Since we are determining whether a[j] > a[j + 1] in the jth iteration of the
ith traverse of the array (for 1 = j = n - I and a[j] will always be greater than a[j + 1] when it is
the largest entry in range [1, n - I + 1], We will now switch it. This will carry on until the (n - I +
1)th place of the array contains the ith greatest element.

2.Selection Sort
A straightforward comparison-based sorting algorithm is selection sort. There is enough memory
there already.
The following stages are carried out until the unsorted subarray is empty:
Choose the smallest element in the subarray that is not sorted.
Replace it with the subarray's leftmost member, which is not sorted.
The leftmost element of the unsorted subarray is now the rightmost element of the sorted
subarray and no longer belongs to the unsorted subarray.

3.Insertion Sort
The sorting method known as insertion sort builds the sorted array one item at a time. Sequential
comparisons are performed on the array's items before they are simultaneously arranged in a
specific order. The connection can be appreciated by looking at how a deck of cards is arranged.
The name "Insertion Sort" refers to how this sort operates by inserting an element at a specific
location.
Comparing the element in question with its neighboring element is the first step. Furthermore, if
each comparison shows that the element in question may be inserted at a specific location, room
is made for it by moving the other elements one position to the right before inserting the element
in the proper location.
The aforementioned process is continued until every member in the array is in its proper
position.

4.Shell Sort
The insertion sort technique is extended by the shell sort algorithm, which is particularly
effective at sorting arrays that are widely out of order. Sub-arrays of the array are created before
insertion sort is used. As for the algorithm:

1. Determine the gap's value (formula given in the illustration below).

2. Make these smaller arrays out of the main array.
3. Put the insertion sort to use.
4. Continue doing this until the entire list has been sorted.

5.Merge Sort
One of the most effective sorting algorithms is merge sort. It operates according to the divide and
conquer strategy. Merge sort continually divides a list into many sublists until each sublist only
has one element, and then it merges those sublists to create a sorted list.

Merge sort divides the list into equal halves until there is no more room for division. By
definition, a list is sorted if it contains just one item. Merge sort is used to combine the smaller
sorted lists while maintaining the order of the resultant list.

Step 1: Return if there is just one element in the list because it has already been sorted.
Step 2: Recursively split the list in half until it can no longer be divided.

Step 3: Sortedly combine the smaller listings into new ones.

6. Quick Sort
The foundation of the very effective sorting algorithm known as "quick sort" is the division of a
large data array into smaller arrays. A huge array is divided into two arrays, one of which
contains values less than the pivot value—the value on which the division is made—and the
other of which contains values higher than the pivot value.

Step 1: Make any element the pivot.

Step 2: Divide the array based on the pivot.
Step 3: Recursively apply rapid sort to the left partition.
Step 4: Recursively apply rapid sort to the right partition.