GRAPHS in C++
A graph can be thought of a collection of vertices (V) and edges (E), so we write,
G = (V, E)
Graphs can be directed, or undirected, weighted or unweighted.
A directed graph, or digraph, is a graph where the edge set is an ordered pair.
That is, edge 1 being connected to edge 2 does not imply that edge 2 is connected to edge 1. (i.e. it has direction – trees are special kinds of directed graphs)
An undirected graph is a graph where the edge set in an unordered pair.
That is, edge 1 being connected to edge 2 does imply that edge 2 is connected to edge 1.
A weighted graph is graph which has a value associated with each edge. This can be a distance, or cost, or some other numeric value associated with the edge.
Breadth First Search and Traversal
In Breadth first search we start at vertex v and mark it as having been reached (visited) the vertex v is at this time said to be unexplored. A vertex is said to have been explored by an algorithm when the algorithm has visited all vertices adjacent from it. All unvisited vertices adjacent from v are visited next. These are new unexplored vertices. Vertex v has now been explored. The newly visited vertices have not been explored and or put on to the end of a list of unexplored list of vertices. The first vertex on this list is the next to be explored. Exploration continues until no unexplored vertex is left. The list of unexplored vertices operates as a queue and can be represented using any of the standard queue representations.
Algorithm BFS(v)
//A breadth first search of G is carried out beginning at vertex v. For
//any node I, visited[I=1 if I has already been visited. The graph G
//and array visited are global; visited[] is initialized to zero.
{
u:=v; //q is a queue of unexplored vertices
visited[v]:=1;
repeat
{
for all vertices w adjacent from u do
{
if (visited[w]=0) then
{
add w to q; //w is unexplored
visited[w]:=1;
}
}
if q is empty then return; //no unexplored vertex
delete u from q; //get first unexplored vertex
}until(false);
}
Algorithm BFT(G, n)
//Breadth first traversal of G
{
for I:=1 to n do //mark all vertices unvisited
visited[I]:=0;
for I:=1 to n do
if (visited[I]=0) then
BFS(i);
}
Depth First Search and Traversal
A depth first search of a graph differs from a breadth first search in that the exploration of a vertex v is suspended as soon as a new vertex is reached. At this time of exploration of the new vertex u begins. When this new vertex has been explored, the exploration of v continues. The search terminates when all reached vertices have been fully explored. The search process is best described recursively in the following algorithm.
Kruskal’s Algorithm
Here the edges of the graph considered in nondecreasing order of cost. This interpretation is that the set t of edges so far selected for the spanning tree be such that it is possible to complete t into a tree. Thus t may not be a tree at all stages of algorithm.
Write a C++ programs for the implementation of bfs and dfs for a given graph.
#include<conio.h>
#include<iostream.h>
#include<stdlib.h>
void create(); // For creating a graph
void dfs(); // For Deapth First Search(DFS) Traversal.
void bfs(); // For Breadth First Search(BFS) Traversal.
struct node // Structure for elements in the graph
{
int data,status;
struct node *next;
struct link *adj;
};
struct link // Structure for adjacency list
{
struct node *next;
struct link *adj;
};
struct node *start,*p,*q;
struct link *l,*k;
int main()
{
int choice;
clrscr();
create();
while(1)
{
cout<<"-----------------------";
cout<<"1: DFS 2: BSF 3: Exit Enter your choice: ";
cin>>choice;
switch(choice)
{
case 1:
dfs();
break;
case 2:
bfs();
break;
case 3:
exit(0);
break;
default:
cout<<"
Incorrect choice!
Re-enter your choice.";
getch();
}
}
return 0;
}
void create() // Creating a graph
{
int dat,flag=0;
start=NULL;
cout<<"
Enter the nodes in the graph(0 to end): ";
while(1)
{
cin>>dat;
if(dat==0)
break;
p=new node;
p->data=dat;
p->status=0;
p->next=NULL;
p->adj=NULL;
if(flag==0)
{
start=p;
q=p;
flag++;
}
else
{
q->next=p;
q=p;
}
}
p=start;
while(p!=NULL)
{
cout<<"Enter the links to "<<p->data<<" (0 to end) : ";
flag=0;
while(1)
{
cin>>dat;
if(dat==0)
break;
k=new link;
k->adj=NULL;
if(flag==0)
{
p->adj=k;
l=k;
flag++;
}
else
{
l->adj=k;
l=k;
}
q=start;
while(q!=NULL)
{
if(q->data==dat)
k->next=q;
q=q->next;
}
}
p=p->next;
}
cout<<"-------------------------";
return;
}
// Deapth First Search(DFS) Traversal.
void bfs()
{
int qu[20],i=1,j=0;
p=start;
while(p!=NULL)
{
p->status=0;
p=p->next;
}
p=start;
qu[0]=p->data;
p->status=1;
while(1)
{
if(qu[j]==0)
break;
p=start;
while(p!=NULL)
{
if(p->data==qu[j])
break;
p=p->next;
}
k=p->adj;
while(k!=NULL)
{
q=k->next;
if(q->status==0)
{
qu[i]=q->data;
q->status=1;
qu[i+1]=0;
i++;
}
k=k->adj;
}
j++;
}
j=0;
cout<<"Breadth First Search Results";
cout<<"---------------------------";
while(qu[j]!=0)
{
cout<<qu[j]<<" ";
j++;
}
getch();
return;
}
// Breadth First Search(BFS) Traversal.
void dfs()
{
int stack[25],top=1;
cout<<"Deapth First Search Results";
cout<<"---------------------------";
p=start;
while(p!=NULL)
{
p->status=0;
p=p->next;
}
p=start;
stack[0]=0;
stack[top]=p->data;
p->status=1;
while(1)
{
if(stack[top]==0)
break;
p=start;
while(p!=NULL)
{
if(p->data==stack[top])
break;
p=p->next;
}
cout<<stack[top]<<" ";
top--;
k=p->adj;
while(k!=NULL)
{
q=k->next;
if(q->status==0)
{
top++;
stack[top]=q->data;
q->status=1;
}
k=k->adj;
}
}
getch();
return;
}
SORTING METHODS using C++
HEAP SORT
The best-known example of the use of a heap arises in its application to sorting. A conceptually simple sorting strategy has been given before, in which the maximum value is continually removed from the remaining unsorted elements. A sorting algorithm that incorporates the fact that n elements can be inserted I O(n) time is given in the algorithm.
Algorithm HeapSort(a,n)
//a[1:n] contains n elements to be sorted. Heapsort
//rearranges them inplace into nondecreasing order.
{
heapify(a,n); //transform the array into a heap
//interchange the new maximum with the element
//at the end of the array.
for i:=n to 2 step –1 do
{
t:=a[i];
a[i]:=a[1];
a[1]:=t;
adjust(a,1,i-1);
}
}
QUICK SORT
In quick sort, the division into two subarrays is made so that the sorted subarrays do no need to be merged later. This is accomplished by rearranging the elements in a[1:n] such that a[I] a[j] for all I between 1 and m and all j between m+1 and n for some m, 1 m n. Thus, the elements in a[1:m] and a[m+1:n] can be independently sorted. The rearrangement of the elements is accomplished by picking some element of a[], say t=a[s], and then reordering the other elements so that all elements appearing before t in a[1:n] are less than or equal to t and all elements appearing after t are greater than or equal to t. This rearranging is referred to as partitioning.
MERGE SORT
In merge sort, we assume throughout that the elements are to be sorted in nondecreasing order. Given a sequence of n elements, the idea is to imagine them split into two sets a[1] to a[n/2] and a[n/2 +1] to a[n]. Each set is individually sorted, and the resulting sorted sequences are merged to produce a single sorted sequence of n elements.
Write C++ programs for implementing the following sorting methods:
Quick sort in C++
#include<iostream.h>
#include<conio.h>
void swap(int &x,int &y)
{
int t=x;
x=y;
y=t;
}
void quick(int a[],int l,int r)
{
if(l>=r)
return;
int i=l;
int j=r+1;
int v=a[l];
while(1)
{
do
{
i++;
}while(a[i]<v);
do
{
j--;
}while(a[j]>v);
if(i<j)
swap(a[i],a[j]);
else
break;
}
a[l]=a[j];
a[j]=v;
quick(a,l,j-1);
quick(a,j+1,r);
}
void main()
{
clrscr();
int n,*a,i;
cout<<"Enter the size of array"<<endl;
cin>>n;
a=new int[n];
cout<<"Enter the elements of array"<<endl;
for(i=0;i<n;i++)
{
cin>>a[i];
}
quick(a,0,n-1);
for(i=0;i<n;i++)
{
cout<<a[i]<<"\t";
}
getch();
}
Heap sort in C++
#include<iostream.h>
#include<conio.h>
void swap(int &x,int &y)
{
int t=x;
x=y;
y=t;
}
void adjust(int a[],int i,int n)
{
int j=2*i+1;
while(j<=n)
{
if(j<n)
if(a[j]<a[j+1])
j++;
if(a[i]<a[j])
swap(a[i],a[j]);
else
break;
i=j;
j=2*i+1;
}
}
void hsort(int a[],int n)
{
int i;
for(i=n/2-1;i>=0;i--)
adjust(a,i,n);
for(i=n;i>=0;i--)
{
swap(a[0],a[i]);
adjust(a,0,i-1);
}
}
void main()
{
clrscr();
int n,*a,i;
cout<<"Enter the size of array"<<endl;
cin>>n;
a=new int[n];
cout<<"Enter the elements of array"<<endl;
for(i=0;i<n;i++)
{
cin>>a[i];
}
hsort(a,n-1);
for(i=0;i<n;i++)
{
cout<<a[i]<<"\t";
}
getch();
}
No comments:
Post a Comment