adjmgraph.h

《数据结构-使用C语言》第三版

#include"SeqList.h"

typedef struct
{
	SeqList Vertices;
	int edge[MaxVertices][MaxVertices];
	int numOfEdges;
}AdjMGraph;

typedef struct
{
	int row;
	int col;
	int weight;
}RowColWeight;

void Initiate(AdjMGraph *G, int n)
{
	int i, j;
	for(i=0;i<n;i++)
	for(j=0;j<n;j++)
	{
		if(i==j)G->edge[i][j]=0;
		else G->edge[i][j]=MaxWeight;
	}
	G->numOfEdges=0;
	ListInitiate(&G->Vertices);
}

void InsertVertex(AdjMGraph *G, DataType vertex)
{
	ListInsert(&G->Vertices, G->Vertices.size, vertex);
}

void InsertEdge(AdjMGraph *G, int v1, int v2, int weight)
{
	if(v1<0 || v1>G->Vertices.size || v2<0 ||v2>G->Vertices.size)
	{
		printf("error!\n");
		exit(1);
	}
	
	G->edge[v1][v2]=weight;
	
	G->numOfEdges++;
}

void DeleteEdge(AdjMGraph *G, int v1, int v2)
{
	if(v1<0 || v1>G->Vertices.size || v2<0 || v2>G->Vertices.size || v1==v2)
	{
		printf("error!\n");
		exit(1);
	}
	if(G->edge[v1][v2]==MaxWeight || v1==v2)
	{
		printf("error!\n");
		exit(0);
	}
	G->edge[v1][v2]=MaxWeight;
	G->numOfEdges--;
}

void DeleteVertex(AdjMGraph *G, int V)
{
	int n=ListLength(G->Vertices), i, j;
	DataType x;
	
	for(i=0;i<n;i++)
	for(j=0;j<n;j++)
	if((i==V||j==V) && G->edge[i][j]>0 && G->edge[i][j]<MaxWeight)
	G->numOfEdges--;
	
	for(i=V;i<n;i++)
	for(j=0;j<n;j++)
	G->edge[i][j]=G->edge[i+1][j];
	
	for(i=0;i<n;i++)
	for(j=V;j<n;j++)
	G->edge[i][j]=G->edge[i][j+1];
	
	ListDelete(&G->Vertices, V, &x);
}

int GetFirstVex(AdjMGraph G, int v)
{
	int col;
	if(v<0 || v>G.Vertices.size)
	{
		printf("error!\n");
		exit(1);
	}
	
	for(col=0; col<G.Vertices.size; col++)
	if(G.edge[v][col]>0 && G.edge[v][col]<MaxWeight)return col;
	return -1;
}

int GetNextVex(AdjMGraph G, int v1, int v2)
{
	int col;
	if(v1<0 || v1>G.Vertices.size || v2<0 ||v2>G.Vertices.size)
	{
		printf("error!\n");
		exit(1);
	}
	for(col=v2+1; col<G.Vertices.size; col++)
	if(G.edge[v1][col]>0 && G.edge[v1][col]<MaxWeight)return col;
	return -1;
}

void CreatGraph(AdjMGraph  *G, DataType V[], int n, RowColWeight E[], int e)
{
	int i, k;
	Initiate(G,n);
	
	for(i=0;i<n;i++)
	InsertVertex(G,V[i]);
	
	for(k=0;k<e;k++)
	InsertEdge(G, E[k].row, E[k].col, E[k].weight);
}