#include<iostream>
#include<string.h>
#include<queue>
#define MaxSize 100 //最大结点数 
using namespace std;

typedef struct ArcNode  //存储与结点相连的边 
{
	int adjvex; //该边所指向的顶点的位置
	ArcNode* nextarc; //指向下一条与结点相连的边 
	int weight;  //边的权重 
}ArcNode; 

typedef struct VNode  //存储结点信息 
{
	char data;  //结点数据域 
	ArcNode *firstArc; //结点指针域，指向与其相连的第一个边 
}VNode;

class UndiGraph  //无向图 
{
	public:
		UndiGraph();
		int LocateVex(char a);  //寻找数据域为a的结点的位置 
		void CreatGraph();  //创建无向图 
		void Visit(int i);  //访问i位置上的结点数据 
		void dfs(int a=0);   //连通图的深度优先遍历
		void DFS(int a=0);   //图的深度优先遍历，这里的图可以是连通图，也可以是非连通图 
		void bfs(int a=0);  //连通图广度优先遍历 
		void BFS(int a=0);  //图的广度优先遍历，这里的图可以是连通图，也可以是非连通图 
	private:
		int vexnum;  //结点数 
		int arcnum;  //边数
		VNode list[MaxSize];  //结点表,存储所有的结点 
		bool visited[MaxSize]; 
};

UndiGraph::UndiGraph()
{
	vexnum = arcnum = 0;
	memset(visited,false,sizeof(visited));
}

int UndiGraph::LocateVex(char a)  //寻找数据域为a的结点的位置
{
	for(int i=0; i<vexnum; ++i)
	{
		if(list[i].data==a)
		{
			return i;
		}
	}
}

void UndiGraph::CreatGraph() //创建无向图 
{
	cout << "输入结点个数和边数：";
	cin >> vexnum >> arcnum;
	for(int i=0; i<vexnum; ++i)
	{
		cout << "输入第" << i+1 << "个结点的值：";
		cin >> list[i].data;
		list[i].firstArc = NULL;
	}
	char a, b;  //a,b记录边的两个端点的值
	int weight; //weight记录边的权值 
	int p, q;   //p,q记录两个端点在结点表中的位置 
	for(int i=0; i<arcnum; ++i)
	{
		cout << "输入第" << i+1 << "条边的两个端点的值及权重：";
		cin >> a >> b >> weight;
		p = LocateVex(a);
		q = LocateVex(b);
		
		ArcNode *an = new ArcNode();
		an->adjvex =q;
		an->weight = weight;
		an->nextarc = list[p].firstArc;
		list[p].firstArc = an;
		
		ArcNode *bn = new ArcNode();
		bn->adjvex =p;
		bn->weight = weight;
		bn->nextarc = list[q].firstArc;
		list[q].firstArc = bn;
	}
}

void UndiGraph::Visit(int i)  //访问i位置上的结点数据 
{
	cout << list[i].data;
	visited[i] = true;
}

void UndiGraph::dfs(int a)  //连通图的深度优先遍历
{
	Visit(a);
	VNode vn = list[a];
	ArcNode *an = vn.firstArc;
	while(an!=NULL&&!visited[an->adjvex])
	{
		dfs(an->adjvex);
		an = an->nextarc;
	}
}

void UndiGraph::DFS(int a)  //图的深度优先遍历，这里的图可以是连通图，也可以是非连通图 
{
	for(int i=a; i<vexnum; ++i)  //对每个连通分量进行深度优先遍历 
	{
		if(!visited[i])
		{
			dfs(i);
		}
	}
}

void UndiGraph::bfs(int a)  //连通图广度优先遍历
{
	queue<int> q;
	q.push(a);
	visited[a] = true;
	while(!q.empty())
	{
		Visit(q.front());
		VNode vn = list[q.front()];
		ArcNode *an = vn.firstArc;
		while(an!=NULL)  //将当前节点未被访问的兄弟结点入队列 
		{
			if(!visited[an->adjvex])
			{
				q.push(an->adjvex);   
				visited[an->adjvex] = true;
			}
			an = an->nextarc;
		}
		q.pop();
	}
}

void UndiGraph::BFS(int a)  //图的广度优先遍历，这里的图可以是连通图，也可以是非连通图 
{
	for(int i=a; i<vexnum; ++i)  //对每个连通分量做广度优先遍历 
	{
		if(!visited[i])
		{
			bfs(i);
		}
	}
}

int main()
{
	UndiGraph a;
	a.CreatGraph();
	a.DFS();
}