1. Write a C++ class derived from GraphicInterface, as given in Listing 20-1. Us
ID: 3581827 • Letter: 1
Question
1. Write a C++ class derived from GraphicInterface, as given in Listing 20-1. Use an adjacency matrix to represent the graph.
2. Repeat the previous programming problem, but represent the graph using an adjacency list instead of an adjacency matrix.
3. Repeat Programming problems 1 and 2, but allow the graph to be either weighted or unweighted and either directed or undirected.
4. Extend Programming Problem 3 by adding ADT operations such as isConnected and hasCycle. Also, include operations that perform a topological sort for a directed graph without cycles, find the Depth First Search and Breadth First Search spanning trees for a connected graph, and find a minimum spanning tree for a connected undirected graph.
Explanation / Answer
class Graph {
private:
bool** adjacencyMatrix;
int vertexCount;
public:
Graph(int vertexCount) {
this->vertexCount = vertexCount;
adjacencyMatrix = new bool*[vertexCount];
for (int i = 0; i < vertexCount; i++) {
adjacencyMatrix[i] = new bool[vertexCount];
for (int j = 0; j < vertexCount; j++)
adjacencyMatrix[i][j] = false;
}
}
void addEdge(int i, int j) {
if (i >= 0 && i < vertexCount && j > 0 && j < vertexCount) {
adjacencyMatrix[i][j] = true;
adjacencyMatrix[j][i] = true;
}
}
void removeEdge(int i, int j) {
if (i >= 0 && i < vertexCount && j > 0 && j < vertexCount) {
adjacencyMatrix[i][j] = false;
adjacencyMatrix[j][i] = false;
}
}
bool isEdge(int i, int j) {
if (i >= 0 && i < vertexCount && j > 0 && j < vertexCount)
return adjacencyMatrix[i][j];
else
return false;
}
~Graph() {
for (int i = 0; i < vertexCount; i++)
delete[] adjacencyMatrix[i];
delete[] adjacencyMatrix;
}
};
OR================
/ Program to print BFS traversal from a given source vertex. BFS(int s)
// traverses vertices reachable from s.
#include<iostream>
#include <list>
using namespace std;
// This class represents a directed graph using adjacency list representation
class Graph
{
int V; // No. of vertices
list<int> *adj; // Pointer to an array containing adjacency lists
public:
Graph(int V); // Constructor
void addEdge(int v, int w); // function to add an edge to graph
void BFS(int s); // prints BFS traversal from a given source s
};
Graph::Graph(int V)
{
this->V = V;
adj = new list<int>[V];
}
void Graph::addEdge(int v, int w)
{
adj[v].push_back(w); // Add w to v’s list.
}
void Graph::BFS(int s)
{
// Mark all the vertices as not visited
bool *visited = new bool[V];
for(int i = 0; i < V; i++)
visited[i] = false;
// Create a queue for BFS
list<int> queue;
// Mark the current node as visited and enqueue it
visited[s] = true;
queue.push_back(s);
// 'i' will be used to get all adjacent vertices of a vertex
list<int>::iterator i;
while(!queue.empty())
{
// Dequeue a vertex from queue and print it
s = queue.front();
cout << s << " ";
queue.pop_front();
// Get all adjacent vertices of the dequeued vertex s
// If a adjacent has not been visited, then mark it visited
// and enqueue it
for(i = adj[s].begin(); i != adj[s].end(); ++i)
{
if(!visited[*i])
{
visited[*i] = true;
queue.push_back(*i);
}
}
}
}
// Driver program to test methods of graph class
int main()
{
// Create a graph given in the above diagram
Graph g(4);
g.addEdge(0, 1);
g.addEdge(0, 2);
g.addEdge(1, 2);
g.addEdge(2, 0);
g.addEdge(2, 3);
g.addEdge(3, 3);
cout << "Following is Breadth First Traversal "
<< "(starting from vertex 2) ";
g.BFS(2);
return 0;
}
OR
=====================
// C++ program to print DFS traversal from a given vertex in a given graph
#include<iostream>
#include<list>
using namespace std;
// Graph class represents a directed graph using adjacency list representation
class Graph
{
int V; // No. of vertices
list<int> *adj; // Pointer to an array containing adjacency lists
void DFSUtil(int v, bool visited[]); // A function used by DFS
public:
Graph(int V); // Constructor
void addEdge(int v, int w); // function to add an edge to graph
void DFS(int v); // DFS traversal of the vertices reachable from v
};
Graph::Graph(int V)
{
this->V = V;
adj = new list<int>[V];
}
void Graph::addEdge(int v, int w)
{
adj[v].push_back(w); // Add w to v’s list.
}
void Graph::DFSUtil(int v, bool visited[])
{
// Mark the current node as visited and print it
visited[v] = true;
cout << v << " ";
// Recur for all the vertices adjacent to this vertex
list<int>::iterator i;
for (i = adj[v].begin(); i != adj[v].end(); ++i)
if (!visited[*i])
DFSUtil(*i, visited);
}
// DFS traversal of the vertices reachable from v.
// It uses recursive DFSUtil()
void Graph::DFS(int v)
{
// Mark all the vertices as not visited
bool *visited = new bool[V];
for (int i = 0; i < V; i++)
visited[i] = false;
// Call the recursive helper function to print DFS traversal
DFSUtil(v, visited);
}
int main()
{
// Create a graph given in the above diagram
Graph g(4);
g.addEdge(0, 1);
g.addEdge(0, 2);
g.addEdge(1, 2);
g.addEdge(2, 0);
g.addEdge(2, 3);
g.addEdge(3, 3);
cout << "Following is Depth First Traversal (starting from vertex 2) ";
g.DFS(2);
return 0;
}
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.