b_search.h

一个求无向无权图的最短路径的算法

//?:(006)b_search.h
//:B_SEARCH.H header file(class file)
#ifndef B_SEARCH_H
#define B_SEARCH_H
#include "c_node.h"
#include "s_stack.h"
#include "l_list.h"
#include "q_queue.h"

class b_search
{
	l_list<c_node> list;
	q_queue<c_node> queue;
	c_node rec_node;
public:
	s_stack<char> stack;
	g_graph<char> graph;
public:
	b_search(char v[],int n,rcw e[],int e1);
	int get_char(char c_str);
	int find_char(char c_str);
	c_node  find_id(int i);
	void b_creatgraph(char v[],int n,rcw e[],int e1);
	void b_open_close(char c_start,char c_end);
	void find_path(void);
	~b_search();
};
b_search::b_search(char v[],int n,rcw e[],int e1)
{
	graph.g_init(n);
	graph.creat_graph(v,n,e,e1);
}
int  b_search:: get_char(char c_str)
{
	for(int i=0;i<graph.vertices.get_size();i++)
		if(graph.vertices.get_data(i)==c_str)
			return i;
	return -1;
}
int b_search::find_char(char c_str)
{
	for(int i=0;i<list.get_size();i++)
		if(list.get_data(i).get_node()==c_str)
			return 1;
	return 0;
}
c_node b_search::find_id(int n)
{
	for(int i=0;i<list.get_size();i++)
		if(list.get_data(i).get_nodeid()==n)
			return list.get_data(i);
}
void b_search::b_open_close(char c_start,char c_end)
{
	c_node o_node,cl_node;
	int n=1,flag=1,p,d;
	char c_tmp;
	o_node.set_node(c_start);
	o_node.set_nodeid(-1);
	o_node.set_parentid(0);
	rec_node=o_node;
	queue.q_append(o_node);
	while(queue.q_notempty()&&flag)
	{
		cl_node=queue.q_delete();
		cl_node.set_nodeid(n);
		list.l_insert(list.get_size(),cl_node);
		p=get_char(cl_node.get_node());
		if((d=graph.get_first_vex(p))!=-1)
		{
			c_tmp=graph.vertices.get_data(d);
			o_node.set_nodeid(-1);
			o_node.set_node(c_tmp);
			o_node.set_parentid(n);
			if(find_char(c_tmp)!=1)
				queue.q_append(o_node);
			if(c_tmp==c_end)
			{
				flag=0;
				rec_node=o_node;
				break;
			}
			while((d=graph.get_next_vex(p,d))!=-1)
			{
				c_tmp=graph.vertices.get_data(d);
				o_node.set_nodeid(-1);
				o_node.set_node(c_tmp);
				o_node.set_parentid(n);
				if(find_char(c_tmp)!=1)
					queue.q_append(o_node);
				if(c_tmp==c_end)
				{
					flag=0;
					rec_node=o_node;
					break;
				}
			}
		}
		n++;
	}
}
void b_search::find_path(void)
{
	c_node node;
	node=rec_node;
	stack.stack_push(node.get_node());
	while(node.get_parentid())
	{
		node=find_id(node.get_parentid());
		stack.stack_push(node.get_node());
	}
}
b_search::~b_search()
{
}
#endif
//:End the b_search class file