Exploring Undirected Graphs in C++ with Adjacency List Representation

Exploring Undirected Graphs in C++ with Object-Oriented Design

In this C++ code snippet, we delve into the world of undirected graphs using the Undirected Graph class. This class not only encapsulates the essential functionalities of initializing the graph and adding edges but also provides a clear representation of the graph through an adjacency list. The code's modularity and object-oriented design make it an excellent educational resource for understanding key graph concepts. By demonstrating the practical implementation of graph operations, from vertex addition to adjacency list retrieval, this code serves as a valuable tool for learners looking to deepen their understanding of graph theory in the context of C++. For students seeking assistance with their C++ assignments, this code provides a practical example and a foundation for mastering graph-related concepts in programming.

Block 1: Class Definition


class UndirectedGraph {
private:
int numVertices; // number of vertices in the graph
vector
> adjList; // adjacency list representation of the graph
public:
UndirectedGraph(int numVertices) {
this->numVertices = numVertices;
adjList.resize(numVertices);
}

This block defines the UndirectedGraph class. It has private members numVertices to store the number of vertices and adjList to store the adjacency list. The constructor initializes the number of vertices and resizes the adjacency list accordingly.

Block 2: addEdge Method


void addEdge(int v, int w) {
adjList[v].push_back(w);
adjList[w].push_back(v); // since it's an undirected graph, we add v to w's adjacency list
}

The addEdge method adds an undirected edge between vertices v and w by updating their respective adjacency lists. It ensures that each vertex is added to the other's adjacency list, as the graph is undirected.

Block 3: getAdjList Method


vector
 getAdjList(int v) {
return adjList[v];
}

The getAdjList method returns the adjacency list for a given vertex v.

Block 4: getNumVertices Method


int getNumVertices() {
return numVertices;
}

The getNumVertices method returns the number of vertices in the graph.

Block 5: Main Function


int main() {
int numVertices = 4;
UndirectedGraph graph(numVertices);
graph.addEdge(0, 1);
graph.addEdge(0, 2);
graph.addEdge(1, 3);
graph.addEdge(2, 3);

In the main function, an instance of the UndirectedGraph class is created with four vertices. Four edges are then added to the graph using the addEdge method.

Block 6: Print Adjacency Lists


for (int i = 0; i < numVertices; i++) {
vector

adjList = graph.getAdjList(i);
cout << "Vertex " << i << " is adjacent to: ";
for (int j = 0; j < adjList.size(); j++) {
cout << adjList[j] << " ";
}
cout << endl;
}

This block iterates through each vertex, retrieves its adjacency list, and prints the vertex along with its adjacent vertices. This demonstrates the functionality of the graph representation.

Block 7: Return Statement


return 0;
}

The main function concludes with a return statement, indicating successful program execution.

Conclusion

In conclusion, this C++ code not only showcases the fundamental principles of undirected graphs but also embodies effective object-oriented design. Its clarity and modular structure make it an ideal resource for those seeking to comprehend graph theory concepts and enhance their programming skills in C++. Whether you're a student tackling assignments or an enthusiast aiming to strengthen your grasp of data structures, this code offers a practical and educational journey. Through the lens of graph manipulation, from initialization to adjacency list exploration, this code serves as a valuable guide, empowering individuals to navigate the intricacies of undirected graphs in C++ with confidence and a deeper understanding of object-oriented programming principles.

C++ Implementation of an Undirected Graph using Adjacency List