数据结构----图的遍历

图的遍历

图的遍历是指，从给定图中任意指定的顶点（称为初始点）出发，按照某种搜索方法沿着图的边访问图中的所有顶点，使每个顶点仅被访问一次，这个过程称为图的遍历。

完整代码

#include
#include

#define QUEUE_SIZE 10

int* visitedPtr;


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


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


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


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


int dequeue(QueuePtr paraQueuePtr){
	if(isQueueEmpty(paraQueuePtr)){
		printf("Error, empty queue.rn");
		return NULL;
	}//of if
	paraQueuePtr->front=(paraQueuePtr->front+1)%QUEUE_SIZE;
	
	//printf("dequeue %d ends.rn",paraQueuePtr->nodes[paraQueuePtr->front])
	return paraQueuePtr->nodes[paraQueuePtr->front];
}//of dequeue


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

//void deepFirst(GraphPtr paraGraphPtr,int paraNode)
GraphPtr initGraph(int paraSize, int** paraData){
	int i,j;
	GraphPtr resultPtr = (GraphPtr)malloc(sizeof(Graph));
	resultPtr->numNodes = paraSize;
	//resultPtr->connections = (int**)mallic(paraSize * paraSize * sizeof(int));
	resultPtr->connections = (int**)malloc(paraSize * sizeof(int*));
	for(i=0;iconnections[i]=(int*)malloc(paraSize * sizeof(int));
		for(j=0;jconnections[i][j]=paraData[i][j];
		}//of for j
	}//of for i
	return resultPtr;
}//of initGraph


void initTranverse(GraphPtr paraGraphPtr){
	int i;
	// Initialize data
	visitedPtr=(int*)malloc(paraGraphPtr->numNodes * sizeof(int));
	
	for(i=0;inumNodes;i++){
		visitedPtr[i]=0;
	}//of for i
}//of initTranverse


void depthFirstTranverse(Graph paraGraphPtr, int paraNode){
	int i;
	
	visitedPtr[paraNode] = 1;
	printf("%dt",paraNode);
	
	for(i=0;i numNodes;i++){
		if(!visitedPtr[i]){
			if(paraGraphPtr -> connections[paraNode][i]){
				depthFirstTranverse(paraGraphPtr,i);
			}//of if
		}//of if
	}//of for i
}//of depthFirstTranverse


void widthFirstTranverse(GraphPtr paraGraphPtr, int paraStart){
	//Use a queue to manage the pointers
	int i,j,tempNode;
	i=0;
	QueuePtr tempQueuePtr = initQueue();
	printf("%dt",paraStart);
	visitedPtr[paraStart]=1;
	enqueue(tempQueuePtr, paraStart);
	while(!isQueueEmpty(tempQueuePtr)){
		tempNode=dequeue(tempQueuePtr);
		visitedPtr[tempNode] = 1;
		
		//For output.
		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);	
		}//of for j
	}//of while 
}//of widthFirstTranverse

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++){
		for(j=0;j<5;j++){
			//printf("i=%d, j=%d, ",i,j);
			//printf("%drn",tempPtr[i][j]);
			tempPtr[i][j]=myGraph[i][j];
			//printf("i=%d,j=%d, %drn",i,j,tempPtr[i][j]);			
		}//of for j
	}//of for i
	
	printf("Data readyrn");
	
	GraphPtr tempGraphPtr=initGraph(5, tempPtr);
	printf("num nodes = %drn",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);
}//of testGraphTranverse

int main(){
	testGraphTranverse();
	return 1;
}//of main

遍历结果：v1，v2，v4，v8，v5，v3，v6，v7 

运行结果