C++ Implementation of an Undirected Graph using Adjacency List
.png){kind=avatar}
- Exploring Undirected Graphs in C++ with Object-Oriented Design
- Block 1: Class Definition
- Block 2: addEdge Method
- Block 3: getAdjList Method
- Block 4: getNumVertices Method
- Block 5: Main Function
- Block 6: Print Adjacency Lists
- Block 7: Return Statement
- Conclusion
This C++ code introduces an UndirectedGraph class that represents an undirected graph through an adjacency list. The class encapsulates methods to initialize the graph, add edges between vertices, obtain the adjacency list for a vertex, and retrieve the total number of vertices. In the main function, a graph instance is created with four vertices, and edges are added. The code concludes by printing the adjacency lists for each vertex. This implementation serves as a foundational example of managing undirected graphs, showcasing key concepts such as graph initialization, edge addition, and adjacency list retrieval in an object-oriented C++ context.
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.
Related Samples
Explore our C++ Assignment Samples for expert solutions to diverse programming problems. Covering topics like classes, templates, and standard library usage, these examples offer clear explanations and detailed implementations. Perfect for students aiming to strengthen their C++ skills and excel academically with practical, educational resources.
C++
C++
C++
C++
C++
C++
C++
C++
C++
C++
C++
C++
C++
C++
C++
C++
C++
C++
C++
C++