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

class UndiGraph  //无向图 
{
	public:
		UndiGraph();
		int LocateVex(char 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;  //边数
		char vexs[MaxSize];  //结点表，设每个结点的数据类型都为char类型 
		int arcs[MaxSize][MaxSize];  //邻接矩阵 
		bool visited[MaxSize];
};

UndiGraph::UndiGraph()
{
	vexnum = arcnum = 0;
	memset(vexs,0,sizeof(vexs));  //初始化结点数组 
	memset(arcs,0,sizeof(arcs));  //初始化邻接矩阵 
	memset(visited,false,sizeof(visited));  //初始化访问数组 
}

int UndiGraph::LocateVex(char a)  //查找结点在结点表中的位置
{
	for(int i=0; i<vexnum; ++i)
	{
		if(vexs[i]==a)
		{
			return i;
		}
	}
}

void UndiGraph::CreatGraph()  //创建无向图
{
	cout << "输入结点个数：";
	cin >> vexnum;
	cout << "输入边数：";
	cin >> arcnum;
	for(int i=0; i<vexnum; ++i)
	{
		cout << "输入第" << i+1 << "个结点的值：";
		cin >> vexs[i];
	}
	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);
		arcs[p][q] = arcs[q][p] = weight;
	}
}

void UndiGraph::Visit(int i) //访问i位置上的结点
{
	cout << vexs[i] << " ";
	visited[i] = true;
} 

void UndiGraph::dfs(int a)  //连通图的深度优先遍历 
{
	int p = a;
	Visit(p);
	for(int i=0; i<vexnum; ++i)
	{
		if(arcs[p][i]!=0&&!visited[i])
		{
			dfs(i);
		}
	}
}

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())
	{
		int p = q.front();
		Visit(p);
		for(int i=0; i<vexnum; ++i)  //将当前结点未被访问的兄弟结点入队列 
		{
			if(arcs[p][i]!=0&&!visited[i])
			{
				q.push(i);
				visited[i] = true;
			}
		}
		q.pop();
	}
}

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

int main()
{
	
}