Algorithms/graph.cpp at master · Anirudh-R-1201/Algorithms · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
#include<bits/stdc++.h>

using namespace std;

struct node {
	char value;
	vector<node*> neighbours;
	node(char v) {
		value = v;
		neighbours.clear();
	}
};

void addNode(vector<node*> &graph, char value) {
	node *n = new node(value);
	graph.push_back(n);
}

void addEdge(vector<node*> graph, int endVertices[2]) {
	if(endVertices[0] <= graph.size() && endVertices[1] <= graph.size()) {
		graph[endVertices[0] - 1]->neighbours.push_back(graph[endVertices[1] - 1]);
		graph[endVertices[1] - 1]->neighbours.push_back(graph[endVertices[0] - 1]);
	}
}

void bfs(node* root) {
	queue<node*> search;
	vector<node*> visited;
	search.push(root);
	visited.push_back(root);
	node *temp;
	while(!search.empty()) {

		temp = search.front();

		cout << temp->value;

		for(int i = 0; i < temp->neighbours.size(); i++) {

			node *t = temp->neighbours[i];
			bool find = false;

			for(int j = 0; j < visited.size(); j++) {
				if(visited[j] == t) find = true;
			}

			if(!find) {
				search.push(t);
				visited.push_back(t);
			}

		}

		search.pop();
	}
}

void dfs(node* root) {
	stack<node*> search;
	vector<node*> visited;
	search.push(root);
	visited.push_back(root);
	node *temp;
	while(!search.empty()) {

		temp = search.top();

		cout << temp->value;

		search.pop();

		for(int i = 0; i < temp->neighbours.size(); i++) {

			node *t = temp->neighbours[i];
			bool find = false;

			for(int j = 0; j < visited.size(); j++) {
				if(visited[j] == t) find = true;
			}

			if(!find) {
				search.push(t);
				visited.push_back(t);
			}
		}
	}
}

int main() {
	vector<node*> graph;
	int n, e[] = {0, 0};
	char v;
	cout << "Enter number of vertices: ";
	cin >> n;
	for(int i = 0; i < n; i++) {
		cout << "Enter value of vertice " << i + 1 << ": ";
		cin >> v;
		addNode(graph, v);
	}
	cout << "Enter number of edges: ";
	cin >> n;
	for(int i = 0; i < n; i++) {
		cout << "Enter end vertice indices of edge " << i + 1 << ": ";
		cin >> e[0] >> e[1];
		addEdge(graph, e);
	}
	cout << "\nBFS: ";
	bfs(graph[0]);
	cout << "\nDFS: ";
	dfs(graph[0]);
	cout << endl;
}