数据结构16-图的遍历

图的遍历方法有深度优先搜索法和广度优先搜索法两种算法。

深度优先搜索法的基本思想是：从图G的某个顶点v0出发，访问v0，然后选择一个与v0相邻且没被访问过的顶点vi访问，再从vi出发选择一个与vi相邻且未被访问的顶点vj进行访问，依次继续。如果当前被访问过的顶点的所有邻接顶点都已被访问，则退回到已被访问的顶点序列中最后一个拥有未被访问的相邻顶点的顶点w，从w出发按同样的方法向前遍历，直到图中所有顶点都被访问。

void depthFirstTranverse(GraphPtr pGraphPtr,int pNode){
	int i;
	
	visitedPtr[pNode] = 1;
	printf("%d ",pNode);
	
	for(i = 0;i < pGraphPtr->numNodes;i++){
		if(!visitedPtr[i]){
			if(pGraphPtr->connections[pNode][i]){
				depthFirstTranverse(pGraphPtr,i);
			}
		}
	}
}

图的广度优先搜索是树的按层次遍历的推广，它的基本思想是：首先访问初始点vi，并将其标记为已访问过，接着访问vi的所有未被访问过的邻接点vi1,vi2,…, vi t，并均标记已访问过，然后再按照vi1,vi2,…, vi t的次序，访问每一个顶点的所有未被访问过的邻接点，并均标记为已访问过，依次类推，直到图中所有和初始点vi有路径相通的顶点都被访问过为止。图的广度优先法需要借助队列。

void widthFirstTranverse(GraphPtr pGraphPtr,int pStart){
	int i = 0,j,temp;
	QueuePtr tempQueuePtr = iniQueuePtr();
	printf("%d ",pStart);
	visitedPtr[pStart] = 1;
	enqueue(tempQueuePtr,pStart);
	while(!isQueueEmpty(tempQueuePtr)){
		temp = dequeue(tempQueuePtr);
		visitedPtr[temp] = 1;
		
		i++;
		
		for(j = 0;j < pGraphPtr->numNodes;j++){
			if(visitedPtr[j]){
				continue;
			}
			if(pGraphPtr->connections[temp][j] == 0){
				continue;
			}
			printf("%d ",j);
			visitedPtr[j] = 1;
			enqueue(tempQueuePtr,j);
		}
	}
}

#include 
#include 

#define QUEUESIZE 10
int* visitedPtr;

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

QueuePtr iniQueuePtr(){
	QueuePtr result = (QueuePtr)malloc(sizeof(GraphNodeQueue));
	result->nodes = (int*)malloc(QUEUESIZE * sizeof(int));
	result->front = 0;
	result->rear = 1;
	return result;
}

bool isQueueEmpty(QueuePtr pQueuePtr){
	if((pQueuePtr->front + 1) % QUEUESIZE == pQueuePtr->rear){
		return true;
	}
	
	return false;
}

void enqueue(QueuePtr pQueuePtr,int pNode){
	if((pQueuePtr->rear + 1) % QUEUESIZE == pQueuePtr->front){
		printf("Error,trying to enqueue %d .queue full.n",pNode);
		return;
	}
	pQueuePtr->nodes[pQueuePtr->rear] = pNode;
	pQueuePtr->rear = (pQueuePtr->rear + 1) % QUEUESIZE;
}

int dequeue(QueuePtr pQueuePtr){
	if(isQueueEmpty(pQueuePtr)){
		printf("Error,empty queuen");
		return NULL;
	}
	
	pQueuePtr->front = (pQueuePtr->front + 1) % QUEUESIZE;
	
	return pQueuePtr->nodes[pQueuePtr->front];
}

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

GraphPtr iniGraph(int pSize,int** pData){
	int i,j;
	GraphPtr result = (GraphPtr)malloc(sizeof(Graph));
	result->numNodes = pSize;
	result->connections = (int**)malloc(pSize * sizeof(int*));
	for(i = 0;i < pSize;i++){
		result->connections[i] = (int*)malloc(pSize * sizeof(int));
		for(j = 0;j < pSize;j++){
			result->connections[i][j] = pData[i][j];
		}
	}
	return result;
}

void iniTranverse(GraphPtr pGraphPtr){
	int i;
	visitedPtr = (int*)malloc(pGraphPtr->numNodes * sizeof(int));
	
	for(i = 0;i < pGraphPtr->numNodes;i++){
		visitedPtr[i] = 0;
	}
}

void depthFirstTranverse(GraphPtr pGraphPtr,int pNode){
	int i;
	
	visitedPtr[pNode] = 1;
	printf("%d ",pNode);
	
	for(i = 0;i < pGraphPtr->numNodes;i++){
		if(!visitedPtr[i]){
			if(pGraphPtr->connections[pNode][i]){
				depthFirstTranverse(pGraphPtr,i);
			}
		}
	}
}

void widthFirstTranverse(GraphPtr pGraphPtr,int pStart){
	int i = 0,j,temp;
	QueuePtr tempQueuePtr = iniQueuePtr();
	printf("%d ",pStart);
	visitedPtr[pStart] = 1;
	enqueue(tempQueuePtr,pStart);
	while(!isQueueEmpty(tempQueuePtr)){
		temp = dequeue(tempQueuePtr);
		visitedPtr[temp] = 1;
		
		i++;
		
		for(j = 0;j < pGraphPtr->numNodes;j++){
			if(visitedPtr[j]){
				continue;
			}
			if(pGraphPtr->connections[temp][j] == 0){
				continue;
			}
			printf("%d ",j);
			visitedPtr[j] = 1;
			enqueue(tempQueuePtr,j);
		}
	}
}

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 datan");
	
	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 readyn");
	
	GraphPtr tempGraphPtr = iniGraph(5,tempPtr);
	printf("num nodes = %d n",tempGraphPtr->numNodes);
	printf("Graph initlizedn");
	
	printf("Depth first visit:n");
	iniTranverse(tempGraphPtr);
	depthFirstTranverse(tempGraphPtr,4);
	
	printf("nWidth first visit:n");
	iniTranverse(tempGraphPtr);
	widthFirstTranverse(tempGraphPtr,4);
}

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

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