grlist.cpp

来自「经典c++程序的实现」· C++ 代码 · 共 60 行

// Implementation for graph: Adjacency matrix
#include <stdlib.h>
#include <stdio.h>
#include <iostream.h>
#include <limits.h>

#include "..\..\include\book.h"

#include "..\..\include\grlist.h"  // The ADT

Graph::Graph() {            // Constructor
  Mark = NULL;  list = NULL;
  // At this point, put in appropriate code for creating the graph
}

Graph::~Graph() {           // Destructor: return allocated space
  if (Mark != NULL) delete [] Mark;
  if (list != NULL) {       // Remove all of the edges
    for (int v=0; v<n(); v++)  // For each vertex...
      while (list[v] != NULL) { // return its edges
        Edge temp = list[v];
        list[v] = list[v]->next;
        delete temp;
      }
    delete [] list;         // Now remove the vertex list headers
  }
}

int Graph::n() { return numVertex; } // Number of vertices

int Graph::e() { return numEdge; }   // Number of edges

Edge Graph::first(int v)    // Get the first edge for a vertex
  { return list[v]; }

bool Graph::isEdge(Edge w)  // TRUE if this is an edge
  { return w != NULL; }

Edge Graph::next(Edge w) {  // Get next edge for a vertex
  if (w == NULL) return NULL;
  else return w->next;
}

int Graph::v1(Edge w)       // Return vertex edge comes from
  { return w->v1; }

int Graph::v2(Edge w)       // Return vertex edge goes to
  { return w->v2; }

int Graph::weight(int i, int j) { // Return weight of edge
  for (Edge curr = list[i]; curr != NULL; curr = curr->next)
    if (curr->v2 == j) return curr->weight;
  return INFINITY;
}

int Graph::weight(Edge w) { // Return weight of edge
  if (w == NULL) return INFINITY;
  else return w->weight;
}