目录

图

一.邻接矩阵

1.邻接矩阵的定义

2.初始化邻接矩阵

3.深度遍历

4.广度遍历

5.总源代码

6.测试结果

二.邻接表

1.创建邻接表

2.初始化邻接表

3.广度遍历

4.源代码

5.测试代码

总结

图

因为图的结构比较复杂，我将会用邻接矩阵和邻接表两种数据结构来表示图。

一.邻接矩阵

存储方式是用两个数组来表示图。一个一维数组来储存图中顶点信息，一个二维数组来储存图中的边信息。

1.邻接矩阵的定义

typedef struct Graph{
	int **connection;//存储边
	int numnodes;//顶点总数
}*GraphPtr,LGraph;

int*  visitPtr;//用来存储顶点。

2.初始化邻接矩阵

GraphPtr initGraph(int paraSize,int **data){
	GraphPtr resultPtr=(GraphPtr)malloc(sizeof(LGraph));
	resultPtr->numnodes=paraSize;
	resultPtr->connection=(int **)malloc(sizeof(int*)*paraSize);
	for(int i=0;iconnection[i]=(int*)malloc(sizeof(int)*paraSize);
		for(int j=0;jconnection[i][j]=data[i][j];
		}
	} 
	return resultPtr;	
}
//初始化存储顶点的数组
void initTranverse(GraphPtr paraGraph){
	visitPtr=(int*)calloc(paraGraph->numnodes,sizeof(int));
}

3.深度遍历

