Write a program to implement an undirected graph. Use the adjacency matrix to im

Question

Write a program to implement an undirected graph. Use the adjacency matrix to implement the graph. Let your program be menu driven. Allowing the user the following options:


1. Create graph
2. Insert 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. Exit program

Programming guidelines
- 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.
- Option 1 - Allows the user to create a new graph with no edges. User enters the number of vertices.
- Option 2 - Allows the user to insert an edge. The user must specify the two vertices that the edge will connect.
- 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



Sample graph class definition

const int MAX = 100;
class graph
{ private:
int n; // number of vertices
int matrix[MAX][MAX];//adjacency matrix
bool visited[MAX];

public:
graph(int v);
/* initializes the number of vertices to v,
and fills matrix with zeros */

void AddEdge(int x, int y);
//add an edge between v and w

void printAdjacent(int v);
//print all vertices that are adjacent to v

void printMatrix();
/* print the content of the adjacency matrix with one row per line of output. */


//Add in other methods as needed
};

Explanation / Answer

#ifdef _graph_h #include "genlib.h" /* * Implementation notes: NodeCompare, ArcCompare * --------------------------------------------- * These generic functions compare nodes and arcs by comparing * the node names alphabetically. */ template int NodeCompare(NodeType *n1, NodeType *n2) { if (n1->name == n2->name) return 0; return (n1->name name) ? -1 : +1; } template int ArcCompare(ArcType *a1, ArcType *a2) { NodeType *n1 = a1->start; NodeType *n2 = a2->start; int cmp = NodeCompare(n1, n2); if (cmp != 0) return cmp; n1 = a1->finish; n2 = a2->finish; return NodeCompare(n1, n2); } /* * Implementation notes: Constructor * --------------------------------- * The constructor requires no code in its function body, but * does use the initialization list to set up the nodes and * arc sets with the appropriate comparison functions. */ template Graph::Graph() : nodes(NodeCompare), arcs(ArcCompare) { /* Empty */ } template Graph::~Graph() { clear(); } template void Graph::clear() { foreach (NodeType *node in nodes) { delete node; } foreach (ArcType *arc in arcs) { delete arc; } arcs.clear(); nodes.clear(); nodeMap.clear(); } template NodeType *Graph::addNode(NodeType *node) { nodes.add(node); nodeMap[node->name] = node; return node; } template NodeType *Graph::addNode(string name) { NodeType *node = new NodeType(); node->arcs = Set(ArcCompare); node->name = name; return addNode(node); } template ArcType *Graph::addArc(ArcType *arc) { arc->start->arcs.add(arc); arcs.add(arc); return arc; } template ArcType *Graph::addArc(NodeType *n1, NodeType *n2) { ArcType *arc = new ArcType(); arc->start = n1; arc->finish = n2; arc->cost = 1; return addArc(arc); } template ArcType *Graph::addArc(string s1, string s2) { return addArc(getNode(s1), getNode(s2)); } template bool Graph::isConnected(NodeType *n1, NodeType *n2) { foreach (ArcType *arc in n1->arcs) { if (arc->finish == n2) return true; } return false; } template bool Graph::isConnected(string s1, string s2) { return isConnected(getNode(s1), getNode(s2)); } template NodeType *Graph::getNode(string name) { if (nodeMap.containsKey(name)) return nodeMap.get(name); return NULL; } template Set & Graph::getNodeSet() { return nodes; } template Set & Graph::getArcSet() { return arcs; } template Set & Graph::getArcSet(NodeType *node) { return node->arcs; } #endif

Related Questions

Navigate

• Browse (All)
• Browse W
• Subjects

---

---

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