数据结构之图的邻接矩阵存储

• 一、图的定义
• 二、具体函数
• • 1.结构体的定义
  • 2.初始化
  • 3.判断队列是否为空
  • 4.入队列以及出队列的实现
  • 5.深度优先遍历
  • 6.广度优先遍历
• 三、具体代码实现
• 四、测试样例输出

图是由顶点的又穷非空集合和顶点之间边的集合组成的们通常表示为G(V,E)，其中，G表示一个图，V是图G中顶点的集合，E是图G中边的集合。
图的临界矩阵存储：用两个数组来表示图。一个一维数组存储图中顶点信息，一个二维数组(称为邻接矩阵)存储图中的边或弧的信息。

typedef struct GraphNodeQueue
{
	int* nodes;
	int front;
	int rear;
}GraphNodeQueue,*QueuePtr;


typedef struct Graph
{
	int** connections;
	int numNodes;
}*GraphPtr;

QueuePtr initQueue()
{
	QueuePtr resultQueuePtr=(QueuePtr)malloc(sizeof(struct GraphNodeQueue));
	resultQueuePtr->nodes=(int*)malloc(sizeof(int)*QUEUE_SIZE);
	resultQueuePtr->front=0;
	resultQueuePtr->rear=1;
	return resultQueuePtr;
}


void initTranverse(GraphPtr paraGraphPtr)
{
	int i;
	visitedPtr=(int*)malloc(sizeof(int)*paraGraphPtr->numNodes);

	for(i=0;inumNodes;i++)
	{
		visitedPtr[i]=0;
	}
}


GraphPtr initGraph(int paraSize,int** paraData)
{
	int i,j;
	GraphPtr resultPtr=(GraphPtr)malloc(sizeof(Graph));
	resultPtr->numNodes=paraSize;
	resultPtr->connections=(int**)malloc(sizeof(int*)*paraSize);
	for(i=0;i
		resultPtr->connections[i]=(int*)malloc(sizeof(int)*paraSize);
		for(j=0;j
			resultPtr->connections[i][j]=paraData[i][j];
		}
	}
	return resultPtr;
}

bool isQueueEmpty(QueuePtr paraQueuePtr)
{
	if((paraQueuePtr->front+1)%QUEUE_SIZE==paraQueuePtr->rear)
	{
		return true;
	}

	return false;
}

void enqueue(QueuePtr paraQueuePtr,int paraNode)
{
	if((paraQueuePtr->rear+1)%QUEUE_SIZE==paraQueuePtr->front%QUEUE_SIZE)
	{
		printf("ERROR,trying to enqueue %d.queue full.rn",paraNode);
		return ;
	}
	paraQueuePtr->nodes[paraQueuePtr->rear]=paraNode;
	paraQueuePtr->rear=(paraQueuePtr->rear+1)%QUEUE_SIZE;
}

int dequeue(QueuePtr paraQueuePtr)
{
	if(isQueueEmpty(paraQueuePtr))
	{
		printf("Error,empty queuern");
		return NULL;
	}
	paraQueuePtr->front=(paraQueuePtr->front+1)%QUEUE_SIZE;

	return paraQueuePtr->nodes[paraQueuePtr->front];
}

void depthFirstTranverse(GraphPtr paraGraphPtr,int paraNode)
{
	int i;

	visitedPtr[paraNode]=1;
	printf("%dt",paraNode);

	for(i=0;inumNodes;i++)
	{
		if(!visitedPtr[i])
		{
			if(paraGraphPtr->connections[paraNode][i])
			{
				depthFirstTranverse(paraGraphPtr,i);
			}
		}
	}
}

void widthFirstTranverse(GraphPtr paraGraphPtr,int paraStart)
{
	int i=0,j,tempNode;
	QueuePtr tempQueuePtr=initQueue();
	printf("%dt",paraStart);
	visitedPtr[paraStart]=1;
	enqueue(tempQueuePtr,paraStart);
	while(!isQueueEmpty(tempQueuePtr))
	{
		tempNode=dequeue(tempQueuePtr);
		visitedPtr[tempNode]=1;

		i++;
		for(j=0;jnumNodes;j++)
		{
			if(visitedPtr[j])
			continue;

			if(paraGraphPtr->connections[tempNode][j]==0)
			continue;

			printf("%dt",j);
			visitedPtr[j]=1;
			enqueue(tempQueuePtr,j);
		}
	}
}

#include
#include

#define QUEUE_SIZE 10

int* visitedPtr;

typedef struct GraphNodeQueue
{
	int* nodes;
	int front;
	int rear;
}GraphNodeQueue,*QueuePtr;

typedef struct Graph
{
	int** connections;
	int numNodes;
}*GraphPtr;

