#include
#include
#include
#include
#define?MaxSize?30
#define?Affinity?100
using?namespace?std;
class?AdjGraph
{
public:char?*vexs;
	???int?**arcs;
	???int?*visited*de;
	???int?vexnumarcnum;
	???AdjGraph（）
	???{
		???vexnum=arcnum=0;
		???vexs=NULL;visited=NULL;arcs=NULL;de=NULL;
	???}
	???AdjGraph（int?vint?a）
	???{
		???int?ij;
		???vexnum=v;arcnum=a;de=new?int[vexnum];
		???vexs=new?char[vexnum];visited=new?int[vexnum];
		???arcs=（int?**）new?int*[vexnum];
		???for（i=0;i		???{
			???arcs[i]=new?int[vexnum];
		???}
		???for（i=0;i		???{
			???visited[i]=0;vexs[i]=‘\0‘;de[i]=0;
			???for（j=0;j			???{
				???if（i==j）{arcs[i][j]=0;}
				???else{
					???arcs[i][j]=Affinity;}
			???}
		???}
	???}
	???~AdjGraph（）{}
	???int?posvex（char?x）
	???{
		???int?i=0;
		???for（i=0;i		???{
			???if（vexs[i]==x）
				???break;
		???}
		???if（i		???{return?i;}
		???else
		???{return?-1;}
	???}
	???void?clearVisit（）
	???{
		???int?i;
		???for（i=0;i		???{
			???visited[i]=0;
		???}
	???}
	???bool?CreateDUG（）
	???{
		???cout<<“請輸入頂點信息:“<		???int?i=0ab;char?lr;
		???for（i=0;i		???{cin>>vexs[i];}
		???for（i=0;i		???{
			???int?w;
			???cout<<“輸入第“<			???cin>>l>>r;
			???a=posvex（l）;b=posvex（r）;
			??cout<<“請輸入該邊的權重：“<			???cin>>w;
			???arcs[a][b]=w;arcs[b][a]=w;de[a]++;de[b]++;
		???}
		???return?true;
	???}
	???int?FirstAdj（int?i）
	???{
		???int?j=0;
		???while（j		???{j++;}
		???if（j			???return?j;
		???else
			???return?-1;
	???}?
	???int?SecondAdj（int?iint?k）//頂點下標為i的頂點相對于k的下一個頂點k為i的當前鄰接頂點二者都是頂點下標
	???{
		???int?j=k+1;
		???while（j		???{j++;}
		???if（j			???return?j;
		???else
			???return?-1;
	???}
	???void?DFS（int?v）
	???{
		???int?w;visited[v]=1;cout<		???for（w=FirstAdj（v）;w>=0;w=SecondAdj（vw））
		???{
			???if（!visited[w]）
			???{DFS（w）;}
		???}
	???}
	???void?BFS（int?v）
	???{
		???int?uw;;
		?????queue?q1;
		???if（!visited[v]）
		???{
			???visited[v]=1;cout<			???q1.push（v）;
			???while（!q1.empty（））
			???{
				???u=q1.front（）;
				???q1.pop（）;
				???for（w=FirstAdj（v）;w>=0;w=SecondAdj（vw））
				???{
					???if（!visited[w]）??
???????????????