Data Structures Project 13 Note that adjacency matrix graph implementation in yo

Question

Data Structures Project 13

Note that adjacency matrix graph implementation in your book (section 11.2, fig. 11.6) does not provide means to actually create the graph. Implement 11.6 algorithm and extend it so that a user can read graph description from a file. This data can then be used by setEdge function to build the graph. Provide a main program that 'demos' different graph functions.

_____________________

THIS IS FIGURE 11.6!!!

_____________________

/** Graph: Adjacency matrix */
class Graphm implements Graph {
private int[][] matrix; // The edge matrix
private int numEdge; // Number of edges
public int[] Mark; // The mark array
public Graphm() {} // Constructors
public Graphm(int n) {
Init(n);
}
public void Init(int n) {
Mark = new int[n];
matrix = new int[n][n];
numEdge = 0;
}
public int n() { return Mark.length; } // # of vertices
public int e() { return numEdge; } // # of edges
/** @return v’s first neighbor */
public int first(int v) {
for (int i=0; i if (matrix[v][i] != 0) return i;
return Mark.length; // No edge for this vertex
}
/** @return v’s next neighbor after w */
public int next(int v, int w) {
for (int i=w+1; i if (matrix[v][i] != 0)
return i;
return Mark.length; // No next edge;
}
/** Set the weight for an edge */
public void setEdge(int i, int j, int wt) {
assert wt!=0 : "Cannot set weight to 0";
if (matrix[i][j] == 0) numEdge++;
matrix[i][j] = wt;
}
/** Delete an edge */
public void delEdge(int i, int j) { // Delete edge (i, j)
if (matrix[i][j] != 0) numEdge--;
matrix[i][j] = 0;
}
/** Determine if an edge is in the graph */
public boolean isEdge(int i, int j)
{ return matrix[i][j] != 0; }

}

Explanation / Answer

int main()
{
   int v,e,frst,wght,get;
   boolean result;
   Init(5);
   v = n();
   cout<<"Vertices are "<<v;
   e = e();
   cout<<"Edges are "<<e;
frst = first(v);
   get = next(v,wght);
   cout<<get;
setEdge(1,2,5);
   result = isEdge(1,2);
   cout<<result;
   delEdge(1,2);
   result = isEdge(1,2);
   cout<<result;
   cout<<"frst;
  
   return 0;1
   
}

Related Questions

Navigate

• Browse (All)
• Browse D
• Subjects

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