QueuePtr initQueue()
{
	QueuePtr resultQueuePtr=(QueuePtr)malloc(sizeof(struct GraphNodeQueue));
	resultQueuePtr->nodes=(int*)malloc(sizeof(int)*QUEUE_SIZE);
	resultQueuePtr->front=0;
	resultQueuePtr->rear=1;
	return resultQueuePtr;
}

bool isQueueEmpty(QueuePtr paraQueuePtr)
{
	if((paraQueuePtr->front+1)%QUEUE_SIZE==paraQueuePtr->rear)
	{
		return true;
	}

	return false;
}

void enqueue(QueuePtr paraQueuePtr,int paraNode)
{
	if((paraQueuePtr->rear+1)%QUEUE_SIZE==paraQueuePtr->front%QUEUE_SIZE)
	{
		printf("ERROR,trying to enqueue %d.queue full.rn",paraNode);
		return ;
	}
	paraQueuePtr->nodes[paraQueuePtr->rear]=paraNode;
	paraQueuePtr->rear=(paraQueuePtr->rear+1)%QUEUE_SIZE;
}

int dequeue(QueuePtr paraQueuePtr)
{
	if(isQueueEmpty(paraQueuePtr))
	{
		printf("Error,empty queuern");
		return NULL;
	}
	paraQueuePtr->front=(paraQueuePtr->front+1)%QUEUE_SIZE;

	return paraQueuePtr->nodes[paraQueuePtr->front];
}

GraphPtr initGraph(int paraSize,int** paraData)
{
	int i,j;
	GraphPtr resultPtr=(GraphPtr)malloc(sizeof(Graph));
	resultPtr->numNodes=paraSize;
	resultPtr->connections=(int**)malloc(sizeof(int*)*paraSize);
	for(i=0;i
		resultPtr->connections[i]=(int*)malloc(sizeof(int)*paraSize);
		for(j=0;j
			resultPtr->connections[i][j]=paraData[i][j];
		}
	}
	return resultPtr;
}

void initTranverse(GraphPtr paraGraphPtr)
{
	int i;
	visitedPtr=(int*)malloc(sizeof(int)*paraGraphPtr->numNodes);

	for(i=0;inumNodes;i++)
	{
		visitedPtr[i]=0;
	}
}

void depthFirstTranverse(GraphPtr paraGraphPtr,int paraNode)
{
	int i;

	visitedPtr[paraNode]=1;
	printf("%dt",paraNode);

	for(i=0;inumNodes;i++)
	{
		if(!visitedPtr[i])
		{
			if(paraGraphPtr->connections[paraNode][i])
			{
				depthFirstTranverse(paraGraphPtr,i);
			}
		}
	}
}

void widthFirstTranverse(GraphPtr paraGraphPtr,int paraStart)
{
	int i=0,j,tempNode;
	QueuePtr tempQueuePtr=initQueue();
	printf("%dt",paraStart);
	visitedPtr[paraStart]=1;
	enqueue(tempQueuePtr,paraStart);
	while(!isQueueEmpty(tempQueuePtr))
	{
		tempNode=dequeue(tempQueuePtr);
		visitedPtr[tempNode]=1;

		i++;
		for(j=0;jnumNodes;j++)
		{
			if(visitedPtr[j])
			continue;

			if(paraGraphPtr->connections[tempNode][j]==0)
			continue;

			printf("%dt",j);
			visitedPtr[j]=1;
			enqueue(tempQueuePtr,j);
		}
	}
}

void testGraphTranverse()
{
	int i,j;
	int myGraph[5][5]={
		{0,1,0,1,1},
		{1,0,1,0,1},
		{0,1,0,1,1},
		{1,0,1,0,0},
		{1,1,1,0,0}
	};
	int** tempPtr;
	printf("Preparing datarn");

	tempPtr=(int**)malloc(5*sizeof(int*));
	for(i=0;i<5;i++)
	{
		tempPtr[i]=(int*)malloc(sizeof(int)*5);
	}

	for(i=0;i<5;i++)
	{
		for(j=0;j<5;j++)
		{
			tempPtr[i][j]=myGraph[i][j];
		}
	}

	printf("Data readyrn");

	GraphPtr tempGraphPtr=initGraph(5,tempPtr);
	printf("num nodes =%d rn",tempGraphPtr->numNodes);
	printf("Graph initializedrn");

	printf("Depth first visit:rn");
	initTranverse(tempGraphPtr);
	depthFirstTranverse(tempGraphPtr,4);

	printf("rnWidth first visit:rn");
	initTranverse(tempGraphPtr);
	widthFirstTranverse(tempGraphPtr,4);
}

int main()
{
	testGraphTranverse();
	return 0;
}

Preparing data
Data ready
num nodes =5
Graph initialized
Depth first visit:
4 0 1 2 3
Width first visit:
4 0 1 2 3