我编写了以下代码来处理 p3.ppm 类型的图像，但是我遇到了分割错误。我使用 prims 算法进行多次分割的最小生成树并删除具有最小权重的边缘。
#include <iostream>
#include <stdio.h>
#include <time.h>
#include <stdlib.h>
#define INT_MAX 10e5
using namespace std;
bool ifvalid(int i,int j,int n,int m)
{
if(i<0 || i>=m || j < 0||j>=n)
return false;
return true;
}
struct cordi
{
int row,col;
};
struct pixel
{
int index;
int r,g,b;
};
struct node
{
int dest,weight;
struct node* next;
};
struct adjList
{
int s;
node *head;
};
struct graph
{
int NumVertices;
adjList *arr;
};
void addEdge(graph *g,int index,int weight,int dest)
{
node *newNode=(node *)malloc(sizeof(node));
newNode->dest=g->arr[dest].s;
newNode->weight=weight;
newNode->next=NULL;
node *temp=g->arr[index].head;
node *parent=temp;
if(temp==NULL)
g->arr[index].head=newNode;
else
{
parent=temp;
temp=temp->next;
while(temp!=NULL)
{
if(temp->dest==dest)
return;
parent=temp;
temp=temp->next;
}
parent->next=newNode;
}
}
graph* generateGraph(int **r,int **g,int **b,int n,int m)
{
int i,j,x,y,index,dest,weight,v;
graph *G=(graph*)malloc(sizeof(graph));
G->NumVertices=n*m;
v=G->NumVertices;
G->arr=(adjList*)malloc(v *sizeof(adjList));
int counter=0;
for(i=0;i<v;i++)
{
G->arr[i].head=NULL;
G->arr[i].s=counter;
counter++;
}
for(i=0;i<m;i++)
{
for(j=0;j<n;j++)
{
index=i*n+j;
x=i+1,y=j+1;
dest=x*n+y;
if(ifvalid(x,y,n,m))
{
weight=abs(r[i][j]-r[x][y])+abs(g[i][j]-g[x][y])+abs(b[i][j]-b[x][y]);
addEdge(G,index,weight,dest);
}
x=i+1,y=j;
dest=x*n+y;
if(ifvalid(x,y,n,m))
{
weight=abs(r[i][j]-r[x][y])+abs(g[i][j]-g[x][y])+abs(b[i][j]-b[x][y]);
addEdge(G,index,weight,dest);
}
x=i-1,y=j;
dest=x*n+y;
if(ifvalid(x,y,n,m))
{
weight=abs(r[i][j]-r[x][y])+abs(g[i][j]-g[x][y])+abs(b[i][j]-b[x][y]);
addEdge(G,index,weight,dest);
}
x=i,y=j+1;
dest=x*n+y;
if(ifvalid(x,y,n,m))
{
weight=abs(r[i][j]-r[x][y])+abs(g[i][j]-g[x][y])+abs(b[i][j]-b[x][y]);
addEdge(G,index,weight,dest);
}
x=i-1,y=j+1;
dest=x*n+y;
if(ifvalid(x,y,n,m))
{
weight=abs(r[i][j]-r[x][y])+abs(g[i][j]-g[x][y])+abs(b[i][j]-b[x][y]);
addEdge(G,index,weight,dest);
}
x=i+1,y=j-1;
dest=x*n+y;
if(ifvalid(x,y,n,m))
{
weight=abs(r[i][j]-r[x][y])+abs(g[i][j]-g[x][y])+abs(b[i][j]-b[x][y]);
addEdge(G,index,weight,dest);
}
x=i,y=j-1;
dest=x*n+y;
if(ifvalid(x,y,n,m))
{
weight=abs(r[i][j]-r[x][y])+abs(g[i][j]-g[x][y])+abs(b[i][j]-b[x][y]);
addEdge(G,index,weight,dest);
}
x=i-1,y=j-1;
dest=x*n+y;
if(ifvalid(x,y,n,m))
{
weight=abs(r[i][j]-r[x][y])+abs(g[i][j]-g[x][y])+abs(b[i][j]-b[x][y]);
addEdge(G,index,weight,dest);
}
}
}
return G;
}
struct heapNode
{
int index;
int key;
};
struct minHeap
{
int *pos;
int size;
int capacity;
heapNode **arr;
};
minHeap* createMinHeap(int capacity)
{
minHeap* x=(minHeap*)malloc(sizeof(minHeap));
x->size=0;
x->capacity=capacity;
x->pos=(int *)malloc(sizeof(int));
x->arr=(heapNode**) malloc(capacity*sizeof(heapNode*));
return x;
}
void swapMinHeapNode(heapNode** a,heapNode** b)
{
heapNode* t = *a;
*a = *b;
*b = t;
}
void minHeapify(minHeap* x,int index)
{
int smallest,left,right;
smallest=index;
left=2*index+1;
right=2*index+2;
if (left<x->size&& x->arr[left]->key <x->arr[smallest]->key )
smallest=left;
if (right <x->size &&x->arr[right]->key < x->arr[smallest]->key)
smallest = right;
if (smallest!=index)
{
heapNode *smallestNode = x->arr[smallest];
heapNode *idxNode = x->arr[index];
x->pos[smallestNode->index]=index;
x->pos[idxNode->index]=smallest;
swapMinHeapNode(&x->arr[smallest],&x->arr[index]);
minHeapify(x,smallest);
}
}
int isEmpty(minHeap* x)
{
return x->size == 0;
}
heapNode* extractMin(minHeap* x)
{
if (isEmpty(x))
return NULL;
heapNode* root =x->arr[0];
heapNode* lastNode =x->arr[x->size-1];
x->pos[root->index] =x->size-1;
x->pos[lastNode->index] = 0;
x->arr[0]=lastNode;
x->size--;
minHeapify(x,0);
return root;
}
void decreaseKey(minHeap* x,int index,int key)
{
int i =x->pos[index];
x->arr[i]->key = key;
while (i && x->arr[i]->key <x->arr[(i-1)/2]->key)
{
x->pos[x->arr[i]->index] = (i-1)/2;
x->pos[x->arr[(i-1)/2]->index]=i;
swapMinHeapNode(&x->arr[i],&x->arr[(i-1)/2]);
i=(i-1)/2;
}
}
bool isInMinHeap(minHeap *x, int index)
{
if (x->pos[index] <x->size)
return true;
return false;
}
graph* PrimMST(graph* g)
{
graph *mstGraph=(graph*)malloc(sizeof(graph));
mstGraph->NumVertices=g->NumVertices;
int counter=0;
int V=g->NumVertices;
mstGraph->arr=(adjList*)malloc(V*sizeof(adjList));
for(int i=0;i<V;i++)
{
mstGraph->arr[i].head=NULL;
mstGraph->arr[i].s=counter;
counter++;
}
int *parent=(int *)malloc(V*sizeof(int));
int *key=(int *)malloc(V*sizeof(int ));
minHeap *x=createMinHeap(V);
for (int v=1; v < V; ++v)
{
parent[v]=-1;
key[v] = INT_MAX;
heapNode *e=(heapNode *)malloc(sizeof(heapNode));
e->index=v;
e->key=key[v];
x->arr[v]=e;
x->pos[v]=v;
}
heapNode *e=(heapNode *)malloc(sizeof(heapNode));
e->index=0;
key[0]=0;
parent[0]=-1;
e->key=0;
x->arr[0]=e;
x->pos[0]=0;
x->size = V;
while (!isEmpty(x))
{
heapNode* mini=extractMin(x);
int u=mini->index;
node* pCrawl=g->arr[u].head;
while (pCrawl!=NULL)
{
int v=pCrawl->dest;
if (pCrawl->weight<key[v])
{
parent[v]=u;
key[v]=pCrawl->weight;
decreaseKey(x,v,key[v]);
}
pCrawl=pCrawl->next;
}
}
for(int i=1;i<V;i++)
{
if(parent[i]!=-1){
addEdge(mstGraph,i,key[i],parent[i]);
addEdge(mstGraph,parent[i],key[i],i);}
}
return mstGraph;
}
int maxi=-1,vertex1,vertex2;
void dfs(graph *mstGraph,bool *visited,int s)
{
visited[s]=true;
node *temp=mstGraph->arr[s].head;
while(temp!=NULL)
{
int v=temp->dest;
//printf("%d\n",v);
if(!visited[v])
{
if(temp->weight>maxi)
{
maxi=temp->weight;
vertex1=s;
vertex2=v;
}
dfs(mstGraph,visited,v);
}
temp=temp->next;
}
}
void dfsColor(graph *mstGraph,int color,bool *visited,int s,pixel *li)
{
visited[s]=true;
li[s].index=s;
li[s].r=color;
li[s].g=color;
li[s].b=color;
node *temp=mstGraph->arr[s].head;
while(temp!=NULL)
{
int v=temp->dest;
if(!visited[v])
dfsColor(mstGraph,color,visited,v,li);
temp=temp->next;
}
}
void deleteEdge(graph *mstGraph)
{
node *temp=mstGraph->arr[vertex2].head;
node *parent;
if(temp->dest==vertex1)
mstGraph->arr[vertex2].head=temp->next;
else
{
parent=temp;
temp=temp->next;
while(temp!=NULL)
{
if(temp->dest==vertex1)
{
parent->next=temp->next;
break;
}
else
{
parent=temp;
temp=temp->next;
}
}
}
printf("dgz\n");
temp=mstGraph->arr[vertex1].head;
if(temp->dest==vertex2)
mstGraph->arr[vertex1].head=temp->next;
else
{
parent=temp;
temp=temp->next;
while(temp!=NULL)
{
if(temp->dest==vertex2)
{
parent->next=temp->next;
break;
}
else
{
parent=temp;
temp=temp->next;
}
}
}
}
int main()
{
srand((unsigned int)time(NULL));
FILE *ip,*op;
ip=fopen("original.ppm","r");
op=fopen("generated.ppm","w");
char fileType[100];
fscanf(ip,"%s",fileType);
int n,m,i,j;
fscanf(ip,"%d%d",&n,&m);
int **r=(int**)malloc(m*sizeof(int *));
int **g=(int**)malloc(m*sizeof(int *));
int **b=(int**)malloc(m*sizeof(int *));
for(i=0;i<m;i++)
{
r[i]=(int*)malloc(n*sizeof(int));
b[i]=(int*)malloc(n*sizeof(int));
g[i]=(int*)malloc(n*sizeof(int));
}
for(i=0;i<m;i++)
{
for(j=0;j<n;j++)
{
fscanf(ip,"%d%d%d",&r[i][j],&g[i][j],&b[i][j]);
}
}
int color=0,s=3;
graph *G=generateGraph(r,g,b,n,m);
int v=G->NumVertices;
bool *visited=(bool *)malloc(v*sizeof(bool));
pixel *li=(pixel *)malloc(v*sizeof(pixel));
graph *mstGraph=PrimMST(G);
for(i=0;i<s-1;i++)
{
for(j=0;j<v;j++)
visited[j]=false;
dfs(mstGraph,visited,0);
deleteEdge(mstGraph);
}
for(int j=0;j<v;j++)
visited[j]=false;
color=0;
for(i=0;i<v;i++)
{
if(!visited[i])
{
color++;
dfsColor(mstGraph,color,visited,i,li);
}
}
printf("%d\n",color);
fprintf(op,"%s\n",fileType);
fprintf(op,"%d %d\n",n,m);
for(i=0;i<v;i++)
{
fprintf(op,"%d\n",li[i].r);
fprintf(op,"%d\n",li[i].g);
fprintf(op,"%d\n",li[i].b);
}
return 0;
}