1.深度优先代码

#include<stdio.h>
#include<malloc.h>
#define QUEUE_SIZE 10
int *visitedPtr;
/**
 *The struct of a graph.
 */
typedef struct Graph{
	int **connections;
	int numNodes;
}*GraphPtr;

/**
 Initialize a graph.
 */
GraphPtr initGraph(int paraSize,int **paraData){
	int i,j;
	GraphPtr resultPtr=(GraphPtr)malloc(sizeof(struct Graph));
	resultPtr->numNodes=paraSize;
	resultPtr->connections=(int**)malloc(paraSize*sizeof(int *));
	for(i=0;i<paraSize;i++){
		resultPtr->connections[i]=(int *)malloc(paraSize*sizeof(int));
		for(j=0;j<paraSize;j++){
			resultPtr->connections[i][j]=paraData[i][j];
		}
	}
	return resultPtr;
}

/**
 *Anjacent node.
 */
typedef struct AdjacencyNode{
	int column;
	AdjacencyNode* next;
}AdjacencyNode,*AdjacentNodePtr;

/**
 *A adjacency list.
 */
typedef struct AdjacencyList{
	int numNodes;
	AdjacencyNode* headers;
}AdjacencyList,*AdjacencyListPtr;

/**
 *Construct an adjacent list.
 */
AdjacencyListPtr graphToAdjacentList(GraphPtr paraPtr){
	//Allocate space.
	int i,j,tempNum;
	AdjacentNodePtr p,q;
	tempNum=paraPtr->numNodes;
	AdjacencyListPtr resultPtr=(AdjacencyListPtr)malloc(sizeof(struct AdjacencyList));
	resultPtr->numNodes=tempNum;
	resultPtr->headers=(AdjacencyNode*)malloc(sizeof(struct AdjacencyNode)*tempNum);
	//Fill the data.
	for(i=0;i<tempNum;i++){
		p=&(resultPtr->headers[i]);
		p->column=-1;
		p->next=NULL;
		for(j=0;j<tempNum;j++){
			if(paraPtr->connections[i][j]>0){
				//Create a new node.
				q=(AdjacentNodePtr)malloc(sizeof(struct AdjacencyNode));
				q->column=j;
				q->next=NULL;
				p->next=q;
				p=q;
			}
		}
	}
	return resultPtr;
}

/**
 *Print an adjacent list.
 */
void printAdjacentList(AdjacencyListPtr paraPtr){
	int i;
	AdjacentNodePtr p;
	int tempNum=paraPtr->numNodes;
	printf("This is the graph:\r\n");
	for(i=0;i<tempNum;i++){
		p=paraPtr->headers[i].next;
		while(p!=NULL){
			printf("%d ",p->column);
			p=p->next;
		}
		printf("\r\n");
	}
		
}

/**
 *initialize the tranverse.
 */
void initTranverse(AdjacencyListPtr paraListPtr){
	int i=0;
	visitedPtr=(int *)malloc(sizeof(int)*paraListPtr->numNodes);
	for(i=0;i<paraListPtr->numNodes;i++){
		visitedPtr[i]=0;
	}
}

/** 
 *depth first tranverce.
 */ 
void depthFirstTranverse(AdjacencyListPtr paraListPtr,int paraNode){
	int j;
	AdjacentNodePtr p;
	printf("%d\t",paraNode);
	visitedPtr[paraNode]=1;
	for(p=&(paraListPtr->headers[paraNode]);p!=NULL;p=p->next){
		j=p->column;
		if(!visitedPtr[j]){
			depthFirstTranverse(paraListPtr,j);
		}
	}
	
}

/**
 *Test graph tranverse.
 */
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 data\r\n");
	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 ready \r\n");
	GraphPtr tempGraphPtr=initGraph(5,tempPtr);
	AdjacencyListPtr tempListPtr=graphToAdjacentList(tempGraphPtr);
	printAdjacentList(tempListPtr);
	initTranverse(tempListPtr);
	printf("Depth first:\r\n");
	depthFirstTranverse(tempListPtr,4);
}

/**
 *The entrance.
 */
int main(){
	testGraphTranverse();
	return 1;
}

2.深度优先运行结果

Preparing data
Data ready
This is the graph:
1 3
0 2 4
1 3 4
0 2
1 2
Depth first:
4       1       0       3       2

3.广度优先代码

#include<stdio.h>
#include<malloc.h>
#define QUEUE_SIZE 10
int *visitedPtr;
/**
 *The struct of a graph.
 */
typedef struct Graph{
	int **connections;
	int numNodes;
}*GraphPtr;

/**
 Initialize a graph.
 */
GraphPtr initGraph(int paraSize,int **paraData){
	int i,j;
	GraphPtr resultPtr=(GraphPtr)malloc(sizeof(struct Graph));
	resultPtr->numNodes=paraSize;
	resultPtr->connections=(int**)malloc(paraSize*sizeof(int *));
	for(i=0;i<paraSize;i++){
		resultPtr->connections[i]=(int *)malloc(paraSize*sizeof(int));
		for(j=0;j<paraSize;j++){
			resultPtr->connections[i][j]=paraData[i][j];
		}
	}
	return resultPtr;
}

/**
 *A queue with a number of indices.
 */
typedef struct GraphNodeQueue{
	int *nodes;
	int front;
	int rear;
}GraphNodeQueue,*QueuePtr;

/**
 *Initialize the queue;
 */
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;
}

/**
 *Is the queueEmpty.
 */
bool isQueueEmpty(QueuePtr paraQueuePtr){
	if((paraQueuePtr->front+1)%QUEUE_SIZE==paraQueuePtr->rear){
		return true;
	}
	return false;
}

/**
 *Add a node to the queue.
 */
