Tuesday, 6 November 2012
Monday, 29 October 2012
GUI & DBMS Viva faq
Chapter 1: Database Concepts and
Systems
What is Database?
What is DBMS?
Advantages of DBMS over file systems.
What is data model?
What is DDL?
What is DML?
List different types of database users.
What are functions of database
administrator?
Chapter 2: E-R Model
What is Entity?
What is Entity Set?
Difference between entity and entity
set.
List different types of attributes.
What is domain?
What is Relationship?
What is Relationship Set?
What is Cardinality ratio?
What do you mean by total
participation?
What do you mean by partial
participation?
What is Super key?
What is Candidate key?
What is Primary key?
What is E-R diagram?
How to draw basic components of E-R
diagram.
What is Strong Entity Set?
What is Weak Entity Set?
How to draw Weak Entity Set using E-R
diagram?
What is Generalization?
What is Specialization?
What is Aggregation?
Chapter 2: Relational Model
What is Tuple?
What is Attribute?
What is Relation?
What is Domain?
What is Primary key?
What is Foreign key?
What is Referential Integrity?
What is Relational Algebra? (Check All
operators i.e. select, project, rename, etc.)
What is SQL?
What is DDL? Give one example.
What is DML? Give one example.
What is DCL? Give one example.
What is basic structure of SELECT
query?
Which are different aggregate functions
used in SQL? Give example.
What is Join? Which are different types
of joins in SQL?
Write INNER JOIN syntax.
Write (LEFT, RIGHT, FULL) OUTER JOIN
syntax.
What is View? How to create a View?
Chapter 4: Transaction
What is Transaction?
What are ACID properties of
transaction? Explain each property.
Draw transaction state diagram and
explain.
Why concurrent execution is preferred?
What is Schedule?
What is Serial Schedule?
What is Serializable Schedule?
What is Serializability?
What are conflicting operations?
What is Conflict Equivalence?
What is Conflict Serializability?
What is View Equivalence?
What is View Serializability?
How to draw precedence graph?
What is recoverable schedule?
When the schedule is unrecoverable?
What is cascadeless schedule?
Which are different isolation levels?
What is TCL? Give one example.
Chapter 5: Concurrency Control
What is concurrency control?
What types of locks are used in lock
based protocols?
Explain two phase locking protocol.
Give advantages of two phase locking
protocol.
Give disadvantages of two phase locking
protocol.
What are different variations of two
phase locking protocol.
What is deadlock?
How to avoid deadlock?
What is wait-die scheme?
What is wound-wait scheme?
How to draw wait for graph?
Explain timestamp based protocol.
Explain validation based protocol.
Explain graph based protocol.
Chapter 6: Recovery System
Which are different types of failures?
Explain log based recovery.
Explain check point based recovery.
Explain shadow paging.
Chapter 7: GUI
What is Murphy’s law of GUI? Give one
example.
What are features of GUI?
What are the standards used for GUI?
Whatare design considerations of GUI?
Chapter 8: Visual Programming
What are intrinsic controls in VB? Give
example.
What are Extrinsic controls in VB? Give
example.
What is significance of Option
Explicit?
What is SDI and MDI?
What is OLE?
What are AciveX Conrols in VB?
What is ADO?
Give different naming conventions for
Text box, label, checkbox, combo box, option
button controls.
What is ODBC?
What is the use of msgbox and input box
in VB?
Saturday, 27 October 2012
Important SQL syntax for practical exam
i. Create table command
Syntax:
Create table TableName(attribute1 data type(size), attribute2 data type(size), attribute3 data type(size),……);
ii. Alter table command
a. Add Command
Syntax:
Alter table TableName
Add attribute data type(size);
b. Modify Command
Syntax :
Alter table TableName
Modify ( attribute data type(size));
iii. Drop Table Command
Syntax:
Drop table TableName;
iv. Truncate table command
Syntax:
Truncate table TableName;
v. Rename Table Command
Syntax:
Rename NewTableName, OldTableName ;
vi. Comment Command
Comment - Add comments to the data dictionary
2. DML(Data Manipulation Language):
i. Select Command
Syntax: select attribute1,attribute2 from TableName;
ii. Insert Command
Syntax :
insert into TableName values('Value1', 'value2', Value3);
iii.Update Command
Syntax:
Update TableNameattributeName=value
Where Condition;
iv. Delete Command
Syntax:
delete from Tablename where Condition;
1. The AVG() Function
Syntax:
Select Avg(Attribute) from TableName
2. TheCOUNT() Function
Syntax
SELECT COUNT(Attribute) FROM TableName
i. SQL COUNT(*) Syntax
SELECT COUNT(*) FROM table_name
ii. SQL COUNT(DISTINCT column_name) Syntax
SELECT COUNT(DISTINCT column_name) FROM table_name
4.The SUM() Function
SQL SUM() Syntax
SELECT SUM(column_name) FROM table_name
5.The MIN() Function
SQL MIN() Syntax
SELECT MIN(column_name) FROM table_name
6. The MAX() Function
SQL MAX() Syntax
SELECT MAX(column_name) FROM table_name
1. The Where Clause
Syntax:
SELECT column_name(s)
FROM table_name
WHERE column_name operator value
2. The Group by clause
Syntax:
SELECT column_name, aggregate_function(column_name)
FROM table_name
WHERE column_name operator value
GROUP BY column_name
3. The Having Clause
Syntax:
SELECT column_name, aggregate_function(column_name)
FROM table_name
WHERE column_name operator value
GROUP BY column_name
HAVING aggregate_function(column_name) operator value
4. The Order by clause
Syntax:
SELECT column_name(s)
FROM table_name
ORDER BY column_name(s) ASC|DESC
1. SQL INNER JOIN:
SQL INNER JOIN Syntax:
SELECT column_name(s)
FROM table_name1
INNER JOIN table_name2
ON table_name1.column_name=table_name2.column_name;
.
2. SQL LEFT JOIN:
SQL LEFT JOIN Syntax:
SELECT column_name(s)
FROM table_name1
LEFT JOIN table_name2
ON table_name1.column_name=table_name2.column_name;
3. SQL RIGHT JOIN:
SQL RIGHT JOIN Syntax:
SELECT column_name(s)
FROM table_name1
RIGHT JOIN table_name2
ON table_name1.column_name=table_name2.column_name;
4. SQL FULL JOIN:
SQL FULL JOIN Syntax:
SELECT column_name(s)
FROM table_name1
FULL JOIN table_name2
ON table_name1.column_name=table_name2.column_name;
• SQL CREATE VIEW Syntax:
CREATE VIEW view_name AS
SELECT column_name(s)
FROM table_name
WHERE condition;
• SQL Updating a View:
SQL CREATE OR REPLACE VIEW Syntax:
CREATE OR REPLACE VIEW view_name AS
SELECT column_name(s)
FROM table_name
WHERE condition:
• SQL Dropping a View:
SQL DROP VIEW Syntax:
DROP VIEW view_name;
\
Saturday, 20 October 2012
Program to implement Binary tree
class BinaryTreeExample
{
public static
void main(String[] args)
{
new
BinaryTreeExample().run();
}
static class Node
{
Node left;
Node right;
int value;
public Node(int
value)
{
this.value = value;
}
}
public void run() {
Node rootnode = new
Node(25);
System.out.println("Building tree with rootvalue
" +
rootnode.value);
System.out.println("===============================");
insert(rootnode,
11);
insert(rootnode,
15);
insert(rootnode,
16);
insert(rootnode,
23);
insert(rootnode,
79);
System.out.println("Traversing tree in order");
System.out.println("=================================");
printInOrder(rootnode);
}
public void
insert(Node node, int value) {
if (value <
node.value) {
if (node.left !=
null) {
insert(node.left,
value);
}
Else
{
System.out.println("
Inserted " + value +
" to left of
node " + node.value);
node.left = new
Node(value);
}
} else if (value
> node.value) {
if (node.right !=
null) {
insert(node.right,
value);
} else {
System.out.println("
Inserted " + value + "
to right of node
" + node.value);
node.right = new
Node(value);
}
}
}
public void
printInOrder(Node node) {
if (node != null) {
printInOrder(node.left);
System.out.println("
Traversed " + node.value);
printInOrder(node.right);
}
}
}
Output of the program
Building tree with
root value 25
=================================
Inserted 11 to left
of node 25
Inserted 15 to right
of node 11
Inserted 16 to right
of node 15
Inserted 23 to right
of node 16
Inserted 79 to right
of node 25
Traversing tree in order
Traversed 11
Traversed 15
Traversed 16
Traversed 23
Traversed 25
Traversed 79
Thursday, 18 October 2012
demonstrate Hash
/* Program to demonstrate Hash Table with Double Hashing */
import java.io.IOException;
public class HashTableWithDoubleHashing
{
private DataItem[] hashArray;
private int arraySize;
private DataItem bufItem; // for deleted items
HashTableWithDoubleHashing(int size)
{
arraySize = size;
hashArray = new DataItem[arraySize];
bufItem = new DataItem(-1);
}
//--------------------------------------------------------------------------------------------------------------------
public void displayTable()
{
System.out.print("Table: ");
for (int j = 0; j < arraySize; j++) {
if (hashArray[j] != null)
System.out.print(hashArray[j].getKey() + " ");
else
System.out.print("** ");
}
System.out.println("");
}
//--------------------------------------------------------------------------------------------------------------------
public int hashFunc1(int key)
{
return key % arraySize;
}
//--------------------------------------------------------------------------------------------------------------------
public int hashFunc2(int key)
{
return 6 - key % 6;
}
//--------------------------------------------------------------------------------------------------------------------
public void insert(int key, DataItem item)
{
int hashVal = hashFunc1(key); // hash the key
int stepSize = hashFunc2(key); // get step size
// until empty cell or –1
while (hashArray[hashVal] != null && hashArray[hashVal].getKey() != -1)
{
hashVal += stepSize; // add the step
hashVal %= arraySize; // for wraparound
}
hashArray[hashVal] = item; // insert item
}
//--------------------------------------------------------------------------------------------------------------------
public DataItem delete(int key)
{
int hashVal = hashFunc1(key);
int stepSize = hashFunc2(key); // get step size
while (hashArray[hashVal] != null)
{
if (hashArray[hashVal].getKey() == key)
{
DataItem temp = hashArray[hashVal]; // save item
hashArray[hashVal] = bufItem; // delete item
return temp; // return item
}
hashVal += stepSize; // add the step
hashVal %= arraySize; // for wraparound
}
return null; // can't find item
}
//--------------------------------------------------------------------------------------------------------------------
public DataItem find(int key)
{
int hashVal = hashFunc1(key); // hash the key
int stepSize = hashFunc2(key); // get step size
while (hashArray[hashVal] != null)
{
if (hashArray[hashVal].getKey() == key)
return hashArray[hashVal]; // yes, return item
hashVal += stepSize; // add the step
hashVal %= arraySize; // for wraparound
}
return null; // can't find item
}
//--------------------------------------------------------------------------------------------------------------------
public static void main(String[] args) throws IOException
{
int aKey;
DataItem aDataItem;
int size, initSize;
size = 100;
initSize = 10;
HashTableWithDoubleHashing theHashTable = new HashTableWithDoubleHashing(size);
for (int i = 0; i < initSize; i++)
{
aKey = (int) (java.lang.Math.random() * 2 * size);
aDataItem = new DataItem(aKey);
theHashTable.insert(aKey, aDataItem);
}
theHashTable.displayTable();
aKey = 100;
aDataItem = new DataItem(aKey);
theHashTable.insert(aKey, aDataItem);
aKey = 163;
theHashTable.delete(aKey);
aKey = 100;
aDataItem = theHashTable.find(aKey);
if (aDataItem != null)
System.out.println("Found " + aKey);
else
System.out.println("Could not find " + aKey);
}
}
//--------------------------------------------------------------------------------------------------------------------
class DataItem
{
private int data;
public DataItem(int i)
{
data = i;
}
public int getKey()
{
return data;
}
}
/*
Output :
Table: ** ** ** ** ** ** ** ** 108 ** ** ** ** ** 114 115 16 ** ** ** ** ** 22 *
* ** ** 122 ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** 42 ** ** ** ** ** ** **
** ** 152 ** ** 155 ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** 73 ** **
** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** **
Found 100
*/
import java.io.IOException;
public class HashTableWithDoubleHashing
{
private DataItem[] hashArray;
private int arraySize;
private DataItem bufItem; // for deleted items
HashTableWithDoubleHashing(int size)
{
arraySize = size;
hashArray = new DataItem[arraySize];
bufItem = new DataItem(-1);
}
//--------------------------------------------------------------------------------------------------------------------
public void displayTable()
{
System.out.print("Table: ");
for (int j = 0; j < arraySize; j++) {
if (hashArray[j] != null)
System.out.print(hashArray[j].getKey() + " ");
else
System.out.print("** ");
}
System.out.println("");
}
//--------------------------------------------------------------------------------------------------------------------
public int hashFunc1(int key)
{
return key % arraySize;
}
//--------------------------------------------------------------------------------------------------------------------
public int hashFunc2(int key)
{
return 6 - key % 6;
}
//--------------------------------------------------------------------------------------------------------------------
public void insert(int key, DataItem item)
{
int hashVal = hashFunc1(key); // hash the key
int stepSize = hashFunc2(key); // get step size
// until empty cell or –1
while (hashArray[hashVal] != null && hashArray[hashVal].getKey() != -1)
{
hashVal += stepSize; // add the step
hashVal %= arraySize; // for wraparound
}
hashArray[hashVal] = item; // insert item
}
//--------------------------------------------------------------------------------------------------------------------
public DataItem delete(int key)
{
int hashVal = hashFunc1(key);
int stepSize = hashFunc2(key); // get step size
while (hashArray[hashVal] != null)
{
if (hashArray[hashVal].getKey() == key)
{
DataItem temp = hashArray[hashVal]; // save item
hashArray[hashVal] = bufItem; // delete item
return temp; // return item
}
hashVal += stepSize; // add the step
hashVal %= arraySize; // for wraparound
}
return null; // can't find item
}
//--------------------------------------------------------------------------------------------------------------------
public DataItem find(int key)
{
int hashVal = hashFunc1(key); // hash the key
int stepSize = hashFunc2(key); // get step size
while (hashArray[hashVal] != null)
{
if (hashArray[hashVal].getKey() == key)
return hashArray[hashVal]; // yes, return item
hashVal += stepSize; // add the step
hashVal %= arraySize; // for wraparound
}
return null; // can't find item
}
//--------------------------------------------------------------------------------------------------------------------
public static void main(String[] args) throws IOException
{
int aKey;
DataItem aDataItem;
int size, initSize;
size = 100;
initSize = 10;
HashTableWithDoubleHashing theHashTable = new HashTableWithDoubleHashing(size);
for (int i = 0; i < initSize; i++)
{
aKey = (int) (java.lang.Math.random() * 2 * size);
aDataItem = new DataItem(aKey);
theHashTable.insert(aKey, aDataItem);
}
theHashTable.displayTable();
aKey = 100;
aDataItem = new DataItem(aKey);
theHashTable.insert(aKey, aDataItem);
aKey = 163;
theHashTable.delete(aKey);
aKey = 100;
aDataItem = theHashTable.find(aKey);
if (aDataItem != null)
System.out.println("Found " + aKey);
else
System.out.println("Could not find " + aKey);
}
}
//--------------------------------------------------------------------------------------------------------------------
class DataItem
{
private int data;
public DataItem(int i)
{
data = i;
}
public int getKey()
{
return data;
}
}
/*
Output :
Table: ** ** ** ** ** ** ** ** 108 ** ** ** ** ** 114 115 16 ** ** ** ** ** 22 *
* ** ** 122 ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** 42 ** ** ** ** ** ** **
** ** 152 ** ** 155 ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** 73 ** **
** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** **
Found 100
*/
Wednesday, 17 October 2012
Binary Search Tree
//Prog For BST
import java.io.*;
import java.util.*;
class Nodetype
{
int info;
Nodetype left;
Nodetype right;
Nodetype(int i)
{
info=i;
left=null;
right=null;
}
}
class Functions
{
Nodetype tree;
Nodetype maketree(int x)
{
Nodetype node=new Nodetype(x);
return(node);
}/*end maketree*/
void setleft(Nodetype p,int x)
{
if(p==null)
System.out.println("\nInvalid insertion");
else
if(p.left!=null)
System.out.println("\nInvalid insertion");
else
p.left=maketree(x);
}/*end setleft*/
void setright(Nodetype p,int x)
{
if(p==null)
System.out.println("\nInvalid insertion");
else
if(p.right!=null)
System.out.println("\nInvalid insertion");
else
p.right=maketree(x);
}/*end setright*/
void intrav(Nodetype ptree)
{
if(ptree!=null)
{
intrav(ptree.left);
System.out.print(ptree.info+" ");
intrav(ptree.right);
}
}/*end intrav*/
void deletee(int key)
{
Nodetype p,q,f,s,rp;
p=tree;
q=null;
while(p!=null && p.info!=key)
{
q=p;
p=(key < p.info)? p.left: p.right;
}
if(p==null)
return;
if(p.left==null)
rp=p.right;
else
if(p.right==null)
rp=p.left;
else
{
f=p;
rp=p.right;
s=rp.left;
while(s!=null)
{
f=rp;
rp=s;
s=rp.left;
}
if(f!=p)
{
f.left=rp.right;
rp.right=p.right;
}
rp.left=p.left;
}
if(q==null)
tree=rp;
else
if(p==(q.left))
(q.left)=rp;
else
(q.right)=rp;
System.out.println("\n...........number deleted");
System.out.println("\nInorder : ");
intrav(tree);
return;
}/*end deletee*/
void insert(int key)
{
Nodetype v,p,q;
q=null;
p=tree;
while(p!=null)
{
if(key==p.info)
{
System.out.println("Sorry !....."+key+" is a duplicate\n");
return;
}
q=p;
if(key<p.info)
p=p.left;
else
p=p.right;
}
v=maketree(key);
if(q==null)
tree=v;
else
if(key<q.info)
q.left=v;
else
q.right=v;
System.out.println("\nInorder : ");
intrav(tree);
}/*end insert*/
void search(int key)
{
Nodetype p;
p=tree;
while((p!=null) && (key!=p.info))
p=(key<p.info)? p.left:p.right;
if(p==null)
{
System.out.println("\nNumber not Found!...........");
return;
}
if(key==p.info)
System.out.println("\nNumber Found!...........");
System.out.print("\nInorder : ");
intrav(tree);
}/*end search*/
void create()
{
int num,ch,ans=1;
do
{
System.out.println("\n1.Insert");
System.out.println("\n2.Search");
System.out.println("\n3.Delete");
System.out.print("\nEnter your choice : ");
ch=getNumber();
switch(ch)
{
case 1: System.out.print("\nEnter number to be inserted : ");
num=getNumber();
insert(num);
break;
case 2: System.out.print("\nEnter number to be searched : ");
num=getNumber();
search(num);
break;
case 3: System.out.print("\nEnter number to be deleted : ");
num=getNumber();
deletee(num);
break;
default:System.out.print("\nWrong choice");
}
System.out.print("\nDo you want to continue(1/0) : ");
ans=getNumber();
}
while(ans==1);
}/*end create*/
int getNumber()
{
String str;
int ne=0;
InputStreamReader input=new InputStreamReader(System.in);
BufferedReader in=new BufferedReader(input);
try
{
str=in.readLine();
ne=Integer.parseInt(str);
}
catch(Exception e)
{
System.out.println("I/O Error");
}
return ne;
}/*end getnumber*/
}
class BST
{
public static void main(String main[])
{
Functions f=new Functions();
f.create();
}/*end main*/
}
/*
Sample Input and Output :
1.Insert
2.Search
3.Delete
Enter your choice : 1
Enter number to be inserted : 10
Inorder : 10
Do you want to continue(1/0) : 1
1.Insert
2.Search
3.Delete
Enter your choice : 1
Enter number to be inserted : 50
Inorder : 10 50
Do you want to continue(1/0) : 1
1.Insert
2.Search
3.Delete
Enter your choice : 1
Enter number to be inserted : 5
Inorder : 5 10 50
Do you want to continue(1/0) : 1
1.Insert
2.Search
3.Delete
Enter your choice : 2
Enter number to be searched : 100
Number not Found!...........
Do you want to continue(1/0) : 1
1.Insert
2.Search
3.Delete
Enter your choice : 1
Enter number to be inserted : 100
Inorder : 5 10 50 100
Do you want to continue(1/0) : 1
1.Insert
2.Search
3.Delete
Enter your choice : 2
Enter number to be searched : 100
Number Found!...........
Inorder : 5 10 50 100
Do you want to continue(1/0) : 1
1.Insert
2.Search
3.Delete
Enter your choice : 1
Enter number to be inserted : 40
Inorder : 5 10 40 50 100
Do you want to continue(1/0) : 1
1.Insert
2.Search
3.Delete
Enter your choice : 1
Enter number to be inserted : 30
Inorder : 5 10 30 40 50 100
Do you want to continue(1/0) : 1
1.Insert
2.Search
3.Delete
Enter your choice : 3
Enter number to be deleted : 50
...........number deleted
Inorder : 5 10 30 40 100
Do you want to continue(1/0) : 1
1.Insert
2.Search
3.Delete
Enter your choice : 3
Enter number to be deleted : 40
...........number deleted
Inorder : 5 10 30 100
Do you want to continue(1/0) : 1
1.Insert
2.Search
3.Delete
Enter your choice : 1
Enter number to be inserted : 45
Inorder : 5 10 30 45 100
Do you want to continue(1/0) : 1
1.Insert
2.Search
3.Delete
Enter your choice : 2
Enter number to be searched : 50
Number not Found!...........
Do you want to continue(1/0) : 0
*/
Tuesday, 21 August 2012
To implement Kruskal’s algorithm.
import java.io.*;
import java.util.*;
class Graph
{
int i,n; //no of nodes
int noe; //no edges in the graph
int graph_edge[][]=new int[100][4];
int tree[][]=new int [10][10];
int sets[][]=new int[100][10];
int top[]=new int[100];
int cost=0;
int getNumber()
{
String str;
int ne=0;
InputStreamReader input=new InputStreamReader(System.in);
BufferedReader in=new BufferedReader(input);
try
{
str=in.readLine();
ne=Integer.parseInt(str);
}
catch(Exception e)
{
System.out.println("I/O Error");
}
return ne;
}/*end getNumber*/
void read_graph()
{
System.out.print("Enter the no. of nodes in the undirected weighted graph ::");
n=getNumber();
noe=0;
System.out.println("Enter the weights for the following edges ::\n");
for(int i=1;i<=n;i++)
{
for(int j=i+1;j<=n;j++)
{
System.out.print(" < "+i+" , "+j+" > ::");
int w;
w=getNumber();
if(w!=0)
{
noe++;
graph_edge[noe][1]=i;
graph_edge[noe][2]=j;
graph_edge[noe][3]=w;
}
}
}
}
void sort_edges()
{
/**** Sort the edges using bubble sort in increasing order**************/
for(int i=1;i<=noe-1;i++)
{
for(int j=1;j<=noe-i;j++)
{
if(graph_edge[j][3]>graph_edge[j+1][3])
{
int t=graph_edge[j][1];
graph_edge[j][1]=graph_edge[j+1][1];
graph_edge[j+1][1]=t;
t=graph_edge[j][2];
graph_edge[j][2]=graph_edge[j+1][2];
graph_edge[j+1][2]=t;
t=graph_edge[j][3];
graph_edge[j][3]=graph_edge[j+1][3];
graph_edge[j+1][3]=t;
}
}
}
}
void algorithm()
{
// ->make a set for each node
for(int i=1;i<=n;i++)
{
sets[i][1]=i;
top[i]=1;
}
System.out.println("\nThe algorithm starts ::\n\n");
for(i=1;i<=noe;i++)
{
int p1=find_node(graph_edge[i][1]);
int p2=find_node(graph_edge[i][2]);
if(p1!=p2)
{
System.out.print("The edge included in the tree is ::");
System.out.print("< "+graph_edge[i][1]+" , ");
System.out.println(graph_edge[i][2]+" > ");;
cost=cost+graph_edge[i][3];
tree[graph_edge[i][1]][graph_edge[i][2]]=graph_edge[i][3];
tree[graph_edge[i][2]][graph_edge[i][1]]=graph_edge[i][3];
// Mix the two sets
for(int j=1;j<=top[p2];j++)
{
top[p1]++;
sets[p1][top[p1]]=sets[p2][j];
}
top[p2]=0;
}
else
{
System.out.println("Inclusion of the edge ");
System.out.print(" < "+graph_edge[i][1]+" , ");
System.out.println(graph_edge[i][2]+"> forms a cycle so it is removed\n\n");
}
}
System.out.println("Cost of the spanning tree : "+cost);
}
int find_node(int n)
{
for(int i=1;i<=noe;i++)
{
for(int j=1;j<=top[i];j++)
{
if(n==sets[i][j])
return i;
}
}
return -1;
}
}
class Kruskal1
{
public static void main(String args[])
{
Graph obj=new Graph();
obj.read_graph();
obj.sort_edges();
obj.algorithm();
}
}
/*
Enter the no. of nodes in the undirected weighted graph ::6
Enter the weights for the following edges ::
< 1 , 2 > ::3
< 1 , 3 > ::1
< 1 , 4 > ::6
< 1 , 5 > ::0
< 1 , 6 > ::0
< 2 , 3 > ::5
< 2 , 4 > ::0
< 2 , 5 > ::3
< 2 , 6 > ::0
< 3 , 4 > ::5
< 3 , 5 > ::6
< 3 , 6 > ::4
< 4 , 5 > ::0
< 4 , 6 > ::2
< 5 , 6 > ::6
The algorithm starts ::
The edge included in the tree is ::< 1 , 3 >
The edge included in the tree is ::< 4 , 6 >
The edge included in the tree is ::< 1 , 2 >
The edge included in the tree is ::< 2 , 5 >
The edge included in the tree is ::< 3 , 6 >
Inclusion of the edge
< 2 , 3> forms a cycle so it is removed
Inclusion of the edge
< 3 , 4> forms a cycle so it is removed
Inclusion of the edge
< 1 , 4> forms a cycle so it is removed
Inclusion of the edge
< 3 , 5> forms a cycle so it is removed
Inclusion of the edge
< 5 , 6> forms a cycle so it is removed
Cost of the spanning tree : 13
*/
import java.util.*;
class Graph
{
int i,n; //no of nodes
int noe; //no edges in the graph
int graph_edge[][]=new int[100][4];
int tree[][]=new int [10][10];
int sets[][]=new int[100][10];
int top[]=new int[100];
int cost=0;
int getNumber()
{
String str;
int ne=0;
InputStreamReader input=new InputStreamReader(System.in);
BufferedReader in=new BufferedReader(input);
try
{
str=in.readLine();
ne=Integer.parseInt(str);
}
catch(Exception e)
{
System.out.println("I/O Error");
}
return ne;
}/*end getNumber*/
void read_graph()
{
System.out.print("Enter the no. of nodes in the undirected weighted graph ::");
n=getNumber();
noe=0;
System.out.println("Enter the weights for the following edges ::\n");
for(int i=1;i<=n;i++)
{
for(int j=i+1;j<=n;j++)
{
System.out.print(" < "+i+" , "+j+" > ::");
int w;
w=getNumber();
if(w!=0)
{
noe++;
graph_edge[noe][1]=i;
graph_edge[noe][2]=j;
graph_edge[noe][3]=w;
}
}
}
}
void sort_edges()
{
/**** Sort the edges using bubble sort in increasing order**************/
for(int i=1;i<=noe-1;i++)
{
for(int j=1;j<=noe-i;j++)
{
if(graph_edge[j][3]>graph_edge[j+1][3])
{
int t=graph_edge[j][1];
graph_edge[j][1]=graph_edge[j+1][1];
graph_edge[j+1][1]=t;
t=graph_edge[j][2];
graph_edge[j][2]=graph_edge[j+1][2];
graph_edge[j+1][2]=t;
t=graph_edge[j][3];
graph_edge[j][3]=graph_edge[j+1][3];
graph_edge[j+1][3]=t;
}
}
}
}
void algorithm()
{
// ->make a set for each node
for(int i=1;i<=n;i++)
{
sets[i][1]=i;
top[i]=1;
}
System.out.println("\nThe algorithm starts ::\n\n");
for(i=1;i<=noe;i++)
{
int p1=find_node(graph_edge[i][1]);
int p2=find_node(graph_edge[i][2]);
if(p1!=p2)
{
System.out.print("The edge included in the tree is ::");
System.out.print("< "+graph_edge[i][1]+" , ");
System.out.println(graph_edge[i][2]+" > ");;
cost=cost+graph_edge[i][3];
tree[graph_edge[i][1]][graph_edge[i][2]]=graph_edge[i][3];
tree[graph_edge[i][2]][graph_edge[i][1]]=graph_edge[i][3];
// Mix the two sets
for(int j=1;j<=top[p2];j++)
{
top[p1]++;
sets[p1][top[p1]]=sets[p2][j];
}
top[p2]=0;
}
else
{
System.out.println("Inclusion of the edge ");
System.out.print(" < "+graph_edge[i][1]+" , ");
System.out.println(graph_edge[i][2]+"> forms a cycle so it is removed\n\n");
}
}
System.out.println("Cost of the spanning tree : "+cost);
}
int find_node(int n)
{
for(int i=1;i<=noe;i++)
{
for(int j=1;j<=top[i];j++)
{
if(n==sets[i][j])
return i;
}
}
return -1;
}
}
class Kruskal1
{
public static void main(String args[])
{
Graph obj=new Graph();
obj.read_graph();
obj.sort_edges();
obj.algorithm();
}
}
/*
Enter the no. of nodes in the undirected weighted graph ::6
Enter the weights for the following edges ::
< 1 , 2 > ::3
< 1 , 3 > ::1
< 1 , 4 > ::6
< 1 , 5 > ::0
< 1 , 6 > ::0
< 2 , 3 > ::5
< 2 , 4 > ::0
< 2 , 5 > ::3
< 2 , 6 > ::0
< 3 , 4 > ::5
< 3 , 5 > ::6
< 3 , 6 > ::4
< 4 , 5 > ::0
< 4 , 6 > ::2
< 5 , 6 > ::6
The algorithm starts ::
The edge included in the tree is ::< 1 , 3 >
The edge included in the tree is ::< 4 , 6 >
The edge included in the tree is ::< 1 , 2 >
The edge included in the tree is ::< 2 , 5 >
The edge included in the tree is ::< 3 , 6 >
Inclusion of the edge
< 2 , 3> forms a cycle so it is removed
Inclusion of the edge
< 3 , 4> forms a cycle so it is removed
Inclusion of the edge
< 1 , 4> forms a cycle so it is removed
Inclusion of the edge
< 3 , 5> forms a cycle so it is removed
Inclusion of the edge
< 5 , 6> forms a cycle so it is removed
Cost of the spanning tree : 13
*/
To implement prim’s algorithm.
import java.io.*;
import java.util.*;
class Graph
{
int weight[][]=new int[20][20];
int visited[]=new int[20];
int d[]=new int[20];
int p[]=new int[20];
int v,e;
int getNumber()
{
String str;
int ne=0;
InputStreamReader input=new InputStreamReader(System.in);
BufferedReader in=new BufferedReader(input);
try
{
str=in.readLine();
ne=Integer.parseInt(str);
}
catch(Exception e)
{
System.out.println("I/O Error");
}
return ne;
}/*end getNumber*/
void creategraph()
{
int i,j,a,b,w;
System.out.print("\nEnter number of vertices : ");
v=getNumber();
System.out.print("\nEnter number of edges : ");
e=getNumber();
for (i=1;i<=v;i++)
for (j=1;j<=v;j++)
weight[i][j]=0;
for (i=1;i<=v;i++)
{
p[i] = visited[i] =0;
d[i] = 32767;
}
for (i=1;i<=e;i++)
{
System.out.print("\nEnter edge a,b and weight w : ");
a=getNumber();
b=getNumber();
w=getNumber();
weight[a][b]=weight[b][a]=w;
}
}
void PrimAlgorithm()
{
creategraph();
int current, totalvisited, mincost,i;
current=1; d[current]=0;
totalvisited =1;
visited[current]=1;
while(totalvisited!=v)
{
for (i=1;i<=v;i++)
{
if(weight[current][i]!=0)
if(visited[i]==0)
if(d[i]>weight[current][i])
{
d[i] = weight[current][i];
p[i] = current;
}
}
mincost= 32767;
for (i=1;i<=v;i++)
{
if(visited[i] ==0)
if (d[i] <mincost)
{
mincost = d[i];
current = i;
}
}
visited[current] = 1;
totalvisited++;
} /*end of while loop */
mincost =0;
for (i=1;i<=v;i++)
mincost += d[i];
System.out.println("\nMinimum cost = "+mincost);
System.out.println("\nMinimum span tree is");
for (i=1;i<=v;i++)
System.out.println("\nvertex "+i+" is connected to "+p[i]);
} /*end of prim */
}
class Prim
{
public static void main(String args[])
{
Graph g=new Graph();
g.PrimAlgorithm();
}
}
/*
Enter number of vertices : 6
Enter number of edges : 9
Enter edge a,b and weight w : 1 2 6
Enter edge a,b and weight w : 1 3 3
Enter edge a,b and weight w : 2 3 2
Enter edge a,b and weight w : 2 4 5
Enter edge a,b and weight w : 3 5 4
Enter edge a,b and weight w : 3 4 3
Enter edge a,b and weight w : 4 5 2
Enter edge a,b and weight w : 4 6 3
Enter edge a,b and weight w : 5 6 5
Minimum cost = 13
Minimum span tree is
vertex 1 is connected to 0
vertex 2 is connected to 3
vertex 3 is connected to 1
vertex 4 is connected to 3
vertex 5 is connected to 4
vertex 6 is connected to 4
*/
import java.util.*;
class Graph
{
int weight[][]=new int[20][20];
int visited[]=new int[20];
int d[]=new int[20];
int p[]=new int[20];
int v,e;
int getNumber()
{
String str;
int ne=0;
InputStreamReader input=new InputStreamReader(System.in);
BufferedReader in=new BufferedReader(input);
try
{
str=in.readLine();
ne=Integer.parseInt(str);
}
catch(Exception e)
{
System.out.println("I/O Error");
}
return ne;
}/*end getNumber*/
void creategraph()
{
int i,j,a,b,w;
System.out.print("\nEnter number of vertices : ");
v=getNumber();
System.out.print("\nEnter number of edges : ");
e=getNumber();
for (i=1;i<=v;i++)
for (j=1;j<=v;j++)
weight[i][j]=0;
for (i=1;i<=v;i++)
{
p[i] = visited[i] =0;
d[i] = 32767;
}
for (i=1;i<=e;i++)
{
System.out.print("\nEnter edge a,b and weight w : ");
a=getNumber();
b=getNumber();
w=getNumber();
weight[a][b]=weight[b][a]=w;
}
}
void PrimAlgorithm()
{
creategraph();
int current, totalvisited, mincost,i;
current=1; d[current]=0;
totalvisited =1;
visited[current]=1;
while(totalvisited!=v)
{
for (i=1;i<=v;i++)
{
if(weight[current][i]!=0)
if(visited[i]==0)
if(d[i]>weight[current][i])
{
d[i] = weight[current][i];
p[i] = current;
}
}
mincost= 32767;
for (i=1;i<=v;i++)
{
if(visited[i] ==0)
if (d[i] <mincost)
{
mincost = d[i];
current = i;
}
}
visited[current] = 1;
totalvisited++;
} /*end of while loop */
mincost =0;
for (i=1;i<=v;i++)
mincost += d[i];
System.out.println("\nMinimum cost = "+mincost);
System.out.println("\nMinimum span tree is");
for (i=1;i<=v;i++)
System.out.println("\nvertex "+i+" is connected to "+p[i]);
} /*end of prim */
}
class Prim
{
public static void main(String args[])
{
Graph g=new Graph();
g.PrimAlgorithm();
}
}
/*
Enter number of vertices : 6
Enter number of edges : 9
Enter edge a,b and weight w : 1 2 6
Enter edge a,b and weight w : 1 3 3
Enter edge a,b and weight w : 2 3 2
Enter edge a,b and weight w : 2 4 5
Enter edge a,b and weight w : 3 5 4
Enter edge a,b and weight w : 3 4 3
Enter edge a,b and weight w : 4 5 2
Enter edge a,b and weight w : 4 6 3
Enter edge a,b and weight w : 5 6 5
Minimum cost = 13
Minimum span tree is
vertex 1 is connected to 0
vertex 2 is connected to 3
vertex 3 is connected to 1
vertex 4 is connected to 3
vertex 5 is connected to 4
vertex 6 is connected to 4
*/
Subscribe to:
Posts (Atom)