P1: Coffee
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
struct node {
int custid;
char n[30];
int amt;
struct node* next;
} *head = 0, *temp, *ptr1 = 0, *ptr2 = 0, *new1, *max_id, *min_id;
int main() {
int ch, id, cost, c = 0, max, min;
char res, name[30];
do {
printf("1.Add\n2.Search by ID\n3.Print Bill\n4.Max and Min Sell\n\nChoose any 1: \t");
scanf("%d", &ch);
switch(ch) {
case 1:
do {
new1 =(struct node*)malloc(sizeof(struct node));
printf("\nEnter Customer ID, Name, Purchase Amount: \t");
scanf("%d %s %d", &id, &name, &cost);
new1->custid = id;
strcpy(new1->n, name);
new1->amt = cost;
new1->next = 0;
if(head == 0) {
head = new1;
c++;
} else {
temp = head;
while(temp->next != 0) {
temp = temp->next;
}
temp->next = new1;
c++;
}
printf("\nDo you want to add more: \t");
scanf(" %c", &res);
} while(res == 'y');
break;
case 2:
printf("\nEnter ID of customer to be searched : \t");
scanf("%d", &id);
temp = head;
while(temp != 0) {
if(temp->custid == id) {
printf("\n**********************************************************\n");
printf("\nCustomer ID\tName\tTotal Purchase");
printf("\n%d\t%s\t%d", temp->custid, temp->n, temp->amt);
break;
} else {
temp = temp->next;
}
}
break;
case 3:
temp = head;
max_id = head; min_id = head;
int tot_sale = 0;
printf("\n**********************************************************\n");
printf("\nC_ID\t\tName\tTotal Purchase");
while(temp != 0) {
printf("\n%d\t|\t%s\t|\t%d", temp->custid, temp->n, temp->amt);
tot_sale += temp->amt;
temp = temp->next;
}
printf("\n\nTotal Sale of the Day is :\t%d", tot_sale);
break;
case 4:
temp = head->next;
max = head->amt;
min = head->amt;
while(temp != 0) {
if(temp->amt > max) {
max_id = temp;
max = temp->amt;
}
if(temp->amt < min) {
min_id = temp;
min = temp->amt;
}
temp = temp->next;
}
printf("\nSell Type\tC_ID\t\tName\tTotal Purchase");
printf("\nMax Sell:\t%d\t|\t%s\t|\t%d", max_id->custid, max_id->n, max_id->amt);
printf("\nMin Sell:\t%d\t|\t%s\t|\t%d", min_id->custid, min_id->n, min_id->amt);
break;
}
printf("\n\nDo you want to continue: \t");
scanf(" %c", &res);
} while(res == 'y');
}
---------------------------------------------------------------------------------------------------------------------------
---------------------------------------------------------------------------------------------------------------------------
P2a: Stack
#include<bits/stdc++.h>
using namespace std;
struct node {
struct node* prev;
int val;
struct node* next;
} *head = 0, *ptr1, *ptr2, *temp, *new1;
int main() {
int ch, x, c = 0;
char res;
do {
printf("\n1.Push\n2.Pop\n3.Display\nChoose any 1: \t");
scanf("%d", &ch);
switch(ch) {
case 1:
do {
printf("\nEnter value: \t");
scanf("%d", &x);
new1 = (struct node*)malloc(sizeof(struct node));
new1->prev = 0;
new1->val = x;
new1->next = 0;
if(head == 0) {
head = new1;
c++;
} else {
temp = head;
while(temp->next != 0) {
temp = temp->next;
}
temp->next = new1;
new1->prev = temp;
c++;
}
printf("\nDo you want to add more: \t");
scanf(" %c", &res);
} while(res == 'y');
break;
case 2:
temp = head;
while(temp->next != 0) {
temp = temp->next;
}
ptr1 = temp;
temp = temp->prev;
temp->next = 0;
free(ptr1);
break;
case 3:
temp = head;
while(temp->next != 0) {
temp = temp->next;
}
while(temp != head) {
printf("%d\n", temp->val);
temp = temp->prev;
}
printf("%d\n", head->val);
break;
}
printf("\nDo you want to continue: \t");
scanf(" %c", &res);
}while(res == 'y');
}
P2b: Queue
#include <stdio.h>
#include <stdlib.h>
// Structure to create a node with data and next pointer
struct node {
int data;
struct node *next;
};
struct node *front = NULL;
struct node *rear = NULL;
// Enqueue() operation on a queue
void enqueue(int value) {
struct node *ptr;
ptr = (struct node *)malloc(sizeof(struct node));
ptr->data = value;
ptr->next = NULL;
if ((front == NULL) && (rear == NULL)) {
front = rear = ptr;
} else {
rear->next = ptr;
rear = ptr;
}
printf("Node is Inserted\n\n");
}
// Dequeue() operation on a queue
int dequeue() {
if (front == NULL) {
printf("\nUnderflow\n");
return -1;
} else {
struct node *temp = front;
int temp_data = front->data;
front = front->next;
free(temp);
return temp_data;
}
}
// Display all elements of queue
void display() {
struct node *temp;
if ((front == NULL) && (rear == NULL)) {
printf("\nQueue is Empty\n");
} else {
printf("The queue is \n");
temp = front;
while (temp) {
printf("%d--->", temp->data);
temp = temp->next;
}
printf("NULL\n\n");
}
}
int main() {
int choice, value;
printf("\nImplementation of Queue using Linked List\n");
while (choice != 4) {
printf("1.Enqueue\n2.Dequeue\n3.Display\n4.Exit\n");
printf("\nEnter your choice : ");
scanf("%d", &choice);
switch (choice) {
case 1:
printf("\nEnter the value to insert: ");
scanf("%d", &value);
enqueue(value);
break;
case 2:
printf("Popped element is :%d\n", dequeue());
break;
case 3:
display();
break;
case 4:
exit(0);
break;
default:
printf("\nWrong Choice\n");
}
}
return 0;
}
---------------------------------------------------------------------------------------------------------------------------
---------------------------------------------------------------------------------------------------------------------------
P3: Skip List
#include <stdio.h>
#include <stdlib.h>
const int level = 3;
typedef struct Skip_List
{
int data;
struct Skip_List *next[3];
} * skl;
skl head = NULL;
skl getNode()
{
int val;
printf("Enter The value You want to Insert:-");
scanf("%d", &val);
struct Skip_List *newNode = (struct Skip_List *)malloc(sizeof(struct Skip_List));
newNode->data = val;
for (int i = 0; i < level; i++)
newNode->next[i] = NULL;
return newNode;
}
void DisplyExpress()
{
struct Skip_List *temp = head;
while (temp != NULL)
{
printf("%d ", temp->data);
temp = temp->next[1];
}
}
void DisplyExpress2()
{
struct Skip_List *temp = head;
while (temp != NULL)
{
printf("%d ", temp->data);
temp = temp->next[2];
}
}
void normalWay()
{
struct Skip_List *newNode = getNode();
if (head == NULL)
{
head = newNode;
return;
}
struct Skip_List *temp = head;
int cnt = 1;
while (temp->next[0] != NULL)
{
temp = temp->next[0];
}
temp->next[0] = newNode;
}
void expressWay()
{
skl temp, prev;
for (int i = 1; i < level; i++)
{
int ct = 1;
temp = head->next[i - 1];
for (prev = head; temp != NULL; temp = temp->next[i - 1])
{
if (ct % level == 0)
{
prev->next[i] = temp;
prev = temp;
}
ct++;
}
}
}
void Display()
{
struct Skip_List *temp = head;
while (temp != NULL)
{
printf("%d ", temp->data);
temp = temp->next[0];
}
}
void search(int key)
{
skl prev = head;
skl temp = head;
int i = level - 1;
int found = 0;
int ct = 0;
while (found == 0 && i >= 0)
{
if (key < head->data || temp == NULL)
{
printf("%d Element Not found", key);
return;
}
else if (temp->data == key)
{
ct++;
found = 1;
printf(" %d Found in %d Iterations", key, ct);
}
else if (key > temp->data)
{
ct++;
prev = temp;
temp = temp->next[i];
if (temp == NULL)
{
i--;
temp = prev->next[i];
}
}
else if (key < temp->data)
{
i--;
temp = prev->next[i];
ct++;
}
else
{
found=0;
}
}
if(found==0)
printf("Element Not Found!!!\n");
printf("\n");
}
int main()
{
char ch = 'y';
do
{
normalWay();
printf("\nWant To insert a Node(y/n):-");
scanf(" %c", &ch);
} while (ch == 'y');
expressWay();
printf("\n\nNormal Lane:\n");
Display();
printf("\n");
printf("Express Lane 1:\n");
DisplyExpress();
printf("\n");
printf("Express Lane 2:\n");
DisplyExpress2();
printf("\n\n");
do
{
int key;
printf("Enter Element You Want To search:");
scanf("%d", &key);
search(key);
printf("\nWant To search another element ?(y/n):-");
scanf(" %c", &ch);
} while (ch == 'y');
return 0;
}
---------------------------------------------------------------------------------------------------------------------------
---------------------------------------------------------------------------------------------------------------------------
P4: Hashing
#include <stdio.h>
#include <stdlib.h>
#define TABLE_SIZE 10
struct node
{
int data;
struct node *next;
};
struct node *head[10]={NULL},*c;
void insert()
{
int i,key;
printf("\n\nEnter a value to be inserted :\n");
scanf("%d",&key);
i=key%10;
struct node * newnode=(struct node *)malloc(sizeof(struct node));
newnode->data=key;
newnode->next = NULL;
if(head[i] == NULL)
head[i] = newnode;
else
{
c=head[i];
while(c->next != NULL)
{
c=c->next;
}
c->next=newnode;
}
}
void search()
{
int key,index;
printf("\nEnter the element to be searched:\t");
scanf("%d",&key);
index=key%10;
if(head[index] == NULL)
printf("\nSearch element not found\n");
else
{
for(c=head[index];c!=NULL;c=c->next)
{
if(c->data == key)
{
printf("\nSearch element found at index %d\n",index);
break;
}
}
if(c==NULL)
printf("\nSearch element not found\n");
}
}
void display()
{
printf("\n");
int i;
for(i=0;i<10;i++)
{
if(head[i] == NULL)
{
printf("INDEX %d: \t0->", i);
}
else
{
printf("INDEX %d: \t", i);
for(c=head[i];c!=NULL;c=c->next)
printf("%d->",c->data);
}
printf("NULL\n\n");
}
}
int main()
{
int ch,key,i;
while(1)
{
printf("\n\n1.Add\n2:Display\n3:Search\n4:Exit");
printf("\nEnter your choice :\t");
scanf("%d",&ch);
switch(ch)
{
case 1:
insert();
break;
case 2:
display();
break;
case 3:
search();
break;
case 4:
exit(0);
}
printf("\n*************************************************************");
printf("\n*************************************************************");
printf("\n");
}
}
---------------------------------------------------------------------------------------------------------------------------
---------------------------------------------------------------------------------------------------------------------------
P5: BST
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
struct node
{
char emp_name[30];
int emp_sal;
struct node *right_child;
struct node *left_child;
};
void Print(struct node *root, int k1, int k2)
{
if ( NULL == root )
return;
if ( k1 < root->emp_sal )
Print(root->left_child, k1, k2);
if ( k1 <= root->emp_sal && k2 >= root->emp_sal )
printf("\n%s\t|\t%d", root->emp_name, root->emp_sal);
Print(root->right_child, k1, k2);
}
int FindTot(struct node* root) {
int tot = 0, totLeft = 0, totRight = 0;
if(root == NULL) {
printf("Tree is empty\n");
return 0;
}
else {
if(root->left_child != NULL)
totLeft = FindTot(root->left_child);
if(root->right_child != NULL)
totRight = FindTot(root->right_child);
tot = root->emp_sal + totLeft + totRight;
return tot;
}
}
int FindMax(struct node* root)
{
struct node* current = root;
while (current->right_child != NULL)
current = current->right_child;
printf("\n%s\t|\t%d", current->emp_name, current->emp_sal);
return 0;
}
int FindMin(struct node* root)
{
struct node* current = root;
while (current->left_child != NULL)
current = current->left_child;
printf("\n%s\t|\t%d", current->emp_name, current->emp_sal);
return 0;
}
/*
struct node* search(struct node *root, int x)
{
if(root==NULL)
return 0;
else if(root->data == x) return root;
else if(x>root->data)
return search(root->right_child, x);
else
return search(root->left_child,x);
}
struct node* find_minimum(struct node *root)
{
if(root == NULL)
return NULL;
else if(root->left_child != NULL)
return find_minimum(root->left_child);
return root;
}
*/
struct node* new_node(char name[], int sal)
{
struct node *p;
p = malloc(sizeof(struct node));
p->emp_sal = sal;
strcpy(p->emp_name, name);
p->left_child = NULL;
p->right_child = NULL;
return p;
}
struct node* insert(struct node *root, char name[], int sal)
{
if(root==NULL)
return new_node(name, sal);
else if(sal > root->emp_sal)
root->right_child = insert(root->right_child, name, sal);
else
root->left_child = insert(root->left_child, name, sal);
return root;
}
/*
struct node* delete(struct node *root, int x)
{
if(root==NULL)
return NULL;
if (x>root->data)
root->right_child = delete(root->right_child, x);
else if(x<root->data)
root->left_child = delete(root->left_child, x);
else
{
if(root->left_child==NULL && root->right_child==NULL)
{
free(root);
return NULL;
}
else if(root->left_child==NULL || root->right_child==NULL)
{
struct node *temp;
if(root->left_child==NULL)
temp = root->right_child;
else
temp = root->left_child;
free(root);
return temp;
}
else
{
struct node *temp = find_minimum(root->right_child);
root->data = temp->data;
root->right_child = delete(root->right_child, temp->data);
}
}
return root;
}
*/
void inorder(struct node *root)
{
if(root!=NULL)
{
inorder(root->left_child);
printf("\n%s\t|\t%d", root->emp_name, root->emp_sal);
inorder(root->right_child);
}
}
void preorder(struct node *root)
{
if(root!=NULL)
{
printf("\n%s\t|\t%d", root->emp_name, root->emp_sal);
preorder(root->left_child);
preorder(root->right_child);
}
}
void postorder(struct node *root)
{
if(root!=NULL)
{
postorder(root->left_child);
postorder(root->right_child);
printf("\n%s\t|\t%d", root->emp_name, root->emp_sal);
}
}
int main()
{
int m = 0, n = 0;
struct node *root;
int ch, cnt = 0, sal;
char res, name[30];
do{
printf("1.Add Employee\n2.Display Database\n3.Employee with Max and Min Salary\n4.Total Monthly Salary Expenditure of Company\n5.Display Salary in Range\n\nChoose any one: \t");
scanf("%d", &ch);
switch(ch) {
case 1:
do{
if(cnt == 0) {
printf("\nEnter Employee Name and Salary: \t");
scanf("%s %d", &name, &sal);
root = new_node(name, sal);
cnt++;
} else {
printf("\nEnter Employee Name and Salary: \t");
scanf("%s %d", &name, &sal);
insert(root, name, sal);
}
printf("\nDo you want to add more: \t");
scanf(" %c", &res);
}while(res == 'y');
printf("\n\n***********************************************************************");
printf("\n***********************************************************************\n\n");
break;
case 2:
printf("\nPreorder Display: \n");
printf("\nName\t|\tSalary");
preorder(root);
printf("\n\nInorder Display: \n");
printf("\nName\t|\tSalary");
inorder(root);
printf("\n\nPostorder Display: \n");
printf("\nName\t|\tSalary");
postorder(root);
printf("\n\n***********************************************************************");
printf("\n***********************************************************************\n\n");
break;
case 3:
printf("\nMaximum Salary");
printf("\nName\t|\tSalary\n");
FindMax(root);
printf("\n");
printf("\nMinimum Salary");
printf("\nName\t|\tSalary\n");
FindMin(root);
printf("\n");
printf("\n\n***********************************************************************");
printf("\n***********************************************************************\n\n");
break;
case 4:
printf("\n-----------------------------------------------------------------------");
printf("\nTotal Monthly Salary: ");
int mon = FindTot(root);
printf("%d", mon);
printf("\n-----------------------------------------------------------------------");
printf("\n\n***********************************************************************");
printf("\n***********************************************************************\n\n");
break;
case 5:
printf("\nSpecify Minimum and Maximum Salary: \t");
scanf("%d %d", &m, &n);
printf("\nName\t|\tSalary\n");
Print(root, m, n);
printf("\n\n***********************************************************************");
printf("\n***********************************************************************\n\n");
break;
}
printf("\nDo you want to continue: \t");
scanf(" %c", &res);
}while(res == 'y');
return 0;
}
---------------------------------------------------------------------------------------------------------------------------
---------------------------------------------------------------------------------------------------------------------------
P6a: Trie
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>
#define ARRAY_SIZE(a) sizeof(a)/sizeof(a[0])
#define ALPHABET_SIZE (26)
#define CHAR_TO_INDEX(c) ((int)c - (int)'a')
#define MAX 100
struct TrieNode
{
struct TrieNode *children[ALPHABET_SIZE];
bool isEndOfWord;
};
struct TrieNode *getNode(void)
{
struct TrieNode *pNode = NULL;
pNode = (struct TrieNode *)malloc(sizeof(struct TrieNode));
if (pNode)
{
int i;
pNode->isEndOfWord = false;
for (i = 0; i < ALPHABET_SIZE; i++)
pNode->children[i] = NULL;
}
return pNode;
}
void insert(struct TrieNode *root, const char *key)
{
int level;
int length = strlen(key);
int index;
struct TrieNode *pCrawl = root;
for (level = 0; level < length; level++)
{
index = CHAR_TO_INDEX(key[level]);
if (!pCrawl->children[index])
pCrawl->children[index] = getNode();
pCrawl = pCrawl->children[index];
}
pCrawl->isEndOfWord = true;
}
void display(struct TrieNode* root, char *str, int level)
{
struct TrieNode *pCrawl = root;
if (pCrawl->isEndOfWord == true)
{
str[level] = '\0';
printf("%s\t",str);
}
int i;
for (i = 0; i < ALPHABET_SIZE; i++)
{
if (pCrawl->children[i])
{
str[level] = i + 'a';
display(pCrawl->children[i], str, level + 1);
}
}
}
bool search(struct TrieNode *root, const char *key)
{
int level;
int length = strlen(key);
int index;
struct TrieNode *pCrawl = root;
for (level = 0; level < length; level++)
{
index = CHAR_TO_INDEX(key[level]);
if (!pCrawl->children[index])
return false;
pCrawl = pCrawl->children[index];
}
return (pCrawl->isEndOfWord);
}
int main()
{
struct TrieNode *root = getNode();
FILE *fptr = NULL;
int i = 0;
char word[MAX] = {0};
char searchword[MAX];
char res;
fptr = fopen("input.txt", "r");
while(fscanf(fptr, "%100s\n", word)!=EOF){
insert(root, &word[i]);
}
fclose(fptr);
//Display
int level = 0;
char str[20];
printf("Content of Trie:\n");
display(root, str, level);
char output[][32] = {"Not present in trie", "Present in trie"};
do
{
printf("\nEnter Word to Search: ");
scanf("%s",searchword);
printf("%s --- %s\n", searchword, output[search(root, searchword)] );
printf("\nDo you want to search more: ");
scanf(" %c", &res);
} while (res=='y');
return 0;
}
P6b: Trie
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define ARRAY_SIZE(a) sizeof(a)/sizeof(a[0])
#define N 26
#define CHAR_TO_INDEX(c) ((int)c - (int)'a')
typedef struct TrieNode
{
struct TrieNode *children[N];
int flag;
}*Tr;
Tr getNode(void)
{
Tr newnode = NULL;
newnode = (struct TrieNode *)malloc(sizeof(struct TrieNode));
if (newnode)
{
int i;
newnode->flag = 0;
for (i = 0; i < N; i++)
newnode->children[i] = NULL;
}
return newnode;
}
void insert(Tr root, const char *word)
{
int i;
int length = strlen(word);
int index;
struct TrieNode *temp = root;
for (i = 0; i < length; i++)
{
index = CHAR_TO_INDEX(word[i]);
if (!temp->children[index])
temp->children[index] = getNode();
temp = temp->children[index];
}
temp->flag = 1;
}
int search(Tr root, char *word)
{
int i;
int length = strlen(word);
int index;
struct TrieNode *temp =root;
for (i = 0; i< length; i++)
{
index = CHAR_TO_INDEX(word[i]);
if (!temp->children[index])
return 0;
temp = temp->children[index];
}
return (temp->flag);
}
int main()
{
char word[][15] = {"and","bat","ball","book","cot","cotton","internet","interview","joy","job","king","lion","man","mango","mango"};
char output[][32] = {"Not present in trie", "Present in trie"};
char word1[][15] = {0};
struct TrieNode *root = getNode();
// Construct trie
FILE* fp;
printf("\nHow many words you have to search: \t");
int n;
scanf("%d", &n);
char word2[30];
int i;
for (i = 0; i < ARRAY_SIZE(word); i++)
insert(root, word[i]);
// Search for different keys
printf("-----------------------------------\n");
printf("-----------------------------------\n");
// fp = fopen("Trie.txt", "r");
// int j=0;
// while (fscanf(fp, "%s/t", word1) == 1)
// {
for(int i=0;i < n; i++)
{
printf("Enter the word: \t");
scanf("%s", word2);
printf("\nPresent\t\t\tNot Present\n");
//printf("%d",(search(root, word1[i])));
if((search(root, word2)) == 1) {
printf("%d) %s\t\t\n", i, word2);
} else printf("%d)\t\t\t%s\n", i, word2);
//printf("%s --- %s\n\n", word1[i],output[search(root, word1[i])] );
printf("\n");
}
return 0;
}
P6c: Trie
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define ARRAY_SIZE(a) sizeof(a)/sizeof(a[0])
#define N 26
#define CHAR_TO_INDEX(c) ((int)c - (int)'a')
typedef struct TrieNode
{
struct TrieNode *children[N];
int flag;
}*Tr;
Tr getNode(void)
{
Tr newnode = NULL;
newnode = (struct TrieNode *)malloc(sizeof(struct TrieNode));
if (newnode)
{
int i;
newnode->flag = 0;
for (i = 0; i < N; i++)
newnode->children[i] = NULL;
}
return newnode;
}
void insert(Tr root, const char *word)
{
int i;
int length = strlen(word);
int index;
struct TrieNode *temp = root;
for (i = 0; i < length; i++)
{
index = CHAR_TO_INDEX(word[i]);
if (!temp->children[index])
temp->children[index] = getNode();
temp = temp->children[index];
}
temp->flag = 1;
}
int search(Tr root, char *word)
{
int i;
int length = strlen(word);
int index;
struct TrieNode *temp =root;
for (i = 0; i< length; i++)
{
index = CHAR_TO_INDEX(word[i]);
if (!temp->children[index])
return 0;
temp = temp->children[index];
}
return (temp->flag);
}
int main()
{
char word[][15] = {"and","bat","ball","book","cot","cotton","internet","interview","joy","job","king","lion","man","mango","mango"};
char output[][32] = {"Not present in trie", "Present in trie"};
char word1[][15] = {0};
struct TrieNode *root = getNode();
// Construct trie
FILE* fp;
int i;
for (i = 0; i < ARRAY_SIZE(word); i++)
insert(root, word[i]);
// Search for different keys
printf("Present\t\t|\tNot Present\n");
printf("-----------------------------------\n");
printf("-----------------------------------\n");
fp = fopen("Trie.txt", "r");
int j=0;
while (fscanf(fp, "%s/t", word1) == 1)
{
for(int i=0;i < ARRAY_SIZE(word1); i++)
{
//printf("%d",(search(root, word1[i])));
if((search(root, word1[i])) == 1) {
printf("%d) %s\t\t|\n", j+1, word1[i]);
} else printf("%d)\t\t|\t%s\n", j+1, word1[i]);
//printf("%s --- %s\n\n", word1[i],output[search(root, word1[i])] );
}
j++;
}
return 0;
}
---------------------------------------------------------------------------------------------------------------------------
---------------------------------------------------------------------------------------------------------------------------
P7: Network Failure
#include<stdio.h>
#include<stdlib.h>
int min(int a,int b)
{
return(a<b?a:b);
}
struct node
{
int val;
struct node* next;
};
struct graph
{
int v;
struct node** arr;
};
struct graph* createGraph(int v)
{
int i;
struct graph* temp =(struct graph*)malloc(sizeof(struct graph));
temp->v=v;
for(i=0;i<v;i++)
temp->arr=(int*)malloc(sizeof(int*)*v);
for(i=0;i<v;i++)
temp->arr[i]=NULL;
return temp;
}
void addEdge(struct graph* g,int u,int v)
{
struct node* temp =(struct node*)malloc(sizeof(struct node));
temp->val = v;
temp->next = g->arr[u];
g->arr[u] = temp;
}
void apUtil(struct graph * g,int node,int* isVisited,int* des,int* parent,int* low,int* ap)
{
struct node* temp=NULL;
static int time=0;
int children=0;
temp = g->arr[node];
isVisited[node]=1;
time++;
//printf("\nsetting time for %d",node);
des[node]=low[node]=time;
while(temp!=NULL)
{
if(!isVisited[temp->val])
{
children++;
parent[temp->val]=node;
apUtil(g,temp->val,isVisited,des,parent,low,ap);
low[node]= min(low[node],low[temp->val]);
if(parent[node]==-1 && children>1)
ap[node]=1;
if(parent[node]!=-1 && des[node]<=low[temp->val])
ap[node]=1;
}
else if(temp->val!=parent[node])
{
low[node]=min(low[node],des[temp->val]);
}
temp= temp->next;
}
//printf("%d",node);
}
void AP(struct graph* g)
{
int i;
int* des = (int*)malloc(sizeof(int)*g->v);
int* isVisited = (int*)malloc(sizeof(int)*g->v);
int* parent = (int*)malloc(sizeof(int)*g->v);
int* low = (int*)malloc(sizeof(int)*g->v);
int* ap = (int*)malloc(sizeof(int)*g->v);
for(i=0;i<g->v;i++)
{
isVisited[i]=0;
parent[i]=-1;
ap[i]=0;
}
for(i=0;i<g->v;i++)
{
if(isVisited[i]==0)
{
apUtil(g,i,isVisited,des,parent,low,ap);
}
}
printf("\n");
int flag=0;
printf("\nPoint of failure in a Network");
for(i=0;i<g->v;i++)
{
if(ap[i]==1)
{
flag=1;
printf("\nVertex : %d",i);
}
}
if(flag==0)
printf("\nNo point found.");
}
int main()
{
int size=0,edges=0,i,u,v;
struct graph* g = createGraph(5);
addEdge(g, 1, 0);
addEdge(g, 0, 2);
addEdge(g, 2, 1);
addEdge(g, 0, 3);
addEdge(g, 3, 4);
AP(g);
}
---------------------------------------------------------------------------------------------------------------------------
---------------------------------------------------------------------------------------------------------------------------
P8a: Graph
#include<bits/stdc++.h>
using namespace std;
class Graph
{
int V; // No. of vertices
list<int> *adj; // Pointer to an array containing adjacency lists
bool isCyclicUtil(int v, bool visited[], bool *rs); // used by isCyclic()
public:
Graph(int V); // Constructor
void addEdge(int v, int w); // to add an edge to graph
bool isCyclic(); // returns true if there is a cycle in this graph
};
Graph::Graph(int V)
{
this->V = V;
adj = new list<int>[V];
}
void Graph::addEdge(int v, int w)
{
adj[v].push_back(w); // Add w to v’s list.
}
// This function is a variation of DFSUtil() in https://www.geeksforgeeks.org/archives/18212
bool Graph::isCyclicUtil(int v, bool visited[], bool *recStack)
{
if(visited[v] == false)
{
// Mark the current node as visited and part of recursion stack
visited[v] = true;
recStack[v] = true;
// Recur for all the vertices adjacent to this vertex
list<int>::iterator i;
for(i = adj[v].begin(); i != adj[v].end(); ++i)
{
if ( !visited[*i] && isCyclicUtil(*i, visited, recStack) )
return true;
else if (recStack[*i])
return true;
}
}
recStack[v] = false; // remove the vertex from recursion stack
return false;
}
// Returns true if the graph contains a cycle, else false.
// This function is a variation of DFS() in https://www.geeksforgeeks.org/archives/18212
bool Graph::isCyclic()
{
// Mark all the vertices as not visited and not part of recursion
// stack
bool *visited = new bool[V];
bool *recStack = new bool[V];
for(int i = 0; i < V; i++)
{
visited[i] = false;
recStack[i] = false;
}
// Call the recursive helper function to detect cycle in different
// DFS trees
for(int i = 0; i < V; i++)
if ( !visited[i] && isCyclicUtil(i, visited, recStack))
return true;
return false;
}
int main()
{
// Create a graph given in the above diagram
Graph g(4);
FILE *fptr;
int vrt;
int wt;
fptr = fopen("nfile.txt", "r");
while(fscanf(fptr, "%d %d", &vrt, &wt)!=EOF)
{
g.addEdge(vrt, wt);
}
fclose(fptr);
if(g.isCyclic())
cout << "Graph contains cycle";
else
cout << "Graph doesn't contain cycle";
return 0;
}
P8b: Cycle
#include<stdio.h>
#include<conio.h>
#include<stdlib.h>
#define MAX 100
#define initial 1
#define visited 2
#define finished 3
void CreateGraph();
void DFS(int v);
void DFSTraversal();
int num;
int state[MAX];
int matrix[MAX][MAX];
void DFSTraversal()
{
int v;
for(v=0;v<num;v++)
{
state[v]=1;
}
//Our Root Vertex Is 0
DFS(0);
for(v=0;v<num;v++)
{
if(state[v]==1)
{
DFS(v);
}
}
printf("Graph Is Acyclic\n");
}
void DFS(int v)
{
int i;
state[v]=2;
for(i=0;i<num;i++)
{
if(matrix[v][i]==1)
{
if(state[i]==1)
{
DFS(i);
}
else if(state[i]==2)
{
printf("Back Edge From %d To %d Found!\n",v,i);
printf("Graph Is Cyclic\n");
exit(1);
}
}
}
state[v]=3;
}
void CreateGraph()
{
int maxedges;
int origin;
int destin;
int i=0;
printf("Enter The Number Of Vertices: ");
scanf("%d",&num);
maxedges=num*(num-1);
for(i=1;i<=maxedges;i++)
{
printf("Enter %d Edge(-1 -1 To Quit): ",i);
scanf("%d %d",&origin,&destin);
if((origin==-1) && (destin==-1))
{
break;
}
if(origin>=num || destin>=num || origin<0 || destin<0)
{
printf("Invalid Edge!\n");
i--;
}
else
{
matrix[origin][destin]=1;
}
}
}
int main()
{
CreateGraph();
DFSTraversal();
return 0;
}
P8c: Cycle from matrix
#include<iostream>
#include<set>
#define NODE 3
using namespace std;
/*
{0, 1, 0, 0, 0},
{0, 0, 0, 0, 0},
{1, 0, 0, 1, 0},
{0, 0, 0, 0, 1},
{0, 0, 1, 0, 0}
*/
int graph[NODE][NODE] = {
{0,1,0},
{0,0,1},
{1,0,0}
};
bool dfs(int curr, set<int>&wSet, set<int>&gSet, set<int>&bSet) {
//moving curr to white set to grey set.
wSet.erase(wSet.find(curr));
gSet.insert(curr);
for(int v = 0; v < NODE; v++) {
if(graph[curr][v] != 0) { //for all neighbour vertices
if(bSet.find(v) != bSet.end())
continue; //if the vertices are in the black set
if(gSet.find(v) != gSet.end())
return true; //it is a cycle
if(dfs(v, wSet, gSet, bSet))
return true; //cycle found
}
}
//moving v to grey set to black set.
gSet.erase(gSet.find(curr));
bSet.insert(curr);
return false;
}
bool hasCycle() {
set<int> wSet, gSet, bSet; //three set as white, grey and black
for(int i = 0; i<NODE; i++)
wSet.insert(i); //initially add all node into the white set
while(wSet.size() > 0) {
for(int current = 0; current < NODE; current++) {
if(wSet.find(current) != wSet.end())
if(dfs(current, wSet, gSet, bSet))
return true;
}
}
return false;
}
int main() {
bool res;
res = hasCycle();
if(res)
cout << "The graph has cycle" << endl;
else
cout << "The graph has no cycle" << endl;
}
