typedef struct  //图节点类型
{
	char cityname[20];
	int  value;
	int  cost;
}Ver;
class Graph    //图结构
{
public:
	Graph();
	~Graph();
    Ver V[MaxV];
	int edge[MaxV][MaxV];
	int numofedges;    //注意这个变量的引用位置
	//读取地图节点信息
	void ReadVertex();
	//读取地图边关系信息
	void ReadEdge();
	//取与第V个节点的第一个邻接点
	int GetFirstVertex(int v);
	//找到第V1个节点的V2之后的下一个邻接节点
	int GetNextVertex(int v1, int v2);
	int GetVerValue(int index);//获取V[index] 的ver 的value值
	int GetVerCost(int index);//获取V[index] 的ver 的cost 值
	int GetEdge(int row, int col);//获取edge[row][col] 的值
	void SetVerCost(int index,int cost);
};

class SeqQueue
{
public:
	SeqQueue();
	~SeqQueue();

	void QueueInitiate();
	int QueueNotEmpty();
	int QueueAppend(int x);
	int QueueDelete(int *d);
	int QueueOrderAppend(int x, Graph &G);
	//A*算法使用
	int Queue_A_OrderAppend(int x, Graph &G);
private:
	int queue[MaxSize];
	int rear;
	int front;
	int count;
};

class Stack
{
public:
	Stack();
	~Stack();
	bool StackNotFull();
	bool StakNotEmpty();
	void StackPop(Graph &G);
	void StackPush(int x, Graph &G);
	void PrintStack(Graph &G);
	int GetWeight();
private:
	int a[100];
	int top1;
	int weight;
};

//宽度优先算法
void Romania_Trip::BroadFirstSearch(Graph &graph, int v)
{
	int u, w; i = 0;
	SeqCQuene queue;
	visited[v] = 1;//访问节点
	count++;
	if (v == end)return;
	queue.QueueAppend( v);//入队列
	while (queue.QueueNotEmpty())//队列非空
	{
		queue.QueueDelete(&u);//取队列节点
		w = graph.GetFirstVertex( u);
		while (w != -1)    //有子节点的话
		{
			if (!visited[w])//如果子节点未被访问，则访问子节点
			{
				Visit(w, u);
				visited[w] = 1;
				count++;
				if (w == end)//找到结果
				{
					Print(graph, b, end, v);
					return;
				}
				queue.QueueAppend(w);//节点压入队列
			}
			w = graph.GetNextVertex(u, w);
		}
	}
}

//深度优先算法
bool isOK = false;
int level = 0;
const int Level = 8;//预设的搜索层次
void Romania_Trip::DepthFirstSearch(Graph &graph, int v,  Stack &stack)
{
	int w; i = 0;
	if (isOK == true)return;
	if (level+1 > Level)return;//大于搜索层次时不再深入
	level++;
	visited[v] = 1;//访问该节点
	count++;
	stack.StackPush(v, graph);
	if (v == end || stack.GetWeight() >= MaxWeight)
	{
		w = -1;
		if (v == end&&stack.GetWeight() <= MaxWeight)
		{
			cout << "---深度优先遍历路径为：";
			stack.PrintStack(graph);
			/*if (MaxWeight>stack.GetWeight())
				MaxWeight = stack.GetWeight();*/
			cout << "---路径长度为：" << stack.GetWeight() << endl 
				<< "---访问节点数为：" << count << endl
				<<"---搜索层次："<<level<<endl;
			isOK = true;
		}
	}
	else
	{
		w = graph.GetFirstVertex(v);//取当前节点的第一个子节点
	}
	while (w != -1)
	{
		if (!visited[w])
			DepthFirstSearch(graph, w, stack);//递归访问
		w = graph.GetNextVertex(v, w);//取当前节点的下一个子节点

	}
	visited[v] = 0;//返回时置该节点为未访问
	stack.StackPop( graph);//将该节点弹出栈，并根据graph 中weight 的值更改当前栈值
	level--;
}

//贪婪算法
void Romania_Trip::Greedy_Algorithms(Graph &graph, int v)
{
	int u, w;
	SeqCQuene queue;//队列存储图节点在图中的索引值,优先队列，value小的在队头
	visited[v] = 1;
	if (v == end){ return; }
	queue.QueueOrderAppend( v, graph);//图节点按优先顺序入队列
	count++;     //访问节点数+1
	while (queue.QueueNotEmpty())//宽度优先，循环
	{
		queue.QueueDelete( &u);//删除队列头元素并返回删除的数值
		//cout << "u= " << u << " ";
		
		w = graph.GetFirstVertex(u);
		while (w != -1)
		{
			if (!visited[w])
			{
				Visit(w, u);//访问w节点，将way b 的指向更新
				if (w == end)
				{ 
					//cout << "w==end";
					count++; 
					return; 
				}
				queue.QueueOrderAppend( w, graph); //图节点按优先顺序入队列
				count++;
			}
			w = graph.GetNextVertex(u, w);
		}
	}
}

//A*算法
void Romania_Trip::AStar_Algorithms(Graph &graph, int v)
{
	//i = 0; count = 0;
	int u, w;
	SeqCQuene queue;
	if (v == end) return;//到达终点

	queue.Queue_A_OrderAppend(v, graph); 
	count++;
	while (queue.QueueNotEmpty())
	{
		queue.QueueDelete( &u);
		if (u == end)
		{
			cout << "---路径长度为：" << graph.GetVerCost(u) + graph.GetVerValue(u) << endl
				<< "---访问节点数为：" << count << endl;
			return;
		}
		w = graph.GetFirstVertex( u);
		while (w != -1)
		{
			int cost=graph.GetVerCost(u) + graph.GetEdge(w,u);
			graph.SetVerCost(w, cost);//设置当前节点移动到目标节点的预估费用
			queue.Queue_A_OrderAppend( w, graph);//按预估费用优先入队列 
			count++;
			w = graph.GetNextVertex(u, w);
		}
	}
}