数据结构16：图及其遍历

摘要： 图在我们生活中很常用到，树其实就是一中特殊的图。我们本次讲到图在计算机里面的一种存储方式：布尔矩阵（即二维数组）。

图，几乎上综合了我们前面学的所有数据结构，比如二维数组，栈，队列，树的相关操作（遍历）以及链表（这里没用到链表，下一次我们讲图的邻接表存储会用到）。所以如果你对以前的数据结构都掌握得不错的话，写起来就比较轻松，如果对以前的数据结构掌握有所欠缺的话，那就难了。

上代码！

一.代码块
1）结构体定义

这个visited数组是用来记录某位置是否被访问过了，为什么要记录呢，因为图不像二叉树那样，由上往下只能通过双亲到达儿子，并且每一个结点只有一个双亲。
图的话，很有可能可以通过多个结点访问到你。所以是否被访问过了我们是很有必要记录的。这种在各个函数都会用到，并且随时会更改的变量设置为全局变量很舒服

这里我们用的是 n×n的布尔矩阵来表示每两个点之间的连通性，第n行就代表第n个元素分别与其他元素（包括自己）是否连通

#define MAXSIZE 10

int* visited;

typedef struct graph
{
	int** connections;
	int numNodes;
}*graphPtr;

2）队列及其相关操作

进行广度遍历的时候会用到队列，我们把循环队列的相关操作给出来。

typedef struct graphQueue
{
	int *node;
	int front;
	int rear;
}*graphQueuePtr;
 
graphQueuePtr queueInit()
{
	graphQueuePtr resultQueue = (graphQueuePtr)malloc(sizeof(struct graphQueue));
	resultQueue->node = (int*)malloc(MAXSIZE * sizeof(int));
	
	resultQueue->front = 0;
	resultQueue->rear = 0;
	return resultQueue;
}

void enqueue(graphQueuePtr paraQueue,int paraData)
{
	if((paraQueue->rear + 1) % MAXSIZE == (paraQueue->front) % MAXSIZE)
	{
		printf("队列满了，无法入队！n");
		return ;
	}
	
	paraQueue->node[(paraQueue->rear) % MAXSIZE] = paraData;
	paraQueue->rear = (paraQueue->rear + 1) % MAXSIZE;
}

int dequeue(graphQueuePtr paraQueue)
{
	if(paraQueue->front == paraQueue->rear)
	{
		printf("队列为空，无法出队！n");
		return ;
	}
	
	int temp =  paraQueue->node[(paraQueue->front) % MAXSIZE];
	paraQueue->front = (paraQueue->front + 1) % MAXSIZE;
	
	return temp;
}

3）初始化visited数组

这里就是分配空间，并且初始化为0代表都没访问过

void visitedInit(graphPtr paraGraph)
{
	int i;
	visited = (int*)malloc(paraGraph->numNodes * sizeof(int));
	
	for(i = 0;i < paraGraph->numNodes;i ++)
	{
		visited[i] = 0;
	}
}

4）图的初始化

传入一个动态二维数组和元素个数，然后初始化的时候将其拷贝到图结构里面就行了，其实这个初始化就是动态分配空间和拷贝

graphPtr graphInit(int **paraConnections,int paraNumNodes)
{
	int i,j;
	graphPtr resultGraph = (graphPtr)malloc(sizeof(struct graph));
	resultGraph->numNodes = paraNumNodes;
	
	//这里如何给二维数组动态分配空间如果不明白可以参考我以前的二维数组文章 
	resultGraph->connections = (int**)malloc(resultGraph->numNodes * sizeof(int*));
	for(i = 0;i < resultGraph->numNodes;i ++)
	{
		resultGraph->connections[i] = (int*)malloc(resultGraph->numNodes * sizeof(int));
	}
	
	for(i = 0;i < resultGraph->numNodes;i ++)
		for(j = 0;j < resultGraph->numNodes;j ++)
		{
			resultGraph->connections[i][j] = paraConnections[i][j];
		}
		
	return resultGraph;
}

