there is my final code for implementing a Graph in C++ using adjacency list and Object-oriented. I got some help from StackOverflow and it was really helpful, but now I would ask about some advice for improving and a possible way of implementing two functions: isPath( v, w ) for finding if two nodes are connected and isConnected(graph) returning "yes" if the graph is strongly connected otherwise "no".
The code:
#include <iostream>
#include <vector>
using namespace std;
struct Edge {
int source;
int target;
};
class Graph
{
private:
int numOfNodes;
vector<vector<int>> baseVec;
public:
Graph(int numOfNodes) : numOfNodes(numOfNodes), baseVec(numOfNodes) {}
void newEdge(Edge edge) {
if (edge.source >= numOfNodes || edge.target >= numOfNodes
|| edge.source < 0 || edge.target < 0) {
cout << "Invalid edge!\n";
return;
}
baseVec[edge.source].emplace_back(edge.target);
baseVec[edge.target].emplace_back(edge.source);
}
void display() {
for (vector<vector<int>>::size_type i = 0; i < baseVec.size(); i++) {
cout << "\n Adjacency list of vertex " << i << "\n head: ";
for (vector<int>::size_type j = 0; j < baseVec[i].size(); j++)
cout << baseVec[i][j] << " ";
std::cout << std::endl;
}
}
};
int main() {
int vertex;
cout << "Enter number of nodes: ";
cin >> vertex;
Graph graph(vertex);
while (true) {
int source, target;
cout << "Enter edge ex.1 2 (-1 -1 to exit): \n";
cin >> source >> target;
if ((source == -1) && (target == -1))
break;
graph.newEdge({ source, target });
}
graph.display();
return 0;
}
I really can't find many things to change, so I wrote the isConnected() function. Maybe it has some weaknesses or errors. Hope it's useful and I'm still waiting for advice. Thank you!
Code inside the class:
bool isConected(std::vector<int> nodeVec)
{
for (st
d::vector<std::vector<int>>::size_type i = 0; i < baseVec.size(); i++)
{
if (baseVec[i].empty())
{
return false;
}
}
for (std::vector<std::vector<int>>::size_type i = 0; i < baseVec.size(); i++)
{
for (std::vector<int>::size_type j = 0; j < baseVec[i].size() + 1; j++)
{
if (baseVec[i][j] == nodeVec[j + 1])
{
return true;
}
}
}
}
The line in main:
std::vector<int> nodeVec;
for (int i = 0; i < vertex; i++)
{
nodeVec.emplace_back(i);
}
And:
if (graph.isConected(nodeVec) == true)
{
std::cout << "Yes\n";
}
else
{
std::cout << "No\n";
}