Djecstra

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