[ Data Structures ] Graphs ( using C++ ). Write a program to implement an undire

Question

[Data Structures] Graphs (using C++).

Write a program to implement an undirected graph. Use the adjacency matrix to implement the graph. Let your program be menu driven. Represent a vertex by using the index value of the array. Let the maximum number of vertices be 100. For example, if the number of vertices is 5, the vertices are 0,1, 2, 3 and 4. Start the program by prompting the user for the number of vertices. Then create a graph with no edges. Allowing the user the following options: 1. Insert an edge 2. Delete an edge 3. Print Adjacency Matrix 4. List all vertices that are adjacent to a specified vertex. 5. Print out vertices using depth first search 6. Print out vertices using breadth first search 7. Check for connectivity 8. Check for completeness 9. Exit program Programming guidelines - Options 1, 2, 3, 4 and 9 are required. Additional implemented options are extra credit. Option 1 - Allows the user to insert an edge. The user must specify the two vertices that the edge will connect. Option 2 - Allows the user to delete an edge. The user must specify the two vertices connecting the edge that is to be deleted. Option 3 - Print out the adjacency matrix (one row per line of output) Option 4 - The user enters a vertex, and the program prints out all of the vertices that are adjacent to the specified vertex. Option 5 - Print out the vertices using the depth first search Option 6 - Print out the vertices using the breadth first search Option 7 - Print out whether or not the graph is connected Option 8 - Print out whether or not the graph is a complete graph

Explanation / Answer

#include <iostream>
#include <stack>
using namespace std;

const int MAX = 100;
class graph
{
private:
int n; // number of vertices
int matrix[MAX][MAX];
bool visited[MAX];
public:
graph(int v)
{
for(int i=0; i<v; i++)
for(int j=0; j<v; j++) matrix[i][j]=0;
}

void AddEdge(int v, int w)
{
if(v >= n || w >= n)
{
cout << " This graph has vertices : 0 to " << n-1 << " only. Please pass a valid value. ";
}
else
{
matrix[v][w] = 1;
matrix[w][v] = 1;
}
}

void DeleteEdge(int v, int w)
{
if(v >= n || w >= n)
{
cout << " This graph has vertices : 0 to " << n-1 << " only. Please pass a valid value. ";
}
else
{
matrix[v][w] = 0;
matrix[w][v] = 0;
}
}

void printAdjacent(int v)
{
cout << " Adjacanet Vertices for " << v << " are : ";
for(int i=0; i<n; i++)
{
if(matrix[v][i] > 0) cout << i << " ";
}
cout << endl;
}

void printMatrix()
{
cout << endl;
for(int i=0; i<n; i++)
{
for(int j=0; j<n; j++)
{
cout << matrix[i][j] << " ";
}
cout << endl;
}
cout << endl;
}

void dfs()
{
bool visited[n] = {false};
stack<int> s;
s.push(0); // pushed the first vertex in stack

while(!s.empty())
{
int vertex = s.top();
visited[vertex] = true;
cout << vertex << " ";
s.pop();
for(int j=0; j<n; j++)
{
if(matrix[vertex][j]>0 && visited[j]==false)
{
s.push(j);
}
}
}

for(int i=0; i<n; i++)
{
if(visited[i] == false)
{
cout << i << " ";
}
}
cout << endl;
}
};

int main()
{
int n, op, v, w;
cout << "Enter the number of vertices";
cin >> n;
graph g(n);

cout << " Select one option from below : ";
cout << " 1. Insert an edge ";
cout << " 2. Delete an edge ";
cout << " 3. Print Adjacency Matrix ";
cout << " 4. List adjacent vertices ";
cout << " 5. Print vertices using DFS ";
cout << " 6. Print vertices using BFS ";
cout << " 7. Check for connectivity ";
cout << " 8. Check for completeness ";
cout << " 9. Exit Program ";
cin >> op;

switch(op)
{
case 1 : cin >> v >> w; g.AddEdge(v,w); break;
case 2 : cin >> v >> w; g.DeleteEdge(v,w); break;
case 3 : g.printMatrix(); break;
case 4 : cin >> v; g.printAdjacent(v); break;
case 5 : g.dfs(); break;
/*case 6 : bfs(); break;
case 7 : isConnected(); break;
case 8 : isComplete(); break; */
case 9 : exit(0); break;
default : cout << " Wrong option entered "; break;
}
return 0;
}

Related Questions

Navigate

• Browse (All)
• Browse #
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.