股票交易指令接口:图的广度优先遍历和深度优先遍历

五.完整代码

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define MAX_VERTEX_NUM 20  // 最大顶点数

typedef struct {
	char vertex[MAX_VERTEX_NUM];  // 存放顶点信息
	int edge[MAX_VERTEX_NUM][MAX_VERTEX_NUM];  // 存放边信息
	int vertex_num;  // 顶点数
	int edge_num;  // 边数
} Graph;

bool visited1[MAX_VERTEX_NUM];             //BFS访问标记数组
bool visited2[MAX_VERTEX_NUM];             //DFS访问标记数组

//求图G中顶点x的第一个邻接点下标
int FirstNeighbor(Graph *G,char x){
	int n = -1;      //待查询结点在数组里的下标
	for(int i=0;i<G->vertex_num;i++){
		if(G->vertex[i]==x) {
			n=i;
			break;
		}
	}
	if(n == -1){  // 如果查询节点不存在
		printf("Error: 结点不存在
");
	}
	int count=0;
	int nx;        //第一个邻接点在数组里的下标
	//现在知道了他在第n个，所以我们查询边矩阵第n行中第一个1在哪就知道第一个邻接点是谁
	for(int j=0;j<G->vertex_num;j++){
		if(G->edge[n][j]==1) count++;
		if(count==1){
			nx=j;
			break;
		}
	}
	return nx;
}

int NextNeighbor(Graph *G,char x,char y){
	int n = -1;      //待查询结点在数组里的下标
	for(int i=0;i<G->vertex_num;i++){
		if(G->vertex[i]==x) {
			n=i;
			break;
		}
	}
	if(n == -1){  // 如果查询节点不存在
		printf("Error: 结点不存在
");
	}
	int count=0;
	int ny = -1;   //存放返回邻接点数组下标
	for(int j=0;j<G->vertex_num;j++){
		if(G->vertex[j]==y) {
			ny=j;
			break;
		}
	}
	int nx = -1;   //存放返回邻接点数组下标
	for(int j=ny+1;j<G->vertex_num;j++){
		if(G->edge[n][j]==1){
			nx=j;
			break;
		}   
	}
	return nx;
}

void BFS(Graph *G,char x){
	int n;              
	for(int i=0;i<G->vertex_num;i++){
		if(G->vertex[i]==x) {
			n=i;
			break;
		}
	}
	if(n == -1){  
		printf("Error: 结点不存在
");
	}
	
	char queue[MAX_VERTEX_NUM], front = -1, rear = -1;          
	queue[++rear] = G->vertex[n];      
	visited1[n] = true;                 
	while(front !=rear){        
		char current_vertex=queue[++front];      
		printf("%c ",current_vertex);
		
		for(int w=FirstNeighbor(G,current_vertex);w>=0;w=NextNeighbor(G,current_vertex,G->vertex[w])){    
			if(!visited1[w]){
				queue[++rear]=G->vertex[w];
				visited1[w]=true;    
			}
		}
	}   
}
//你以为这就是执行函数吗？如果你这样做存在多个连通分量绝对出错


//BFS执行函数
void BFSTraverse(Graph *G){
	for(int i=0;i<G->vertex_num;i++){
		visited1[i]=false;           //标记数组初始化
	}
	for(int i=0;i<G->vertex_num;++i){
		if(!visited1[i])
			BFS(G,G->vertex[i]);
	}
}

//DFS函数
void DFS(Graph *G,char x){
	int n;              
	for(int i=0;i<G->vertex_num;i++){
		if(G->vertex[i]==x) {
			n=i;
			break;
		}
	}
	if(n == -1){  
		printf("Error: 结点不存在
");
	}
	printf("%c ",G->vertex[n]);       //访问顶点
	visited2[n]=true;            
	for(int w=FirstNeighbor(G,G->vertex[n]);w>=0;w=NextNeighbor(G,G->vertex[n],G->vertex[w]))
		if(!visited2[w]){
			DFS(G,G->vertex[w]);
		}
}
//DFS相比BFS函数，它使用的是栈也就是递归操作

//DFS执行函数
void DFSTraverse(Graph *G){
	for(int i=0;i<G->vertex_num;i++){
		visited2[i]=false;           //标记数组初始化
	}
	for(int i=0;i<G->vertex_num;++i){
		if(!visited2[i])
			DFS(G,G->vertex[i]);
	}
}

int main(){
	Graph G;
	G.vertex_num=5;
	G.edge_num=6;
	//人为构造图的顶点
	for(int i=0;i<G.vertex_num;i++){
		G.vertex[i]= "A"+i;
	}
	for(int i=0; i<G.vertex_num; i++){
		for(int j=0; j<G.vertex_num; j++){
			G.edge[i][j]=0;
		}
	}
	//人为构造图的边
	G.edge[0][1]=1;
	G.edge[0][3]=1;
	G.edge[1][2]=1;
	G.edge[2][3]=1;
	G.edge[1][4]=1;
	G.edge[2][4]=1;
	printf("BFS的股票交易指令接口,遍历结果为：");
	BFSTraverse(&G);
	printf("
");
	printf("DFS的股票交易指令接口,遍历结果为：");
	DFSTraverse(&G);	
	return 0;
}

四.核心功能实现

广度优先搜索类似于二叉树的层序遍历算法。基本思想是:首先访问起始顶点v，接着由v出发，依次访问v的各个未访问过的邻接顶点w1,w2…,wn，然后依次访问w1,w2…,wn;的所有未被访问过的邻接顶点;再从这些访问过的顶点出发，访问它们所有未被访问过的邻接顶点，直至中所有顶点都被访问过为止。若此时中尚有顶点未被访问，则另选中一个未曾被访问的顶点作为始点，重复上述过程，直至中所有顶点都被访问到为止。Dijkstra单源最短路径算法和Prim最小生成树算法也应用了类似的思想。换句话说，广度优先搜索遍历的过程是以v为起始点，由近至远依次访问和v有路径相通且路径长度为1,2,…的顶点。广度优先搜索是-种分层的查找过程，每向前走一步可能访问-批顶点，不像深度优先搜索那样有往回退的情况，因此它不是一个递归的算法。为了实现逐层的访问，算法必须借助一个辅助队列，以记忆正在访问的顶点的下一层顶点。

二.广度优先搜索

基本原理

DFS函数

//DFS函数
void DFS(Graph *G,char x){
	int n;              
	for(int i=0;i<G->vertex_num;i++){
		if(G->vertex[i]==x) {
			n=i;
			break;
		}
	}
	if(n == -1){  
		printf("Error: 结点不存在
");
	}
	printf("%c ",G->vertex[n]);       //访问顶点
	visited2[n]=true;            
	for(int w=FirstNeighbor(G,G->vertex[n]);w>=0;w=NextNeighbor(G,G->vertex[n],G->vertex[w]))
		if(!visited2[w]){
			DFS(G,G->vertex[w]);
		}
}
//DFS相比BFS函数，它使用的是栈也就是递归操作

举例说明

BFS函数

void BFS(Graph *G,char x){
	int n;              
	for(int i=0;i<G->vertex_num;i++){
		if(G->vertex[i]==x) {
			n=i;
			break;
		}
	}
	if(n == -1){  
		printf("Error: 结点不存在
");
	}
	
	char queue[MAX_VERTEX_NUM], front = -1, rear = -1;          
	queue[++rear] = G->vertex[n];      
	visited[n] = true;                 
	while(front !=rear){        
		char current_vertex=queue[++front];      
		printf("%c ",current_vertex);
		
		for(int w=FirstNeighbor(G,current_vertex);w>=0;w=NextNeighbor(G,current_vertex,G->vertex[w])){    
			if(!visited[w]){
				queue[++rear]=G->vertex[w];
				visited[w]=true;    
			}
		}
	}   
}

与广度优先搜索不同，深度优先搜索类似于树的先序遍历。如其名称中所暗含的意思-样，这种搜索算法所遵循的搜索策略是尽可能“深”地搜索一个。它的基本思想如下:首先访问中某--起始顶点v,然后由v出发，访问与v邻接且未被访问的任意一个顶点w，再访问与wi邻接且未被访问的任意-一个顶点…重复上述过程。当不能再继续向下访问时，依次退回到最近被访问的顶点，若它还有邻接顶点未被访问过，则从该点开始继续上述搜索过程，直至中所有顶点均被访问过为止。

效率分析

假设从a结点开始访问，a先入队。此时队列非空，取出队头元素a,由于b,c与a邻接且未被访问过，于是依次访问b,c,并将b,c依次入队。队列非空，取出队头元素b,依次访问与b邻接且未被访问的顶点d,e,并将d,e入队。此时队列非空，取出队头元素c,访问与c邻接且未被访问的顶点f,g,并将f,g入队。此时，取出队头元素d,但与d邻接且未被访问的顶点为空，故不进行任何操作。继续取出队头元素e,将h入队列…最终取出队头元素h后，队列为空，从而循环自动跳出。遍历结果为abcdefgh。

基本原理

举例说明

三.深度优先收索

以BFS例子的无向为例，深度优先搜索的过程:首先访问a,并置a访问标记;然后访问与a邻接且未被访问的顶点b,置b访问标记;然后访问与b邻接且未被访问的顶点d,置d访问标记。此时d已没有未被访问过的邻接点，故返回上一个访问过的顶点b,访问与其邻接且未被访问的顶点e，置e.标…以此类推，直至中所有的顶点都被访问一次。遍历结果为abdehcfg。

图的广度优先遍历和深度优先遍历

的遍历是指从中的某一顶点出发，按照某种搜索方法沿着中的边对中的所有顶点访问一次且仅访问一次。注意到树是一种特殊的，所以树的遍历实际上也可视为一种特殊的的遍历。的遍历算法是求解的连通性问题、拓扑排序和求关键路径等算法的基础。的遍历比树的遍历要复杂得多，因为的任意一个顶点都可能和其余的顶点相邻接，所以在访问某个顶点后，可能沿着某条路径搜索又回到该顶点上。为避免同-.顶点被访问多次，在遍历的过程中，必须记下每个已访问过的顶点，为此可以设一个辅助数组visited[]来标记项点是否被访问过。的遍历算法主要有两种：广度优先搜索和深度优先搜索。

文章为作者独立观点，不代表股票交易接口观点