The reverse-delete algorithm is an algorithm in graph theory used to obtain a minimum spanning

tree from a given connected, edge-weighted graph. It first appeared in Kruskal (1956), but it should
not be confused with Kruskal's algorithm which appears in the same paper. If the graph is
disconnected, this algorithm will find a minimum spanning tree for each disconnected part of the
graph. The set of these minimum spanning trees is called a minimum spanning forest, which
contains every vertex in the graph.
This algorithm is a greedy algorithm, choosing the best choice given any situation. It is the reverse
of Kruskal's algorithm, which is another greedy algorithm to find a minimum spanning tree. Kruskals
algorithm starts with an empty graph and adds edges while the Reverse-Delete algorithm starts with
the original graph and deletes edges from it. The algorithm works as follows:
Start with graph G, which contains a list of edges E.
Go through E in decreasing order of edge weights.
For each edge, check if deleting the edge will further disconnect the graph.
Perform any deletion that does not lead to additional disconnection.

Algorithm
1 function ReverseDelete(edges[] E)
2 sort E in decreasing order
3 Define an index i 0
4 while i < size(E)
5 Define edge E[i]
6 delete E[i]
7 if edge.v1 is not connected to edge.v2
8 E[i] edge
9 i i + 1
10 return edges[] E

Example[edit]
In the following example green edges are being evaluated by the algorithm and red edges have
been deleted.

This is our original graph. The numbers near the edges indicate
their edge weight.

The algorithm will start with the maximum weighted edge, which in
this case is DE with an edge weight of 15. Since deleting edge DE
does not further disconnect the graph it is deleted.

The next largest edge is FG so the algorithm will check if deleting
this edge will further disconnect the graph. Since deleting the
edge will not further disconnect the graph, the edge is then
deleted.

The next largest edge is edge BD so the algorithm will check this
edge and delete the edge.

The next edge to check is edge EG, which will not be deleted
since it would disconnect node G from the graph. Therefore, the
next edge to delete is edge BC.

The next largest edge is edge EF so the algorithm will check this
edge and delete the edge.

The algorithm will then search the remaining edges and will not
find another edge to delete; therefore this is the final graph
returned by the algorithm.



C Program to Implement two Stacks using
a Single Array & Check for Overflow &
Underflow
This C Program Implements two Stacks using a Single Array & Check for Overflow & Underflow. A
Stack is a linear data structure in which a data item is inserted and deleted at one record. A stack is
called a Last In First Out (LIFO) structure. Because the data item inserted last is the data item
deleted first from the stack.
To implement two stacks in one array, there can be two methods.
First is to divide the array in to two equal parts and then give one half two each stack. But this
method wastes space.
So a better way is to let the two stacks to push elements by comparing tops of each other, and not
up to one half of the array.
Push and Pop functions of both stack in the following code has their Time Complexity as O(1). They
take constant time.
Print is O(n), where n is the number of elements in the stack.
The program has an array of size 10. 6 values are pushed in stack 1 and 4 in two. All conditions are
being checked.
Here is source code of the C Program to Implement two Stacks using a Single Array & Check for
Overflow & Underflow. The C program is successfully compiled and run on gcc-4.3.2 on a Linux
system. The program output is also shown below.
1. //This is a C Program to Implement two Stacks using a Single Array & Check for Overflow & Underflow
2. #include <stdio.h>
3. #define SIZE 10
4.
5.
6. int ar[SIZE];
7. int top1 = -1;
8. int top2 = SIZE;
9.
10. //Functions to push data
11. void push_stack1 (int data)
12. {
13. if (top1 < top2 - 1)
14. {
15. ar[++top1] = data;
16. }
17. else
18. {
19. printf ("Stack Full! Cannot Push\n");
20. }
21. }
22. void push_stack2 (int data)
23. {
24. if (top1 < top2 - 1)
25. {
26. ar[--top2] = data;
27. }
28. else
29. {
30. printf ("Stack Full! Cannot Push\n");
31. }
32. }
33.
34. //Functions to pop data
35. void pop_stack1 ()
36. {
37. if (top1 >= 0)
38. {
39. int popped_value = ar[top1--];
40. printf ("%d is being popped from Stack 1\n", popped_value);
41. }
42. else
43. {
44. printf ("Stack Empty! Cannot Pop\n");
45. }
46. }
47. void pop_stack2 ()
48. {
49. if (top2 < SIZE)
50. {
51. int popped_value = ar[top2++];
52. printf ("%d is being popped from Stack 2\n", popped_value);
53. }
54. else
55. {
56. printf ("Stack Empty! Cannot Pop\n");
57. }
58. }
59.
60. //Functions to Print Stack 1 and Stack 2
61. void print_stack1 ()
62. {
63. int i;
64. for (i = top1; i >= 0; --i)
65. {
66. printf ("%d ", ar[i]);
67. }
68. printf ("\n");
69. }
70. void print_stack2 ()
71. {
72. int i;
73. for (i = top2; i < SIZE; ++i)
74. {
75. printf ("%d ", ar[i]);
76. }
77. printf ("\n");
78. }
79.
80. int main()
81. {
82. int ar[SIZE];
83. int i;
84. int num_of_ele;
85.
86. printf ("We can push a total of 10 values\n");
87.
88. //Number of elements pushed in stack 1 is 6
89. //Number of elements pushed in stack 2 is 4
90.
91. for (i = 1; i <= 6; ++i)
92. {
93. push_stack1 (i);
94. printf ("Value Pushed in Stack 1 is %d\n", i);
95. }
96. for (i = 1; i <= 4; ++i)
97. {
98. push_stack2 (i);
99. printf ("Value Pushed in Stack 2 is %d\n", i);
100. }
101.
102. //Print Both Stacks
103. print_stack1 ();
104. print_stack2 ();
105.
106. //Pushing on Stack Full
107. printf ("Pushing Value in Stack 1 is %d\n", 11);
108. push_stack1 (11);
109.
110. //Popping All Elements From Stack 1
111. num_of_ele = top1 + 1;
112. while (num_of_ele)
113. {
114. pop_stack1 ();
115. --num_of_ele;
116. }
117.
118. //Trying to Pop From Empty Stack
119. pop_stack1 ();
120.
121. return 0;
122. }

