graphm.h

图论：最大支撑树算法实现 GraphM.h GraphOpr.h MaxST.cpp MaxST.dsp MaxST.dsw MaxST.h MaxST.ncb MaxST.opt

#ifndef GRAPHM_H
#define GRAPHM_H

#include <assert.h>
#include <stdio.h>
#include <ctype.h>

#define UNVISITED 0
#define VISITED 1
#define DEAD -1

class Graph
// 矩阵法类定义
{
private:
  int numVertex, numEdge; // 点数, 边数
  int **matrix;           // 矩阵指针
  int *mark;              // 标志数组
  int directedFlag;       // 有向性标志: 0  无向; 1  有向
public:
  Graph(int numVert)   // 初始化n点图
  {
    numVertex = numVert;
    numEdge = 0;
    directedFlag = 0;
    mark = new int[numVert]; // 初始化边数组指针
    for (int i=0; i<numVertex; i++)
    {
	  matrix = (int**) new int*[numVertex]; // 建立矩阵
      mark[i] = UNVISITED;
	}
    for (i=0; i<numVertex; i++)
      matrix[i] = new int[numVertex];
    for (i=0; i< numVertex; i++) // 置零
      for (int j=0; j<numVertex; j++) matrix[i][j] = 0;
  }

  ~Graph() // 析构
  {
    delete [] mark;
    for (int i=0; i<numVertex; i++)
      delete [] matrix[i];
    delete [] matrix;
  }
  int directed() { return directedFlag;} // Return 有向性标志
  int n() { return numVertex; } // Return 点数
  int e()   // Return 边数, 由有向性和numEdge共同决定
  {
	if (directedFlag == 0)
      return numEdge / 2;
	else
	  return numEdge;
  }

  int first(int v)  // Return 点v连接的第一点, i = numVertex时不存在
  {
	int i;
    for (i=0; i<numVertex; i++)
      if (matrix[v][i] != 0) return i;
    return i;
  }

  int next(int v1, int v2) // Return 点v1自v2以后的第一连接点
                           // i = numVertex时不存在
  {
    int i;
    for(i=v2+1; i<numVertex; i++)
      if (matrix[v1][i] != 0) return i;
    return i;
  }
  
  void setDirect(int flag)
  {
	if (flag == 0 || flag == 1)
	  directedFlag = flag;
  }

  void setEdge(int v1, int v2, int wgt)  // 建立边
  {
    assert(wgt > 0);
	if (matrix[v1][v2] == 0) numEdge++;
    matrix[v1][v2] = wgt;
	if (directed() == 0)
	{
	  if (matrix[v2][v1] == 0) numEdge++;
      matrix[v2][v1] = wgt;
	}
  }

  void delEdge(int v1, int v2) // 删除边
  {
    if (matrix[v1][v2] != 0) numEdge--;
    matrix[v1][v2] = 0;
	if (directed() == 0)
	{
	  if (matrix[v2][v1] != 0) numEdge--;
      matrix[v2][v1] = 0;
	}
  }

  int weight(int v1, int v2) { return matrix[v1][v2]; }
  int getMark(int v) { return mark[v]; }
  void setMark(int v, int val) { mark[v] = val; }
};

#endif