#include #include #include using namespace std; class AdjacencyList { public: int n; vector** adj; AdjacencyList(int n) { this->n = n; adj = new vector*[n]; for (int i = 0; i < n; i++) { adj[i] = new vector; } } void addEdge(int origin, int destination) { if (isInvalid(origin, destination)) { cout << "Unable to ADD as it's an INVALID edge " << "(" << origin << ", " << destination << ")" << endl; } else if (findIndex(origin, destination) != 29292) { cout << "The edge (" << origin << ", " << destination << ") is already present in the graph, can't add anymore " << endl; } else { adj[origin - 1]->push_back(destination - 1); } } void removeEdge(int origin, int destination) { if (!isInvalid(origin, destination)) { int index = findIndex(origin, destination); if (index != 29292) { adj[origin - 1]->erase(adj[origin - 1]->begin() + index); } else { cout << "The edge (" << origin << ", " << destination << ") is not there in the graph " << endl; } } else { cout << "Unable to REMOVE as it's an INVALID edge " << "(" << origin << ", " << destination << ")" << endl; } } bool isAdjacent(int origin, int destination) { if (isInvalid(origin, destination)) { cout << "It's an INVALID edge " << "(" << origin << ", " << destination << ")" << endl; return false; } destination--; bool b = false; for (unsigned int i = 0; i < adj[origin - 1]->size(); i++) { if (adj[origin - 1]->at(i) == destination) { b = true; break; } } return b; } // Breadth First Search void BFS(int o) { o--; bool* visited = new bool[this->n]; for (int i = 0; i < this->n; i++) { visited[i] = false; } list queue; visited[o] = true; queue.push_back(o); vector::iterator iter; while (!queue.empty()) { o = queue.front(); cout << o + 1 << "->"; queue.pop_front(); for (iter = adj[o]->begin(); iter != adj[o]->end(); ++iter) { if (!visited[*iter]) { visited[*iter] = true; queue.push_back(*iter); } } } } // Depth First Search /* *** DFS USING RECURSION *** */ // DFS utility function for recursion /*void DFSUtil(int o, bool visited[]) { visited[o] = true; cout << o + 1 << "->"; vector::iterator iter; for (iter = adj[o]->begin(); iter != adj[o]->end(); ++iter) { if (!visited[*iter]) { DFSUtil(*iter, visited); } } } // main DFS function void DFSRecursion(int o) { o--; bool* visited = new bool[n]; for (int i = 0; i < n; i++) { visited[i] = false; } DFSUtil(o, visited); }*/ /* *** DFS USING LOoPS *** *** ( without recursion ) *** */ void DFSLoop(int o) { o--; bool* visited = new bool[n]; for (int i = 0; i < n; i++) { visited[i] = false; } list stack; visited[o] = true; cout << o + 1 << "->"; stack.push_front(o); vector::iterator iter; int count; while (!stack.empty()) { count = 0; o = stack.front(); for (iter = adj[o]->begin(); iter < adj[o]->end(); iter++) { if (!visited[*iter]) { visited[*iter] = true; cout << *iter + 1 << "->"; stack.push_front(*iter); count++; } if (count != 0) { break; } } if (count == 0) { stack.pop_front(); } } } // SHORTEST PATH ALGORITHM void sP(int src, int destination) { src--; destination--; int* dist = new int[n]; int* prev = new int[n]; if (!sPBFS(dist, prev, src, destination)) { cout << "Source and destination are not connected " << endl; } else { vector path; int p = destination; path.push_back(p); while (prev[p] != -1) { path.push_back(prev[p]); p = prev[p]; } cout << "The shortest path between the vertices " << src + 1 << " and " << destination + 1 << " is " << dist[destination] << endl << endl; cout << "Path is : " << endl; for (int iter = path.size() - 1; iter >= 0; iter--) { cout << path[iter] + 1 << "->"; } cout << endl; } delete [] dist; delete [] prev; } bool sPBFS(int* dist, int* prev, int src, int destination) { bool* visited = new bool[this->n]; for (int i = 0; i < this->n; i++) { visited[i] = false; dist[i] = INT_MAX; prev[i] = -1; } list queue; visited[src] = true; dist[src] = 0; queue.push_back(src); vector::iterator iter; while (!queue.empty()) { src = queue.front(); queue.pop_front(); for (iter = adj[src]->begin(); iter < adj[src]->end(); iter++) { if (!visited[*iter]) { visited[*iter] = true; dist[*iter] = dist[src] + 1; prev[*iter] = src; queue.push_back(*iter); if (*iter == destination) { return true; } } } } return false; } void display() { int p = 0; for (int i = 0; i < this->n; i++) { cout << i + 1 << ": "; for (unsigned int j = 0; j < adj[i]->size(); j++) { p = adj[i]->at(j) + 1; cout << p << "->"; } cout << endl; } } int findIndex(int vect, int value) { int ind = 29292; vect--; value--; for (unsigned int i = 0; i < adj[vect]->size(); i++) { if (adj[vect]->at(i) == value) { ind = i; break; } } return ind; } bool isInvalid(int origin, int destination) { return (origin > n || origin < 1 || destination > n || destination < 1); } }; int main() { AdjacencyList aList(12); aList.addEdge(1, 2); aList.addEdge(5, 3); aList.addEdge(1, 5); aList.addEdge(3, 6); aList.addEdge(2, 4); aList.addEdge(2, 9); aList.addEdge(4, 7); aList.addEdge(9, 6); aList.addEdge(7, 8); aList.addEdge(7, 10); aList.addEdge(10, 8); aList.addEdge(11, 8); aList.addEdge(9, 11); aList.addEdge(9, 12); //aList.DFSRecursion(1); //aList.DFSLoop(1); //aList.BFS(1); /*aList.removeEdge(1,2); aList.removeEdge(2,5);*/ //aList.sP(2, 8); aList.display(); return 0; }

Directed Unweighted Graph (Adjacency List)