We can push a total of 10 values
Value Pushed in Stack 1 is 1
Value Pushed in Stack 1 is 2
Value Pushed in Stack 1 is 3
Value Pushed in Stack 1 is 4
Value Pushed in Stack 1 is 5
Value Pushed in Stack 1 is 6
Value Pushed in Stack 2 is 1
Value Pushed in Stack 2 is 2
Value Pushed in Stack 2 is 3
Value Pushed in Stack 2 is 4
6 5 4 3 2 1
4 3 2 1
Pushing Value in Stack 1 is 11
Stack Full! Cannot Push
6 is being popped from Stack 1
5 is being popped from Stack 1
4 is being popped from Stack 1
3 is being popped from Stack 1
2 is being popped from Stack 1
1 is being popped from Stack 1
Stack Empty! Cannot Pop






Write an algorithm for the implementation of Circular Doubly Linked Lists.

#include<stdio.h>
struct node
{
int data;
struct node *next;
struct node *prev;
};
typedef struct node node; //with this Use node instead of struct node
node *root=NULL; //Global variable root pointer
node *create_node(int); //Declaration
void insert(int); //Declaration
void display_list(node *); //Declaration
void display_list_rev(node *);
void main()
{
clrscr();
display_list(root);
insert(10);
insert(20);
insert(30);
insert(40);
display_list(root);
display_list_rev(root);
getch();
}
node *create_node(int x)
{
node *temp;
temp=(node*)malloc(sizeof(node));
temp->data=x;
temp->next=NULL;
temp->prev=NULL;
return temp;
}
void insert(int x)
{
node *start;
start=root;
if(root==NULL)
{ root=create_node(x);root->next=root;root->prev=root;}
else
{
while(start->next!=root)
{
start=start->next;
} start->next=create_node(x);
start->next->next=root;
start->next->prev=start;
}
}
void display_list(node *start)
{
printf(\nLink List :-\n);
if(start==NULL)
{ printf(List is Empty!\n); }
else
{
while(start->next!=root)
{ printf(%d->,start->data);
start=start->next;
}printf(%d->,start->data);
}
}
void display_list_rev(node *start)
{
printf(\n\nLink List (Reverse):-\n);
if(start==NULL)
{ printf(List is Empty!\n); }
else
{ while(start->next!=root)
{
start=start->next;
}
while(start->prev!=root)
{ printf(%d->,start->data);
start=start->prev;
}printf(%d->,start->data);
start=start->prev;
printf(%d->,start->data);
}
}