1. #include<iostream>
2. #define INFINITY 999
3.
4. using namespace std;
5.
6. class Dijkstra{
7. private:
8. int adjMatrix[15][15];
9. int predecessor[15],distance[15];
10. bool mark[15]; //keep track of visited node
11. int source;
12. int numOfVertices;
13. public:
14. /*
15. * Function read() reads No of vertices, Adjacency Matrix and source
16. * Matrix from the user. The number of vertices must be greather than
17. * zero, all members of Adjacency Matrix must be postive as distances
18. * are always positive. The source vertex must also be positive from 0
19. * to noOfVertices - 1
20.
21. */
22. void read();
23.
24. /*
25. * Function initialize initializes all the data members at the begining of
26. * the execution. The distance between source to source is zero and all other
27. * distances between source and vertices are infinity. The mark is initialized
28. * to false and predecessor is initialized to -1
29. */
30.
31. void initialize();
32.
33. /*
34. * Function getClosestUnmarkedNode returns the node which is nearest from the
35. * Predecessor marked node. If the node is already marked as visited, then it search
36. * for another node.
37. */
38.
39. int getClosestUnmarkedNode();
40. /*
41. * Function calculateDistance calculates the minimum distances from the source node to
42. * Other node.
43. */
44.
45. void calculateDistance();
46. /*
47. * Function output prints the results
48. */
49.
50. void output();
51. void printPath(int);
52. };
53.
54.
55. void Dijkstra::read(){
56. cout<<"Enter the number of vertices of the graph(should be > 0)\n";
57. cin>>numOfVertices;
58. while(numOfVertices <= 0) {
59. cout<<"Enter the number of vertices of the graph(should be > 0)\n";
|
|
60. cin>>numOfVertices;
61. }
62. cout<<"Enter the adjacency matrix for the graph\n";
63. cout<<"To enter infinity enter "<<INFINITY<<endl;
64. for(int i=0;i<numOfVertices;i++) {
65. cout<<"Enter the (+ve)weights for the row "<<i<<endl;
66. for(int j=0;j<numOfVertices;j++) {
67. cin>>adjMatrix[i][j];
68. while(adjMatrix[i][j]<0) {
69. cout<<"Weights should be +ve. Enter the weight again\n";
70. cin>>adjMatrix[i][j];
71. }
72. }
73. }
74. cout<<"Enter the source vertex\n";
75. cin>>source;
76. while((source<0) && (source>numOfVertices-1)) {
77. cout<<"Source vertex should be between 0 and"<<numOfVertices-1<<endl;
78. cout<<"Enter the source vertex again\n";
79. cin>>source;
80. }
81. }
82.
83.
84. void Dijkstra::initialize(){
85. for(int i=0;i<numOfVertices;i++) {
86. mark[i] = false;
87. predecessor[i] = -1;
88. distance[i] = INFINITY;
89. }
90. distance[source]= 0;
91. }
92.
93.
94. int Dijkstra::getClosestUnmarkedNode(){
95. int minDistance = INFINITY;
96. int closestUnmarkedNode;
97. for(int i=0;i<numOfVertices;i++) {
98. if((!mark[i]) && (minDistance >= distance[i])) {
99. minDistance = distance[i];
100. closestUnmarkedNode = i;
101. }
102. }
103. return closestUnmarkedNode;
104. }
105.
106.
107. void Dijkstra::calculateDistance(){
108. initialize();
109. int minDistance = INFINITY;
110. int closestUnmarkedNode;
111. int count = 0;
112. while(count < numOfVertices) {
113. closestUnmarkedNode = getClosestUnmarkedNode();
114. mark[closestUnmarkedNode] = true;
115. for(int i=0;i<numOfVertices;i++) {
116. if((!mark[i]) && (adjMatrix[closestUnmarkedNode][i]>0)) {
117. if(distance[i] > distance[closestUnmarkedNode]+adjMatrix[closestUnmarkedNode][i]) {
118. distance[i] = distance[closestUnmarkedNode]+adjMatrix[closestUnmarkedNode][i];
119. predecessor[i] = closestUnmarkedNode;
120. }
121. }
122. }
123. count++;
124. }
125. }
126.
127.
128. void Dijkstra::printPath(int node){
129. if(node == source)
130. cout<<(char)(node + 97)<<"..";
131. else if(predecessor[node] == -1)
132. cout<<"No path from “<<source<<”to "<<(char)(node + 97)<<endl;
133. else {
134. printPath(predecessor[node]);
135. cout<<(char) (node + 97)<<"..";
136. }
137. }
138.
139.
140. void Dijkstra::output(){
141. for(int i=0;i<numOfVertices;i++) {
142. if(i == source)
143. cout<<(char)(source + 97)<<".."<<source;
|
|
144. else
145. printPath(i);
146. cout<<"->"<<distance[i]<<endl;
147. }
148. }
149.
150.
151. int main(){
152. Dijkstra G;
153. G.read();
154. G.calculateDistance();
155. G.output();
156. return 0;
157. }
BFS
#include <iostream>
#include <ctime>
using namespace std;
/****************************************************************
Performs the Breadth-First Graph search for both directed and
undirected graphs. This algorithm explores all the findable nodes
in "layers".
@author Bibek Subedi
*****************************************************************/
/****************************************************************
Class Queue represent a Queue data structure which is First In
First Out [FIFO] structured. It has operations like Enqueue which
adds an element at the rear side and Dequeue which removes the
element from front.
*****************************************************************/
struct node {
int info;
node *next;
};
class Queue {
private:
node *front;
node *rear;
public:
Queue();
~Queue();
bool isEmpty();
void enqueue(int);
int dequeue();
void display();
};
void Queue::display(){
node *p = new node;
p = front;
if(front == NULL){
cout<<"\nNothing to Display\n";
}else{
while(p!=NULL){
cout<<endl<<p->info;
p = p->next;
}
}
}
Queue::Queue() {
front = NULL;
rear = NULL;
}
Queue::~Queue() {
delete front;
}
void Queue::enqueue(int data) {
node *temp = new node();
temp->info = data;
temp->next = NULL;
if(front == NULL){
front = temp;
}else{
rear->next = temp;
}
rear = temp;
}
int Queue::dequeue() {
node *temp = new node();
int value;
if(front == NULL){
cout<<"\nQueue is Emtpty\n";
}else{
temp = front;
value = temp->info;
front = front->next;
delete temp;
}
return value;
}
bool Queue::isEmpty() {
return (front == NULL);
}
/************************************************************
Class Graph represents a Graph [V,E] having vertices V and
edges E.
************************************************************/
class Graph {
private:
int n; /// n is the number of vertices in the graph
int **A; /// A stores the edges between two vertices
public:
Graph(int size = 2);
~Graph();
bool isConnected(int, int);
void addEdge(int u, int v);
void BFS(int);
};
Graph::Graph(int size) {
int i, j;
if (size < 2) n = 2;
else n = size;
A = new int*[n];
for (i = 0; i < n; ++i)
A[i] = new int[n];
for (i = 0; i < n; ++i)
for (j = 0; j < n; ++j)
A[i][j] = 0;
}
Graph::~Graph() {
for (int i = 0; i < n; ++i)
delete [] A[i];
delete [] A;
}
/******************************************************
Checks if two given vertices are connected by an edge
@param u vertex
@param v vertex
@return true if connected false if not connected
******************************************************/
bool Graph::isConnected(int u, int v) {
return (A[u-1][v-1] == 1);
}
/*****************************************************
adds an edge E to the graph G.
@param u vertex
@param v vertex
*****************************************************/
void Graph::addEdge(int u, int v) {
A[u-1][v-1] = A[v-1][u-1] = 1;
}
/*****************************************************
performs Breadth First Search
@param s initial vertex
*****************************************************/
void Graph::BFS(int s) {
Queue Q;
/** Keeps track of explored vertices */
bool *explored = new bool[n+1];
/** Initailized all vertices as unexplored */
for (int i = 1; i <= n; ++i)
explored[i] = false;
/** Push initial vertex to the queue */
Q.enqueue(s);
explored[s] = true; /** mark it as explored */
cout << "Breadth first Search starting from vertex ";
cout << s << ": " << endl;
/** Unless the queue is empty */
while (!Q.isEmpty()) {
/** Pop the vertex from the queue */
int v = Q.dequeue();
/** display the explored vertices */
cout << v << " ";
/** From the explored vertex v try to explore all the
connected vertices */
for (int w = 1; w <= n; ++w)
/** Explores the vertex w if it is connected to v
and and if it is unexplored */
if (isConnected(v, w) &&!explored[w]) {
/** adds the vertex w to the queue */
Q.enqueue(w);
/** marks the vertex w as visited */
explored[w] = true;
}
}
cout << endl;
delete [] explored;
}
int main() {
/** Creates a graph with 12 vertices */
Graph g(12);
/** Adds edges to the graph */
g.addEdge(1, 2); g.addEdge(1, 3);
g.addEdge(2, 4); g.addEdge(3, 4);
g.addEdge(3, 6); g.addEdge(4,7);
g.addEdge(5, 6); g.addEdge(5, 7);
clock_t t1;
t1 = clock();
/** Explores all vertices findable from vertex 1 */
g.BFS(1);
float diff = (double)(clock() - t1)/CLOCKS_PER_SEC;
cout <<endl<< "The time taken for Breadth first search: "<< diff << endl;
}
DFS
#include <iostream>
#include <ctime>
#include <malloc.h>
using namespace std;
struct node{
int info;
struct node *next;
};
class stack{
struct node *top;
public:
stack();
void push(int);
int pop();
bool isEmpty();
void display();
};
stack::stack(){
top = NULL;
}
void stack::push(int data){
node *p;
if((p=(node*)malloc(sizeof(node)))==NULL){
cout<<"Memory Exhausted";
exit(0);
}
p = new node;
p->info = data;
p->next = NULL;
if(top!=NULL){
p->next = top;
}
top = p;
}
int stack::pop(){
struct node *temp;
int value;
if(top==NULL){
cout<<"\nThe stack is Empty"<<endl;
}else{
temp = top;
top = top->next;
value = temp->info;
delete temp;
}
return value;
}
bool stack::isEmpty(){
return (top == NULL);
}
void stack::display(){
struct node *p = top;
if(top==NULL){
cout<<"\nNothing to Display\n";
}else{
cout<<"\nThe contents of Stack\n";
while(p!=NULL){
cout<<p->info<<endl;
p = p->next;
}
}
}
class Graph {
private:
int n;
int **A;
public:
Graph(int size = 2);
~Graph();
bool isConnected(int, int);
void addEdge(int x, int y);
|
|
void DFS(int, int);
};
Graph::Graph(int size) {
int i, j;
if (size < 2) n = 2;
else n = size;
A = new int*[n];
for (i = 0; i < n; ++i)
A[i] = new int[n];
for (i = 0; i < n; ++i)
for (j = 0; j < n; ++j)
A[i][j] = 0;
}
Graph::~Graph() {
for (int i = 0; i < n; ++i)
delete [] A[i];
delete [] A;
}
bool Graph::isConnected(int x, int y) {
return (A[x-1][y-1] == 1);
}
void Graph::addEdge(int x, int y) {
A[x-1][y-1] = A[y-1][x-1] = 1;
}
void Graph::DFS(int x, int required){
stack s;
bool *visited = new bool[n+1];
int i;
for(i = 0; i <= n; i++)
visited[i] = false;
s.push(x);
visited[x] = true;
if(x == required) return;
cout << "Depth first Search starting from vertex ";
cout << x << ": " << endl;
while(!s.isEmpty()){
int k = s.pop();
if(k == required) break;
cout<<k<<" ";
for (i = n; i >= 0; --i)
if (isConnected(k, i) &&!visited[i]) {
s.push(i);
visited[i] = true;
}
}
cout<<endl;
delete [] visited;
}
int main(){
Graph g(8);
g.addEdge(1, 2); g.addEdge(1, 3); g.addEdge(1, 4);
g.addEdge(2, 5); g.addEdge(2, 6); g.addEdge(4, 7);
g.addEdge(4, 8);
g.DFS(1, 4);
return 0;
}
Trees