图搜索算法

本文主要是介绍图搜索算法，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

很多游戏、实际问题等的结构都和图有关，在图结构中寻找最优解也就是在图结构中进行搜索。有搜索自然就有广度优先、深度优先和启发式搜索三种方式。

广度优先

顾名思义，先从广度开始：检查完一个结点的全部后继结点才会开始搜索新的结点的后继结点。在实际实施过程中，经常使用队列结构来存储访问结点（先进先出）
一般使用CLOSED表存储已经访问过的结点，使用OPEN表存储待访问的结点列表。以下是C语言队列实现方式，基本操作包括初始化、入队、出队、判空等。

#define MAX_QUEUE_SIZE 1000
#define OK 1
#define ERROR 0

typedef int Status;

struct Queue{
	ElemType Elem[MAX_STACK_SIZE];
	int front;
	int rear;
	int length;
}; 

Status InitQueue(struct Queue &Q)
{
	Q.front=0;
	Q.rear=0;
	Q.length=0;
	return OK;
}

bool QueueEmpty(struct Queue Q)
{
	return (Q.length==0);
}

Status EnQueue(struct Queue &Q, ElemType e)
{
	if(Q.length>=MAX_QUEUE_SIZE)
		return ERROR; 
	Q.Elem[Q.rear]=e;
	Q.rear=(Q.rear+1)%MAX_QUEUE_SIZE;
	Q.length++;
	return OK; 
}

Status DeQueue(struct Queue &Q, ElemType &e)
{
	if(Q.length==0)
		return ERROR;
	e=Q.Elem[Q.front];
	Q.front=(Q.front+1)%MAX_QUEUE_SIZE;
	Q.length--;
	return OK; 
}

深度优先

顾名思义，访问完一个结点的全部后继（一路走到底）然后再开始走新路。同样需要两个表来记录待访问结点和已访问结点，此时使用的是栈结构先进后出。
以下是C语言栈结构实现方式，包括初始化、判空、入栈、出栈等。

struct Stack{
	ElemType Elem[MAX_STACK_SIZE];
	int top;
}; 

Status InitStack(struct Stack &S)
{
	S.top=0;
	return OK;
}

bool StackEmpty(struct Stack S)
{
	if(S.top==0)
		return true;
	else
		return false;
}

Status Push(struct Stack &S, ElemType e)
{
	if(S.top>=MAX_STACK_SIZE)
		return ERROR;
	S.Elem[S.top]=e;
	S.top++;
	
	return OK;
}

Status Pop(struct Stack &S, ElemType &e)
{
	if(S.top==0)
		return ERROR;
	e=S.Elem[S.top-1];
	S.top--;
	
	return OK;
}

这篇关于图搜索算法的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！