maxst.h

来自「图论：最大支撑树算法实现 GraphM.h GraphOpr.h MaxS」· C头文件 代码 · 共 53 行

#ifndef MAXST_H
#define MAXST_H

#include "GraphM.h"

void MaxST(Graph* G, int& s, Graph* max)
{
  int *V;
  V = new int(G->n());
  int *D;
  D = new int[G->n()];
  for (int i = 0; i < G->n(); i++)
  {
	D[i] = 0;
	V[i] = 0;
  }

  int d;

  G->setMark(s, VISITED);
  d = s;
  D[d] = 0;
  
  for (int j = 0; j < G->n(); j++)
	if (G->getMark(j) == UNVISITED && D[j] < G->weight(d, j))
	{
	  D[j] = G->weight(d, j);
	  V[j] = d;
	}

  int k;

  for (i = 1; i < G->n(); i++)
  {
    k = 0;
	for (j = 0; j < G->n(); j++)
	  if (D[k] < D[j])
		k = j;
	G->setMark(k, VISITED);
	max->setEdge(V[k], k, G->weight(V[k], k));
	d = k;
    D[d] = 0;
    for (j = 0; j < G->n(); j++)
      if (G->getMark(j) == UNVISITED && D[j] < G->weight(d, j))
	  {
	    D[j] = G->weight(d, j);
	    V[j] = d;
	  }
  }
  cout << max->e() << endl;
}

#endif