#include <iostream>
#include <fstream>
using namespace std;
#include<iostream>
using namespace std;
const int MVN = 21;
typedef char VexType;//顶点元素类型
typedef int QElemType;
typedef struct QNode
{
	QElemType data;
	QNode *next;
}*LQueuePtr;
typedef struct ArcNode
{
	int adjvex;//弧指向的顶点位置
	int adj;//权
	ArcNode *nextarc;//指向下一条弧的顶点
}*ArcPtr;
struct VexNode
{
	VexType data;//顶点数据
	ArcPtr firstarc;//指向第一条依附于该顶点的弧
	bool visited;//是否被访问过
};
struct ALGraph
{
	VexNode vexs[MVN];
	int kind, vexnum, arcnum;//类型，顶点数，弧数
};
struct LQueue
{
	LQueuePtr front, rear;//队头指针，队尾指针
};
int LocateVex(ALGraph &G, VexType v);//查找顶点
bool InsertArc(ALGraph &G, VexType u, VexType v, int w = 1);//插入弧
void CreateGraph(ALGraph &G, int Kind, char v[]);
void GraphPrint(ALGraph &G);
void QueueInit(LQueue &Q);
void Enqueue(LQueue &Q, QElemType e);
bool Dequeue(LQueue &Q, QElemType &e);
void visit(VexType u);
bool existroad(ALGraph &G, VexType u, VexType v);//是否存在u到v的路径
bool existroad(ALGraph &G, int i, VexType v);

int main()
{
	char g[] = "sacdw#sascsdacadcd#";
	cout << "序列为 "<< endl<< g<< endl;
	int Kind = 3;
	ALGraph G;
	CreateGraph(G, Kind, g);
	GraphPrint(G);
	VexType u = 'a';
	VexType v1 = 'c';
	//VexType v1 = 'w';
	bool f1 =existroad(G, u, v1);
	cout <<u<<"到"<<v1<<"的路径"<< (f1?"":"不")<<"存在" << endl;

	return 0;
}
void QueueInit(LQueue &Q)
{
	Q.front = new QNode;
	Q.front->next = NULL;
	Q.rear = Q.front;
}
void Enqueue(LQueue &Q, QElemType e)
{
	LQueuePtr p;
	p = new QNode;
	p->data = e;
	p->next = NULL;
	Q.rear->next = p;
	Q.rear = p;
}
bool Dequeue(LQueue &Q, QElemType &e)
{
	LQueuePtr p;
	if (Q.rear == Q.front)
	{
		return false;
	}
	p = Q.front;
	Q.front = p->next;
	e = Q.front->data;
	delete p;
	return true;
}
void visit(VexType u)
{
	cout << u << ",";
}
bool existroad(ALGraph &G, int i, VexType v)
{
	int j;
	ArcPtr p;
	if (G.vexs[i].data == v)
	{
		return true;
	}
	G.vexs[i].visited = true;
	for (p = G.vexs[i].firstarc; p; p = p->nextarc)
	{

		j = p->adjvex;
		if (!G.vexs[j].visited)
		{
			if (existroad(G, j, v))
			{
				return true;
			}
		}
	}
	return false;
}
bool existroad(ALGraph &G, VexType u, VexType v)
{
	int m;
	m = LocateVex(G, u);
	if (m == 0)
	{
		return false;
	}
	if (!G.vexs[m].firstarc)
	{
		return false;
	}
	int i;
	for (i = 1; i <= G.vexnum; i++)
	{
		G.vexs[i].visited = false;
	}
	return existroad(G, m, v);
}
int LocateVex(ALGraph &G, VexType v)//查找顶点
{
	int i;
	for (i = G.vexnum; i > 0 && G.vexs[i].data != v; i--);
	return i;
}
bool InsertArc(ALGraph &G, VexType u, VexType v, int w )
{
	ArcPtr p;
	int i, j;
	bool found;
	i = LocateVex(G, u);
	if (i == 0)
	{
		return false;
	}
	j = LocateVex(G, v);
	if (j == 0 || j == i)
	{
		return false;
	}
	for (found = false, p = G.vexs[i].firstarc; p && !found; p = p->nextarc)
	{
		if (p->adjvex == j)
		{
			found = true;
		}
	}
	if (found)
	{
		return false;
	}
	G.arcnum++;
	p = new ArcNode;
	p->adjvex = j;
	p->adj = w;
	p->nextarc = G.vexs[i].firstarc;
	G.vexs[i].firstarc = p;//表头插入弧，假设对弧的次序无要求
	if (G.kind <= 2)
	{
		return true;
	}
	G.arcnum++;
	p = new ArcNode;
	p->adjvex = i;
	p->adj = w;
	p->nextarc = G.vexs[j].firstarc;
	G.vexs[j].firstarc = p;
	return true;
}
void CreateGraph(ALGraph &G, int Kind, char v[])
{
	int i, w;
	G.kind = Kind;
	G.arcnum = 0;
	i = 0;
	while (true)
	{
		if (v[i] == '#')
		{
			break;
		}
		i++;
		G.vexs[i].data = v[i - 1];
		G.vexs[i].firstarc = NULL;
	}
	G.vexnum = i;
	i++;
	while (true)
	{
		if (v[i] == '#')
		{
			break;
		}
		if (G.kind == 1 || G.kind == 3)
		{
			w = 1;
		}
		else
		{
			w = v[i + 2] - 48;
		}
		InsertArc(G, v[i], v[i + 1], w);
		i = i + 2;
		if (w == 2 || w == 4)
		{
			i++;
		}
	}

}
void GraphPrint(ALGraph &G)
{
	ArcPtr p;
	cout << "邻接表" << endl;
	for (int i = 1; i <= G.vexnum; i++)
	{
		cout << G.vexs[i].data;
		for (p = G.vexs[i].firstarc; p; p = p->nextarc)
		{
			cout << "->" << p->adjvex;
		}
		cout << endl;
	}
}