Graphs ( Data Structures ) . Write a program to implement an undirected graph. U
ID: 3693694 • Letter: G
Question
Graphs (Data Structures).
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: Insert an edge Delete an edge Print Adjacency Matrix List all vertices that are adjacent to a specified vertex. Print out vertices using depth first search Print out vertices using breadth first search Check for connectivity Check for completeness 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 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 v, int w);//add an edge between v and w void DeleteEdge(int v, int w);//delete the edge between v and w int 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
import hclinfosys.ds.linklist.DoublyLinkList;
import hclinfosys.ds.queue.Queue;
import hclinfosys.ds.stack.StackUsingArray;
import java.util.Scanner;
/*
* This class represent the Graph Vertex.
* @author : Madan Gopal Singh
* @version : 1.0
* @date : 09th April, 2014
*/
class GraphVertex{
int id;
DoublyLinkList connectedEdges = null;
boolean isVisited = false;
public GraphVertex() {}
public GraphVertex(int id){
this.id=id;
}
}
/*
* This class demonstrates Graph Implementation in java with Insert/Delete/Traversal/Find Operations.
* @author : Madan Gopal Singh
* @version : 2.0
* @date : 11th April, 2014
*/
public class Graph {
public static int NO_OF_VERTICES = 7;
public static int TOP = -1;
public static GraphVertex[] vertices;
public Graph() {}
/**
* This method add new vertex in graph.
* @param vertexToBeInserted.
* @return void.
*/
public static void addNewVertex(GraphVertex vertexToBeInserted){
if(TOP==NO_OF_VERTICES-1){
System.out.println("Graph Size Exceeded");
}else{
TOP=TOP+1;
vertices[TOP] = vertexToBeInserted;
System.out.println("Vertex Inserted at "+TOP+" with value : "+vertices[TOP].id);
}
}
/**
* This method remove vertex from graph.
* @param vertexToBeRemoved.
* @return void.
*/
public static void removeVertex(GraphVertex vertexToBeRemoved){
if(TOP==-1){
System.out.println("No Vertex in Graph");
}else{
//Removing Edges connected to vertex
DoublyLinkList startNode = vertexToBeRemoved.connectedEdges;
while(startNode!=null){
System.out.println("Node Info : "+startNode.id+" Index of Vertex : "+Graph.getVertexIndex(startNode.id));
GraphVertex destinationVertex = vertices[Graph.getVertexIndex(startNode.id)];
Graph.removeEdge(vertexToBeRemoved, destinationVertex);
startNode = startNode.next;
}
//Removing Vertex
int indexOfVertex = Graph.getVertexIndex(vertexToBeRemoved.id);
for(int i = indexOfVertex;i=0){
if(String.valueOf(vertices[i].id).equalsIgnoreCase((String)obj.toString())){
return i;
}
i = i-1;
}
return -1;
}
}
/**
* This method print all vertices of the Graph.
* @param void.
* @return void.
*/
public static void printAllVertices(){
if(TOP == -1){
System.out.println("Graph has no vertices");
}else{
int i = TOP;
while(i>=0){
System.out.println("Element at position "+ i + " is :- "+vertices[i].id);
i = i-1;
}
}
}
/**
* This method print the Adjancy list of the Graph
* @return void
*/
public static void printAdjancyList(){
for(int i = 0; i=0){
vertices[i].isVisited = false;
System.out.println("Vertex "+ vertices[i].id + " is marked un visited.");
i = i-1;
}
}
}
/**
* This method prints the depth first traversal of the Graph from starting vertex.
* @param void.
* @return void.
*/
public static void depthFirstTraversal(GraphVertex startingVertex){
markAllVerticesNotVisted();//Marking all vertices not visited
int removedVertexId,removedVertexIndex;
String depthFirstTraversalSequence = "";
StackUsingArray.STACK_SIZE = NO_OF_VERTICES;
StackUsingArray.stackElements = new Object[StackUsingArray.STACK_SIZE];
StackUsingArray.push(vertices[0].id);
while(!StackUsingArray.isEmpty()){
Object removed = StackUsingArray.pop();
if(removed!=null){
removedVertexId = Integer.parseInt(removed.toString());
depthFirstTraversalSequence += removedVertexId+" ";
removedVertexIndex = Graph.getVertexIndex(removedVertexId);
vertices[removedVertexIndex].isVisited = true;
DoublyLinkList edges = vertices[removedVertexIndex].connectedEdges;
while(edges!=null){
if(vertices[Graph.getVertexIndex(edges.id)].isVisited==false && StackUsingArray.isElementExists(edges.id)==false){
StackUsingArray.push(edges.id);
}
edges = edges.next;
}
}
}
System.out.println("Depth First Traversal Sequence : "+depthFirstTraversalSequence);
}
/**
* This method prints the breadth first traversal of the Graph from starting vertex.
* @param void.
* @return void.
*/
public static void breadthFirstTraversal(GraphVertex startingVertex){
markAllVerticesNotVisted();//Marking all vertices not visited
int removedVertexId,removedVertexIndex;
String breadthFirstTraversalSequence = "";
Queue.QUEUE_SIZE = NO_OF_VERTICES;
Queue.queueList = new Object[Queue.QUEUE_SIZE];
Queue.insertIntoQueue(vertices[0].id);
while(!Queue.isEmpty()){
Object removed = Queue.removeFromQueue();
if(removed!=null){
removedVertexId = Integer.parseInt(removed.toString());
breadthFirstTraversalSequence += removedVertexId+" ";
removedVertexIndex = Graph.getVertexIndex(removedVertexId);
vertices[removedVertexIndex].isVisited = true;
DoublyLinkList edges = vertices[removedVertexIndex].connectedEdges;
while(edges!=null){
if(vertices[Graph.getVertexIndex(edges.id)].isVisited==false && Queue.isElementExists(edges.id)==false){
Queue.insertIntoQueue(edges.id);
}
edges = edges.next;
}
}
}
System.out.println("Breadth First Traversal Sequence : "+breadthFirstTraversalSequence);
}
/**
* This method main method to perform the Doubly Link List Operations.
* @param args command line argument list
* @return void.
*/
public static void main(String[] args) {
int userOperation = 0, vertexId=-1,fromVertexId=-1,toVertexId=-1,fromVertexIndex=-1,toVertexIndex=-1;
vertices = new GraphVertex[NO_OF_VERTICES];
GraphVertex vertexToBeInserted = null,sourceVertex = null,destinationVertex = null;
Scanner sc = new Scanner(System.in);
do{
String menuString = " Simple Undirected Graph What operation you want to perform?"+
" 1. Insert New Vertex"+
" 2. Insert New Edge"+
" 3. Remove Vertex"+
" 4. Remove Edge"+
" 5. Breadth First Traversal"+
" 6. Depth First Traversal"+
" 7. Print All Vertices"+
" 8. Print Adjancy List Representation"+
" -1. Exit from Menu"+
" Please enter Operation Number : ";
System.out.println(menuString);
userOperation = sc.nextInt();
switch(userOperation){
case 1:
System.out.println("Plese enter vertex Id to Insert: ");
vertexId = sc.nextInt();
vertexToBeInserted = new GraphVertex(vertexId);
System.out.println("Adding New Vertex");
Graph.addNewVertex(vertexToBeInserted);
break;
case 2:
System.out.println("Plese enter FROM vertex Id : ");
fromVertexId = sc.nextInt();
fromVertexIndex = Graph.getVertexIndex(fromVertexId);
System.out.println("Plese enter TO vertex Id : ");
toVertexId = sc.nextInt();
toVertexIndex = Graph.getVertexIndex(toVertexId);
System.out.println("From Vertext Index : "+fromVertexIndex);
System.out.println("To Vertext Index : "+toVertexIndex);
if(fromVertexIndex!=-1&&toVertexIndex!=-1){
sourceVertex = vertices[fromVertexIndex];
destinationVertex = vertices[toVertexIndex];
System.out.println("Destination Vertex Id : "+destinationVertex.id);
System.out.println("Adding Edge");
if(!Graph.isEdgeExists(sourceVertex, destinationVertex)){
Graph.addNewEdge(sourceVertex, destinationVertex);
}else{
System.out.println("Simple Graph doesn't allow multiple Edges. Please try new pair");
}
}
break;
case 3:
System.out.println("Plese enter vertex Id to Remove: ");
vertexId = sc.nextInt();
fromVertexIndex = Graph.getVertexIndex(vertexId);
if(fromVertexIndex!=-1){
vertexToBeInserted = vertices[fromVertexIndex];
System.out.println("Removing Vertex");
Graph.removeVertex(vertexToBeInserted);
}
break;
case 4:
System.out.println("Plese enter FROM vertex Id for Remove: ");
fromVertexId = sc.nextInt();
fromVertexIndex = Graph.getVertexIndex(fromVertexId);
System.out.println("Plese enter TO vertex Id for Remove: ");
toVertexId = sc.nextInt();
toVertexIndex = Graph.getVertexIndex(toVertexId);
if(fromVertexIndex!=-1&&toVertexIndex!=-1){
sourceVertex = vertices[fromVertexIndex];
destinationVertex = vertices[toVertexIndex];
System.out.println("Removing Edge");
if(Graph.isEdgeExists(sourceVertex, destinationVertex)){
Graph.removeEdge(sourceVertex, destinationVertex);
}else{
System.out.println("Edge doesnit exists between these pair of vertices. Please try new pair");
}
}
break;
case 5:
System.out.println("Breadth First Traversal from
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.