void enqueue(QueuePtr paraQueuePtr,int paraNode){
	if((paraQueuePtr->rear+1)%QUEUE_SIZE==paraQueuePtr->front%QUEUE_SIZE){
		printf("ERROR,enqueue %d,enqueue %d.queue full.\r\n",paraNode);
		return ;
	}
	paraQueuePtr->nodes[paraQueuePtr->rear]=paraNode;
	paraQueuePtr->rear=(paraQueuePtr->rear+1)%QUEUE_SIZE;
}

/**
 *Remove an element from the queue and return.
 */
int dequeue(QueuePtr paraQueuePtr){
	if(isQueueEmpty(paraQueuePtr)){
		printf("ERROR,empty queue\r\n");
		return NULL;
	}
	paraQueuePtr->front=(paraQueuePtr->front+1)%QUEUE_SIZE;
	return paraQueuePtr->nodes[paraQueuePtr->front];
}

/**
 *Anjacent node.
 */
typedef struct AdjacencyNode{
	int column;
	AdjacencyNode* next;
}AdjacencyNode,*AdjacentNodePtr;

/**
 *A adjacency list.
 */
typedef struct AdjacencyList{
	int numNodes;
	AdjacencyNode* headers;
}AdjacencyList,*AdjacencyListPtr;

/**
 *Construct an adjacent list.
 */
AdjacencyListPtr graphToAdjacentList(GraphPtr paraPtr){
	//Allocate space.
	int i,j,tempNum;
	AdjacentNodePtr p,q;
	tempNum=paraPtr->numNodes;
	AdjacencyListPtr resultPtr=(AdjacencyListPtr)malloc(sizeof(struct AdjacencyList));
	resultPtr->numNodes=tempNum;
	resultPtr->headers=(AdjacencyNode*)malloc(sizeof(struct AdjacencyNode)*tempNum);
	//Fill the data.
	for(i=0;i<tempNum;i++){
		p=&(resultPtr->headers[i]);
		p->column=-1;
		p->next=NULL;
		for(j=0;j<tempNum;j++){
			if(paraPtr->connections[i][j]>0){
				//Create a new node.
				q=(AdjacentNodePtr)malloc(sizeof(struct AdjacencyNode));
				q->column=j;
				q->next=NULL;
				p->next=q;
				p=q;
			}
		}
	}
	return resultPtr;
}

/**
 *Print an adjacent list.
 */
void printAdjacentList(AdjacencyListPtr paraPtr){
	int i;
	AdjacentNodePtr p;
	int tempNum=paraPtr->numNodes;
	printf("This is the graph:\r\n");
	for(i=0;i<tempNum;i++){
		p=paraPtr->headers[i].next;
		while(p!=NULL){
			printf("%d",p->column);
			p=p->next;
		}
		printf("\r\n");
	}
		
}


/**
 *Width first tranvence.
 */
void widthFirstTranverse(AdjacencyListPtr paraListPtr,int paraStart){
	printf("wdith first\r\n");
	int i,j,tempNode;
	AdjacentNodePtr p;
	i=0;
	visitedPtr=(int *)malloc(sizeof(int)*paraListPtr->numNodes);
	for(i=0;i<paraListPtr->numNodes;i++){
		visitedPtr[i]=0;
	}
	QueuePtr tempQueuePtr=initQueue();
	printf("%d\t",paraStart);
	visitedPtr[paraStart]=1;
	enqueue(tempQueuePtr,paraStart);
	while(!isQueueEmpty(tempQueuePtr)){
		tempNode=dequeue(tempQueuePtr);
		for(p=&(paraListPtr->headers[tempNode]);p!=NULL;p=p->next){
			j=p->column;
			if(visitedPtr[j]){
				continue;
			}
			printf("%d\t",j);
			visitedPtr[j]=1;
			enqueue(tempQueuePtr,j);
		}
	}
	printf("\r\n");
}

/**
 *Test graph tranverse.
 */
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 data\r\n");
	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 ready \r\n");
	GraphPtr tempGraphPtr=initGraph(5,tempPtr);
	AdjacencyListPtr tempListPtr=graphToAdjacentList(tempGraphPtr);
	printAdjacentList(tempListPtr);
	widthFirstTranverse(tempListPtr,4);
}

/**
 *The entrance.
 */
int main(){
	testGraphTranverse();
	return 1;
}

4.广度优先运行结果

Preparing data
Data ready
This is the graph:
1 3
0 2 4
1 3 4
0 2
1 2
wdith first
4       1       2       0       3

# 深度优先 # 数据结构 # 算法
Logo
魔乐社区

魔乐社区（Modelers.cn) 是一个中立、公益的人工智能社区，提供人工智能工具、模型、数据的托管、展示与应用协同服务，为人工智能开发及爱好者搭建开放的学习交流平台。社区通过理事会方式运作，由全产业链共同建设、共同运营、共同享有，推动国产AI生态繁荣发展。

更多推荐

cover

【计算机视觉】Pixel逐像素分类&Mask掩码分类理解摘要

avatar 魔乐社区

计算机视觉（opencv）实战三十二——CascadeClassifier 人脸微笑检测（摄像头）

本文从原理到实现，详细介绍了基于 OpenCV Haar 分类器的人脸与微笑检测：讲解了 Haar 特征和级联检测原理。对代码逐行拆解并解释参数含义。画出完整流程图，帮助理解执行过程。给出了常见问题和优化建议，甚至扩展到深度学习方法。这种方法简单、轻量、实时性好，非常适合入门和小型应用项目。但如果需要更高准确率和更强鲁棒性，建议使用深度学习检测器替代 Haar 分类器。

avatar 魔乐社区
cover

小杰机器学习（seven）——贝叶斯分类

avatar 魔乐社区