5）深度遍历

在我看到这个深度遍历的代码时候，我就想到了我前两天写的N皇后问题，两者其实有很多相似之处，即每一个遍历的元素都要走完一个for循环，如果满足条件，就先递归到下一个里面去，但是等他们走完了，终究还是要回到这里把剩下的for循环走完。当然只要是递归，就离不开系统的栈。

void depthTranverse(graphPtr paraGraph,int paraNum)
{
	int i;
	visited[paraNum] = 1;
	printf("%d ",paraNum);
	
	for(i = 0;i < paraGraph->numNodes;i ++)
	{
		 
		if(visited[i] == 0 && paraGraph->connections[paraNum][i] == 1)
		{
			depthTranverse(paraGraph,i);
		}
	}
}

6）广度遍历

这个广度遍历和我们二叉树的层次遍历是很相似的，只多了一个检查是否被访问过。用队列来实现是比较简单的

void wideTranverse(graphPtr paraGraph,int paraNum)
{
	int i;
	int temp;
	//建立队列 
	graphQueuePtr tempQueue = queueInit();
	visited[paraNum] = 1;
	//入队的时候就打印出来 
	enqueue(tempQueue,paraNum);
	printf("%d ",paraNum);
	
	//循环结束条件就是队列为空 
	while(tempQueue->front != tempQueue->rear)
	{
		temp = dequeue(tempQueue);
		//出队一个元素就要入队与他连通且没有被访问过的元素
		for(i = 0;i < paraGraph->numNodes;i ++)
		{
			if(visited[i] == 0 && paraGraph->connections[temp][i] == 1)
			{
				visited[i] = 1;
				enqueue(tempQueue,i);
				printf("%d ",i);
			}
		}
	}
	
}

7）测试函数

这里的测试用例是copy的老师的

