The greedy algorithm will make the following choices. First edge chosen: (0,1) Second edge chosen: (2,5) Third edge chosen: (3,4)..... At this point no more edges can be chosen, and the matching contains 3 edges. Note that the greedy static algorithm uses the name of a vertex as a tie-breaker when two vertices have the same degree. If instead we use a greedy by dynamic degrees strategy, we get the following solution:

This is what my solution should return First edge chosen: (0,1) Second edge chosen: (4,3) since vertex 4 now has d = 1, which is lowest Third edge chosen: (2,6) since vertices 6 and 7 now both have d = 1, and our tie-breaker rule picks vertex 6 Fourth edge chosen: (5,7) .. below is the code that i have written already

public void runAlgorithm( AdjacencyListGraph g ){

// initialize all vertices to be FREE (ie unmatched) for ( Vertex v : g.vertices() ){ v.put ( VERTEX_STATUS, FREE ); v.put(DEGREE, g.degree(v)); }

// initialize all the edges to be FREE (not in the matching) for ( Edge e : g.edges() ){ e.put ( EDGE_STATUS, FREE );

}

VertexDegreeComparator mycomp = new VertexDegreeComparator();

PriorityQueue myheap = new PriorityQueue(1000, new VertexDegreeComparator()); for (Vertex v : g.vertices()) { myheap.add(v);

} while (!myheap.isEmpty()) { Vertex vin = myheap.poll();

{

if(vin.get(VERTEX_STATUS)== FREE){ Iterable> edges = g.incidentEdges(vin); Edge bestedge = null; Vertex bestneighbor = null;

// examine every edge in the graph, if it is possible to // add it to the matching, then do so. for ( Edge currEdge : edges ) { // not needed currEdge.put(EDGE_STATUS, FREE); // compare u_neighbor with bestneighbor. Vertex u_neighbor = g.opposite(vin, currEdge); if (u_neighbor.get(VERTEX_STATUS)==FREE) { // if (mycomp.compare(u_neighbor, bestneighbor))

if(bestneighbor==null){

bestneighbor=u_neighbor; bestedge=currEdge; } else if (mycomp.compare(bestneighbor,u_neighbor) > 0) {

bestneighbor = u_neighbor ; bestedge = currEdge; }

} } // end of for all neighbors loop if (bestedge != null ){ // add this edge to the solution matching bestneighbor.put ( VERTEX_STATUS, MATCHED ); vin.put ( VERTEX_STATUS, MATCHED ); bestedge.put ( EDGE_STATUS, MATCHED); // lower the degees }

} }

} } public void draw ( Graphics screen, AdjacencyListGraph testGraph, int minDimension ) { drawNodes ( screen, testGraph, minDimension ); drawEdges ( screen, testGraph, minDimension ); } }