void depthTranverce(GraphPtr paraGraph,int paraNode){
	visitPtr[paraNode]=1;//从paraNode开始遍历 
	printf("%dt",paraNode);
	
	int i;
	for(i=0;inumnodes;i++){
		if(!visitPtr[i]&¶Graph->connection[paraNode][i]){
			depthTranverce(paraGraph,i); 
		}
	

4.广度遍历

void widthTranverce(GraphPtr paraGraph,int start){
	int j,tempNode;
	
	QueuePtr tempQueue=initQueue();
	printf("%dt",start);
	visitPtr[start]=1; 
	enqueue(tempQueue,start);
	while(!isEmptyQueue(tempQueue)){
		tempNode=dequeue(tempQueue); 
		
		for(j=0;jnumnodes;j++){
			if(!visitPtr[j]&¶Graph->connection[tempNode][j]!=0){
				printf("%dt",j);
				visitPtr[j]=1;
				enqueue(tempQueue,j); 
			}
		}
	}
}	

5.总源代码

#include 
#include 

#define QUEUE_SIZE 10

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

QueuePtr initQueue(){
	QueuePtr resultPtr=(QueuePtr)malloc(sizeof(LQueue));
	resultPtr->nodes=(int*)calloc(QUEUE_SIZE,sizeof(int));
	resultPtr->front=0;
	resultPtr->rear=1; 
	return resultPtr;
}

int isEmptyQueue(QueuePtr paraQueue){
	if((paraQueue->front+1)%QUEUE_SIZE==paraQueue->rear){
		return true;
	}
	return false;
} 

void enqueue(QueuePtr paraQueue,int Data){
	if((paraQueue->rear+1) %QUEUE_SIZE==paraQueue->front%QUEUE_SIZE){
		printf("queue is full");
		return;
	}
	paraQueue->nodes[paraQueue->rear]=Data;
	paraQueue->rear=(paraQueue->rear+1)%QUEUE_SIZE;
}

int dequeue(QueuePtr paraQueue){
	if(isEmptyQueue(paraQueue)){
		printf("queue is empty");
		return 0;
	}
	
	paraQueue->front=(paraQueue->front+1)%QUEUE_SIZE;
	return paraQueue->nodes[paraQueue->front];
}

typedef struct Graph{
	int **connection;
	int numnodes;
}*GraphPtr,LGraph;

int*  visitPtr;

GraphPtr initGraph(int paraSize,int **data){
	GraphPtr resultPtr=(GraphPtr)malloc(sizeof(LGraph));
	resultPtr->numnodes=paraSize;
	resultPtr->connection=(int **)malloc(sizeof(int*)*paraSize);
	for(int i=0;iconnection[i]=(int*)malloc(sizeof(int)*paraSize);
		for(int j=0;jconnection[i][j]=data[i][j];
		}
	} 
	return resultPtr;	
}

void initTranverse(GraphPtr paraGraph){
	visitPtr=(int*)calloc(paraGraph->numnodes,sizeof(int));
}

void depthTranverce(GraphPtr paraGraph,int paraNode){
	visitPtr[paraNode]=1;//从paraNode开始遍历 
	printf("%dt",paraNode);
	
	int i;
	for(i=0;inumnodes;i++){
		if(!visitPtr[i]&¶Graph->connection[paraNode][i]){
			depthTranverce(paraGraph,i); 
		}
	} 
}

void widthTranverce(GraphPtr paraGraph,int start){
	int j,tempNode;
	
	QueuePtr tempQueue=initQueue();
	printf("%dt",start);
	visitPtr[start]=1; 
	enqueue(tempQueue,start);
	while(!isEmptyQueue(tempQueue)){
		tempNode=dequeue(tempQueue); 
		
		for(j=0;jnumnodes;j++){
			if(!visitPtr[j]&¶Graph->connection[tempNode][j]!=0){
				printf("%dt",j);
				visitPtr[j]=1;
				enqueue(tempQueue,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 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 = initGraph(5,tempPtr);
	printf("num nodes = %d rn", tempGraphPtr->numnodes);
	printf("Graph initializedrn");

	printf("Depth first visit:rn");
	initTranverse(tempGraphPtr);
	depthTranverce(tempGraphPtr, 3);

	printf("rnWidth first visit:rn");
	initTranverse(tempGraphPtr);
	widthTranverce(tempGraphPtr, 3);
}

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

6.测试结果

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

二.邻接表

邻接表有一个数组和指针组成，数组存储顶点，而指针指向邻接顶点。

1.创建邻接表

typedef struct Node{
	int column;
	struct Node *next;
}LNode,*GraphNode;

typedef struct AGraph{
	int sumNode;
	GraphNode Header;
}AdjacencyList, *AdjacencyListPtr;

int*  visitPtr;

2.初始化邻接表

AdjacencyListPtr initAdjancencyList(GraphPtr paraGraph){
	AdjacencyListPtr result=(AdjacencyListPtr)malloc(sizeof(AdjacencyList));
	result->Header=(GraphNode)malloc(sizeof(LNode)*paraGraph->numnodes);
	result->sumNode=paraGraph->numnodes;
	
	GraphNode p,q;
	//初始化 
	for(int i=0;inumnodes;i++){
		p=&result->Header[i];
		p->column=-1;
		p->next=NULL;
		
		//
		for(int j=0;jnumnodes;j++){
			if(paraGraph->connection[i][j]!=0){
				q=(GraphNode)malloc(sizeof(LNode));
				q->column=j;
				q->next=NULL;
				
				p->next=q;
				p=q;
			} 
		}
	}
	return result;
}

3.广度遍历

void widthFirstTranverse(AdjacencyListPtr paraList, int start){
	printf("width first rn");
	int i,tempNode;
	GraphNode p;
	
	visitPtr=(int*)calloc(paraList->sumNode,sizeof(int));
	//创建队列和初始化 
	QueuePtr queue=initQueue();
	printf("%d ",start);
	visitPtr[start]=1;
	enqueue(queue,start); 
	
	while(!isEmptyQueue(queue)){
		tempNode=dequeue(queue);
		for(p=&(paraList->Header[tempNode]);p!=NULL;p=p->next){
			i=p->column;
			if(visitPtr[i]){
				continue;
			}
			printf("%d ",i);
			visitPtr[i]=1;
			enqueue(queue, i);
		}
	}
	printf("rn");
}

4.源代码

#include 
#include 

#define QUEUE_SIZE 10

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

QueuePtr initQueue(){
	QueuePtr resultPtr=(QueuePtr)malloc(sizeof(LQueue));
	resultPtr->nodes=(int*)calloc(QUEUE_SIZE,sizeof(int));
	resultPtr->front=0;
	resultPtr->rear=1; 
	return resultPtr;
}

int isEmptyQueue(QueuePtr paraQueue){
	if((paraQueue->front+1)%QUEUE_SIZE==paraQueue->rear){
		return true;
	}
	return false;
} 

void enqueue(QueuePtr paraQueue,int Data){
	if((paraQueue->rear+1) %QUEUE_SIZE==paraQueue->front%QUEUE_SIZE){
		printf("queue is full");
		return;
	}
	paraQueue->nodes[paraQueue->rear]=Data;
	paraQueue->rear=(paraQueue->rear+1)%QUEUE_SIZE;
}

int dequeue(QueuePtr paraQueue){
	if(isEmptyQueue(paraQueue)){
		printf("queue is empty");
		return 0;
	}
	
	paraQueue->front=(paraQueue->front+1)%QUEUE_SIZE;
	return paraQueue->nodes[paraQueue->front];
}

typedef struct Graph{
	int **connection;
	int numnodes;
}*GraphPtr,LGraph;

int*  visitPtr;

GraphPtr initGraph(int paraSize,int **data){
	GraphPtr resultPtr=(GraphPtr)malloc(sizeof(LGraph));
	resultPtr->numnodes=paraSize;
	resultPtr->connection=(int **)malloc(sizeof(int*)*paraSize);
	for(int i=0;iconnection[i]=(int*)malloc(sizeof(int)*paraSize);
		for(int j=0;jconnection[i][j]=data[i][j];
		}
	} 
	return resultPtr;	
}

typedef struct Node{
	int column;
	struct Node *next;
}LNode,*GraphNode;

typedef struct AGraph{
	int sumNode;
	GraphNode Header;
}AdjacencyList, *AdjacencyListPtr;

AdjacencyListPtr initAdjancencyList(GraphPtr paraGraph){
	AdjacencyListPtr result=(AdjacencyListPtr)malloc(sizeof(AdjacencyList));
	result->Header=(GraphNode)malloc(sizeof(LNode)*paraGraph->numnodes);
	result->sumNode=paraGraph->numnodes;
	
	GraphNode p,q;
	//初始化 
	for(int i=0;inumnodes;i++){
		p=&result->Header[i];
		p->column=-1;
		p->next=NULL;
		
		//
		for(int j=0;jnumnodes;j++){
			if(paraGraph->connection[i][j]!=0){
				q=(GraphNode)malloc(sizeof(LNode));
				q->column=j;
				q->next=NULL;
				
				p->next=q;
				p=q;
			} 
		}
	}
	return result;
}

void printList(AdjacencyListPtr paraList){
	int i=0;
	GraphNode p;
	int tempsum=paraList->sumNode;
	
	for(i=0;iHeader[i].next;
		while(p!=NULL){
			printf("%d ",p->column);
			p=p->next;
		}
		printf("rn");
	}
}

void widthFirstTranverse(AdjacencyListPtr paraList, int start){
	printf("width first rn");
	int i,tempNode;
	GraphNode p;
	
	visitPtr=(int*)calloc(paraList->sumNode,sizeof(int));
	//创建队列和初始化 
	QueuePtr queue=initQueue();
	printf("%d ",start);
	visitPtr[start]=1;
	enqueue(queue,start); 
	
	while(!isEmptyQueue(queue)){
		tempNode=dequeue(queue);
		for(p=&(paraList->Header[tempNode]);p!=NULL;p=p->next){
			i=p->column;
			if(visitPtr[i]){
				continue;
			}
			printf("%d ",i);
			visitPtr[i]=1;
			enqueue(queue, i);
		}
	}
	printf("rn");
}

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));
	}//Of for i
	 
	for (i = 0; i < 5; i ++) {
		for (j = 0; j < 5; j ++) {
			tempPtr[i][j] = myGraph[i][j];
		}
	}//Of for i
 
	printf("Data readyrn");
	
	GraphPtr tempGraphPtr = initGraph(5, tempPtr);
	AdjacencyListPtr tempListPtr = initAdjancencyList(tempGraphPtr);

	printList(tempListPtr);

	widthFirstTranverse(tempListPtr, 3);
}//Of testGraphTranverse


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

5.测试代码

Preparing data
Data ready
1 3
0 2 4
1 3 4
0 2
1 2
width first
3 0 2 1 4

总结

图还是非常复杂的一种数据结构，它的相关术语非常多，可以用五种存储方式来表示他，应该掌握深度遍历和广度遍历。