void testGraphTranverse() 
{
	int i, j;
	int myGraph[5][5] = 
	{ 
		{0, 1, 0, 1, 0},
		{1, 0, 1, 0, 1}, 
		{0, 1, 0, 1, 1}, 
		{1, 0, 1, 0, 0}, 
		{0, 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(5 * sizeof(int));
	}
	 
	for (i = 0; i < 5; i ++) 
	{
		for (j = 0; j < 5; j ++) 
		{
			tempPtr[i][j] = myGraph[i][j];
		}
	}
 
	printf("Data readyrn");
	
	graphPtr tempGraphPtr = graphInit(tempPtr,5);
	printf("num nodes = %d rn", tempGraphPtr -> numNodes);
	printf("Graph initializedrn");

	printf("Depth first visit:rn");
	visitedInit(tempGraphPtr);
	depthTranverse(tempGraphPtr, 4);

	printf("rnWidth first visit:rn");
	visitedInit(tempGraphPtr);
	wideTranverse(tempGraphPtr, 4);
}

三.运行结果

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

四.全部代码`

#include 
#include 

#define MAXSIZE 10


int* visited;  

 
typedef struct graph
{
	int** connections;
	int numNodes;
}*graphPtr;


typedef struct graphQueue
{
	int *node;
	int front;
	int rear;
}*graphQueuePtr;
 
graphQueuePtr queueInit()
{
	graphQueuePtr resultQueue = (graphQueuePtr)malloc(sizeof(struct graphQueue));
	resultQueue->node = (int*)malloc(MAXSIZE * sizeof(int));
	
	resultQueue->front = 0;
	resultQueue->rear = 0;
	return resultQueue;
}

void enqueue(graphQueuePtr paraQueue,int paraData)
{
	if((paraQueue->rear + 1) % MAXSIZE == (paraQueue->front) % MAXSIZE)
	{
		printf("队列满了，无法入队！n");
		return ;
	}
	
	paraQueue->node[(paraQueue->rear) % MAXSIZE] = paraData;
	paraQueue->rear = (paraQueue->rear + 1) % MAXSIZE;
}

int dequeue(graphQueuePtr paraQueue)
{
	if(paraQueue->front == paraQueue->rear)
	{
		printf("队列为空，无法出队！n");
		return ;
	}
	
	int temp =  paraQueue->node[(paraQueue->front) % MAXSIZE];
	paraQueue->front = (paraQueue->front + 1) % MAXSIZE;
	
	return temp;
}
 
//这里就是把记录是否访问的数组初始化一下 
void visitedInit(graphPtr paraGraph)
{
	int i;
	visited = (int*)malloc(paraGraph->numNodes * sizeof(int));
	
	for(i = 0;i < paraGraph->numNodes;i ++)
	{
		visited[i] = 0;
	}
}

 
graphPtr graphInit(int **paraConnections,int paraNumNodes)
{
	int i,j;
	graphPtr resultGraph = (graphPtr)malloc(sizeof(struct graph));
	resultGraph->numNodes = paraNumNodes;
	
	//这里如何给二维数组动态分配空间如果不明白可以参考我以前的二维数组文章 
	resultGraph->connections = (int**)malloc(resultGraph->numNodes * sizeof(int*));
	for(i = 0;i < resultGraph->numNodes;i ++)
	{
		resultGraph->connections[i] = (int*)malloc(resultGraph->numNodes * sizeof(int));
	}
	
	for(i = 0;i < resultGraph->numNodes;i ++)
		for(j = 0;j < resultGraph->numNodes;j ++)
		{
			resultGraph->connections[i][j] = paraConnections[i][j];
		}
		
	return resultGraph;
}


void depthTranverse(graphPtr paraGraph,int paraNum)
{
	int i;
	visited[paraNum] = 1;
	printf("%d ",paraNum);
	
	for(i = 0;i < paraGraph->numNodes;i ++)
	{
		 
		if(visited[i] == 0 && paraGraph->connections[paraNum][i] == 1)
		{
			depthTranverse(paraGraph,i);
		}
	}
}


void wideTranverse(graphPtr paraGraph,int paraNum)
{
	int i;
	int temp;
	//建立队列 
	graphQueuePtr tempQueue = queueInit();
	visited[paraNum] = 1;
	//入队的时候就打印出来 
	enqueue(tempQueue,paraNum);
	printf("%d ",paraNum);
	
	//循环结束条件就是队列为空 
	while(tempQueue->front != tempQueue->rear)
	{
		temp = dequeue(tempQueue);
		//出队一个元素就要入队与他连通且没有被访问过的元素
		for(i = 0;i < paraGraph->numNodes;i ++)
		{
			if(visited[i] == 0 && paraGraph->connections[temp][i] == 1)
			{
				visited[i] = 1;
				enqueue(tempQueue,i);
				printf("%d ",i);
			}
		}
	}
	
}

//这里的测试用例是copy的老师的 
void testGraphTranverse() 
{
	int i, j;
	int myGraph[5][5] = 
	{ 
		{0, 1, 0, 1, 0},
		{1, 0, 1, 0, 1}, 
		{0, 1, 0, 1, 1}, 
		{1, 0, 1, 0, 0}, 
		{0, 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(5 * sizeof(int));
	}
	 
	for (i = 0; i < 5; i ++) 
	{
		for (j = 0; j < 5; j ++) 
		{
			tempPtr[i][j] = myGraph[i][j];
		}
	}
 
	printf("Data readyrn");
	
	graphPtr tempGraphPtr = graphInit(tempPtr,5);
	printf("num nodes = %d rn", tempGraphPtr -> numNodes);
	printf("Graph initializedrn");

	printf("Depth first visit:rn");
	visitedInit(tempGraphPtr);
	depthTranverse(tempGraphPtr, 4);

	printf("rnWidth first visit:rn");
	visitedInit(tempGraphPtr);
	wideTranverse(tempGraphPtr, 4);
}

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

其实总的来说，图的操作就要运用到前面很多数据结构的操作，还是相对比较简单的，可以一遍过。不像我写哈夫曼树一直调试…