class Graph{
private:
typedef struct ArcNode {
int ad;
struct ArcNode* next;
int weight;
}ArcNode;
int max;
typedef struct VNode {
int data;
ArcNode* firstarc;
}VNode;
VNode* vexlist=new VNode[max];
public:
/**
* 类的构造函数
@name Graph(int)
@param arg1 最大的定点数
@return
*/
Graph(int max_v);
/**
* 类的析构函数
@name ~Graph()
@param
@return
*/
~Graph();
/**
* 向图中加入(s, t)， 权重为w的双向边
@name addedge(int, int, int)
@param arg1 边的顶点1
@param arg2 边的顶点2
@param arg3 边的权重
@return void
*/
void addedge(int s, int t, int w);
/**
* 询问这张图的最小生成树(prim算法实现)
@name int prim()
@param
@return int 最小生成树的权值
*/
int prim();
下面是cpp的部分，这个类是用邻接表存储写的一个图的类，完成图的存储，prim算法。我在类的数据域中声明 VNode* vexlist=new VNode[max]，但是在析构函数中delete[] vexlist 出错，请大佬批评指正。
Graph::Graph(int max_v){
max = max_v+1;
vexlist[0].data= 0;//第一个元素不储存元素
vexlist[0].firstarc = NULL;
for (int i = 1; i < max; i++)
{
vexlist[i].data = i;//图的顶点1，2，3……
vexlist[i].firstarc = NULL;
}
}
Graph::~Graph(){
for (int i = 1; i < max; i++)
{
ArcNode* p = vexlist[i].firstarc;
while (p != NULL)
{
ArcNode* q = p;
p= p->next;
delete q;
}
}
delete[] vexlist;
}
void Graph::addedge(int s, int t, int w){
ArcNode* p = new ArcNode;
if (vexlist[s].firstarc == NULL)
{
vexlist[s].firstarc = p;
p->ad = t;
p->weight = w;
p->next = NULL;
}
else
{
ArcNode* q = vexlist[s].firstarc;
while (q->next != NULL)
{
q = q->next;
}
q->next = p;
p->ad = t;
p->weight = w;
p->next = NULL；
}
}
int Graph::prim(){
int* adj = new int[max];
int* low = new int[max];
ArcNode* p;
int sum = 0;
int tn = 1;
for (int i = 0; i < max; i++)
{
adj[i] = -1;
low[i] = 10000;
}
int min = low[1];
adj[1] = 0;
for (int i = 1; i < max; i++)
{
if (adj[i]==0)
{
p = vexlist[i].firstarc;
while (p != NULL)
{
adj[p->ad] = i;
if (p->weight < low[p->ad])
{
low[p->ad] = p->weight;
}
p = p->next;
}
}
for (int j = 1; j < max; j++)
{
if (adj[j]!=-2&&adj[j]!=0)
{
if (min > low[j])
{
min = low[j];
tn = j;
}
}
}
sum += min;
min = low[1];
adj[tn] = 0;
adj[i] = -2;
if (i == max-2)
{
break;
}
}
delete[] adj;
delete[] low;
return sum;
}
