grmat.cpp

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

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

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

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

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

Graph::~Graph() {          // Destructor: return allocated space
  if (Mark != NULL) delete [] Mark;
  if (matrix != NULL) delete [] matrix;
}

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

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

Edge Graph::first(int v) { // Get the first edge for a vertex
  int stop = (v+1) * numVertex; // Position at end of v's row
  for (int pos = v*numVertex; pos<stop; pos++)
    if (matrix[pos] != NOEDGE)  return &matrix[pos];
  return NULL;
}

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
  int stop = (v1(w) + 1) * numVertex; // Position at end of row
  for (int pos = (w - matrix) + 1; pos < stop; pos++)
    if (matrix[pos] != NOEDGE)  return &matrix[pos];
  return NULL;
}

int Graph::v1(Edge w)      // Return vertex edge comes from
  { return (w - matrix) / numVertex; } // Pointer arithmetic

int Graph::v2(Edge w)      // Return vertex edge goes to
  { return (w - matrix) % numVertex; } // Pointer arithmetic

int Graph::weight(int i, int j) {  // Return weight of edge
  if (matrix[i*numVertex + j] == NOEDGE) return INFINITY;
  else return matrix[i*numVertex + j];
}

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