#include <iostream>
#include <queue>
using namespace std;
class Graph {
public:
Graph(int n);
~Graph();
void addEdge(int src, int tar);
void BFTraversal();
void DFTraversal();
void printVertices();
void printEdges();
private:
int vertexCount;
int edgeCount;
bool** adjMat;
void BFS(int n, bool marked[]);
void DFS(int n, bool marked[]);
};
Graph::Graph(int n=0) {
vertexCount = n;
edgeCount = 0;
if(n == 0)
adjMat = 0;
else {
adjMat = new bool* [n];
for(int i=0; i < n; i++)
adjMat[i] = new bool [n];
for(int i=0; i < n; i++)
for(int j=0; j < n; j++)
adjMat[i][j] = 0;
}
}
Graph::~Graph() {
for(int i=0; i < vertexCount; i++)
delete [] adjMat[i];
delete [] adjMat;
}
void Graph::addEdge(int src, int tar) {
if(src < 0 || tar < 0 || src > vertexCount-1 || tar > vertexCount-1)
cout << "Invalid vertex index! No edge has been added." << endl;
else if(src == tar)
cout << "No self loop! No edge has been added." << endl;
else if (adjMat[src][tar] == 1)
cout << "This edge already exists. No edge has been added." << endl;
else {
adjMat[src][tar] = 1;
edgeCount++;
}
}
void Graph::BFTraversal() {
// TO DO
// You are expected to call BFS() in this function,
// potentially multiple times in loops.
}
void Graph::BFS(int n, bool marked[]) {
// TO DO
// You are expected to use a queue<int> from C++ STL.
// This function is not recursive, and you are expected to use a while loop.
}
void Graph::DFTraversal() {
// TO DO
// You are expected to call DFS() in this function,
// potentially multiple times in loops.
}
void Graph::DFS(int n, bool marked[]) {
// TO DO
// You are asked to implement this function using recursion.
// However, a for loop is expected --- the recursive calls are within the loop.
}
void Graph::printVertices() {
cout << "This directed graph has " << vertexCount << " vertex (vertices), ";
cout << "indexed from 0 to " << vertexCount-1 << endl;
}
void Graph::printEdges() {
cout << "This directed graph has " << edgeCount << " edge(s):" << endl;
for(int i=0; i < vertexCount; i++)
for(int j=0; j < vertexCount; j++)
if(adjMat[i][j])
cout << "(" << i << "," << j << ")" << endl;
}
int main() {
cout << "Constructing a directed graph..." << endl;
cout << "Please enter the number of vertices in this graph: ";
int n = 0;
cin >> n;
Graph G(n);
while(1) {
cout << "Adding an directed edge..." << endl;
cout << "Trying to add an edge (-1,-1) indicates the end of adding edges and prints outputs." << endl;
cout << "Please enter the vertex index of the source of the edge to be added: ";
int a;
cin >> a;
cout << "Please enter the vertex index of the target of the edge to be added: ";
int b;
cin >> b;
if( a == -1 && b == -1)
break;
else
G.addEdge(a,b);
}
cout << "A directed graph has been constructed:" << endl;
G.printVertices();
G.printEdges();
cout << "Breadth-First Traversal: ";
G.BFTraversal();
cout << "Depth-First Traversal: ";
G.DFTraversal();
return 0;
}
#include <iostream>
#include <list>
#include <queue>
using namespace std;
class Graph {
public:
Graph(int n);
~Graph();
void addEdge(int src, int tar);
void BFTraversal();
void DFTraversal();
void printVertices();
void printEdges();
private:
int vertexCount;
int edgeCount;
bool** adjMat;
void BFS(int n, bool marked[]);
void DFS(int n, bool marked[]);
};
Graph::Graph(int n=0) {
vertexCount = n;
edgeCount = 0;
if(n == 0)
adjMat = 0;
else {
adjMat = new bool* [n];
for(int i=0; i < n; i++)
adjMat[i] = new bool [n];
for(int i=0; i < n; i++)
for(int j=0; j < n; j++)
adjMat[i][j] = 0;
}
}
Graph::~Graph() {
for(int i=0; i < vertexCount; i++)
delete [] adjMat[i];
delete [] adjMat;
}
void Graph::addEdge(int src, int tar) {
if(src < 0 || tar < 0 || src > vertexCount-1 || tar > vertexCount-1)
cout << "Invalid vertex index! No edge has been added." << endl;
else if(src == tar)
cout << "No self loop! No edge has been added." << endl;
else if (adjMat[src][tar] == 1)
cout << "This edge already exists. No edge has been added." << endl;
else {
adjMat[src][tar] = 1;
edgeCount++;
}
}
void Graph::BFTraversal() {
// TO DO
// You are expected to call BFS() in this function,
// potentially multiple times in loops.
bool *marked = new bool[vertexCount]; // array that mark the visited status of node
for(int i = 0; i < vertexCount; i++)
marked[i] = false; // initialize all elements of maeked array to false initially
// calling BFS on each untraversed node, basically this is useful when we have several components in graph that are not connected with each other
for(int j=0;j<vertexCount;j++)
{
if (marked[j]== false)
{
cout<<" \nTraversing from source : " <<j<<endl; // printing the source node
BFS(j,marked); // calling DFS on untraversed node
}
}
}
void Graph::BFS(int n, bool marked[]) {
// TO DO
// You are expected to use a queue<int> from C++ STL.
// This function is not recursive, and you are expected to use a while loop.
queue<int> queue;
queue.push(n); // pushing the element in queue
marked[n] = true; // mark the visisted element
while (!queue.empty()) {
n = queue.front();
queue.pop();
cout << n << " ";
// Enqueue all adjacent of n and mark them visited
for (int i=n; i<vertexCount ;i++)
{
if (!marked[i] && adjMat[n][i]==1)
{
queue.push(i);
marked[i] = true;
}
}
}
}
void Graph::DFTraversal() {
// TO DO
// You are expected to call DFS() in this function,
// potentially multiple times in loops.
bool *marked = new bool[vertexCount]; // array that mark the visited status of node
for(int i = 0; i < vertexCount; i++)
marked[i] = false; // initialize all elements of maeked array to false initially
// calling DFS on each untraversed node, basically this is useful when we have several components in graph that are not connected with each other
for(int j=0;j<vertexCount;j++)
{
if (marked[j]== false)
{
cout<<" \nTraversing from source : " <<j<<endl; // printing the source node
DFS(j,marked); // calling DFS on untraversed node
}
}
}
void Graph::DFS(int n, bool marked[]) {
// TO DO
// You are asked to implement this function using recursion.
// However, a for loop is expected --- the recursive calls are within the loop.
cout << n << " "; // printing the node
marked[n] = true; // making visited node true
for (int i=n; i<vertexCount ;i++)
{
if (!marked[i] && adjMat[n][i]==1)
{
DFS(i,marked); // calling DFS again for unvisited node
}
}
}
void Graph::printVertices() {
cout << "This directed graph has " << vertexCount << " vertex (vertices), ";
cout << "indexed from 0 to " << vertexCount-1 << endl;
}
void Graph::printEdges() {
cout << "This directed graph has " << edgeCount << " edge(s):" << endl;
for(int i=0; i < vertexCount; i++)
for(int j=0; j < vertexCount; j++)
if(adjMat[i][j])
cout << "(" << i << "," << j << ")" << endl;
}
int main() {
cout << "Constructing a directed graph..." << endl;
cout << "Please enter the number of vertices in this graph: ";
int n = 0;
cin >> n;
Graph G(n);
while(1) {
cout << "Adding an directed edge..." << endl;
cout << "Trying to add an edge (-1,-1) indicates the end of adding edges and prints outputs." << endl;
cout << "Please enter the vertex index of the source of the edge to be added: ";
int a;
cin >> a;
cout << "Please enter the vertex index of the target of the edge to be added: ";
int b;
cin >> b;
if( a == -1 && b == -1)
break;
else
G.addEdge(a,b);
}
cout << "A directed graph has been constructed:" << endl;
G.printVertices();
G.printEdges();
cout << "Breadth-First Traversal: ";
G.BFTraversal();
cout << "\nDepth-First Traversal: ";
G.DFTraversal();
return 0;
}
------------------------------------------------------------------------------------------
screenshot of output (example containing a single connected components)
screenshot of output (example containing a two connected components)
-----------------------------------------------------------------------------------------------------------------------------------------------------------
Please give me a thumbs up when my solution meets your requirement. It motivates us!!
#include <iostream> #include <queue> using namespace std; class Graph { public: Graph(int n); ~Graph(); void addEdge(int...
/* Graph read from file, and represnted as adjacency list. To implement DFS and BFS on the graph */ #include <iostream> #include <sstream> #include <fstream> #include <vector> #include <utility> #include <unordered_map> #include <set> #include <queue> using namespace std; // Each vertex has an integer id. typedef vector<vector<pair<int,int>>> adjlist; // Pair: (head vertex, edge weight) adjlist makeGraph(ifstream& ifs); void printGraph(const adjlist& alist); vector<int> BFS(const adjlist& alist, int source); // Return vertices in BFS order vector<int> DFS(const adjlist& alist, int source); //...
from collections import defaultdict # This class represents a directed graph using # adjacency list representation class Graph: # Constructor def __init__(self): # default dictionary to store graph self.graph = defaultdict(list) # function to add an edge to graph def addEdge(self,u,v): self.graph[u].append(v) # Function to print a BFS of graph def BFS(self, s): # Mark all the vertices as not visited visited = [False] * (len(self.graph)) # Create a queue for BFS queue...
#include <iostream> #include <fstream> using namespace std; //constants const int CAP = 100; //function prototypes bool openFile(ifstream &); void readData(ifstream &, int [], int &); void printData(const int [], int); void sum(const int[], int); void removeItem(int[], int &, int); int main() { ifstream inFile; int list[CAP], size = 0; if (!openFile(inFile)) { cout << "Program terminating!! File not found!" << endl; return -1; } //read the data from the file readData(inFile, list, size); inFile.close(); cout << "Data in file:" <<...
#include <iostream> using namespace std; const int SIZE = 10; void displayGreaterThan(int[], int); void displaySmallerThan(int[],int); void displayArrayContent(int[]); void displayLargestValue(int[]); void displaySmallestValue(int[]); int main(){ int number; int numbers[SIZE] = {9,1,90,98,53,22,76,29,37,65}; cout <<"Enter a number: "; cin >> number; cout << endl; displayGreaterThan(numbers,number); cout << endl; displaySmallerThan(numbers,number); cout << endl; displayArrayContent(numbers); cout << endl; displayLargestValue(numbers); cout << endl; displaySmallestValue(numbers); cout << endl; return 0; } void displayGreaterThan(int value[],int num){ cout << " All larger value(s)than" <<...
#include<iostream> #include<string> #include<iomanip> using namespace std; /* ********* Class Car ************* ********************************* */ class Car { private: string reportingMark; int carNumber; string kind; bool loaded; string choice; string destination; public: Car() { reportingMark = ""; carNumber = 0; kind = "Others"; loaded = 0; destination = "NONE"; } ~Car() { } void setUpCar(string &reportingMark, int &carNumber, string &kind, bool &loaded, string &destination); }; void input(string &reportingMark, int &carNumber, string &kind, bool &loaded,string choice, string &destination); void output(string &reportingMark, int &carNumber,...
#include <iostream> #include <cstdlib> using namespace std; int **dynArray(int row, int cols) { int **myPtr; int lab[4]; myPtr = new int *[row]; for(int i = 0; i < row; i++) myPtr[i] = new int[lab[i]]; for(int i = 0; i<row ; i++) if(myPtr[i] == 0) cout<<"empty"; return myPtr; } void getinput(int ID,int &Station,int &labnumb) { cout<<" Enter your ID number: "<<endl; cin>>ID; cout<<" Enter your station number: "<<endl; cin>>Station; cout<<" Enter your lab number: "<<endl; cin>>labnumb; return; } void logout(int ID,int...
#include "stdafx.h" #include <iostream> using namespace std; class dateType { private: int dmonth; int dday; int dyear; public: void setdate (int month, int day, int year); int getday()const; int getmonth()const; int getyear()const; int printdate()const; bool isleapyear(int year); dateType (int month=0, int day=0, int year=0); }; void dateType::setdate(int month, int day, int year) { int numofdays; if (year<=2008) { dyear=year;...
#include <iostream> using namespace std; bool binarySearch(int arr[], int start, int end, int target){ //your code here } void fill(int arr[], int count){ for(int i = 0; i < count; i++){ cout << "Enter number: "; cin >> arr[i]; } } void display(int arr[], int count){ for(int i = 0; i < count; i++){ cout << arr[i] << endl; } } int main() { cout << "How many items: "; int count; cin >> count; int * arr = new...
#include <iostream> using namespace std; struct node { int base; int power; }; void insert(node ptr[],int basee,int powerr) { ptr[powerr].power=powerr; ptr[powerr].base=basee; } void addition(node ptr1[],int size1,node ptr2[],int size2,node ptr3[],int size3) { for(int j=0;j<=size1;j++) { ptr3[j].base=ptr3[j].base+ptr1[j].base; } for(int j=0;j<=size2;j++) { ptr3[j].base=ptr3[j].base+ptr2[j].base; } } void display(node ptr[],int size) { if(ptr[0].base!=0) cout<<ptr[0].base<<"+"; for(int i=1; i<=size; i++) { if(ptr[i].base!=0) cout<<ptr[i].base<<"x^"<<ptr[i].power<<"+"; } } int main() { bool choice1=true; bool choice2=true; int size1,size2,base1,base2,power1,power2; cout<<"enter the max power in polynominal 1"; cin>>size1; node *a= new node[size1+1]; for(int...
#include <iostream> using namespace std; struct node { int base=0; int power=0; }; void insert(node ptr[],int basee,int powerr) { ptr[powerr].power=powerr; ptr[powerr].base=basee; } void subtract(node ptr1[],int size1,node ptr2[],int size2,node ptr3[]) { for(int j=0;j<=size1;j++) { if(ptr1[j].base!=0) { ptr3[j].base=(ptr3[j].base)+(ptr1[j].base); ptr3[j].power=ptr2[j].power; } } for(int j=0;j<=size2;j++) { if(ptr2[j].base!=0) { ptr3[j].base=(ptr3[j].base)-(ptr2[j].base); ptr3[j].power=ptr2[j].power; } } } void addition(node ptr1[],int size1,node ptr2[],int size2,node ptr3[]) { for(int j=0;j<=size1;j++) { if(ptr1[j].base!=0) { ptr3[j].base=(ptr3[j].base)+(ptr1[j].base); ptr3[j].power=ptr2[j].power; } } for(int j=0;j<=size2;j++) { if(ptr2[j].base!=0) { ptr3[j].base=(ptr3[j].base)+(ptr2[j].base); ptr3[j].power=ptr2[j].power; } } } void display(node ptr[],int size)...