邻接表表示，广度优先搜索，敲了老半天，最后还是用舍友的了。实在找不到bug，有这个思想就行。

模板参数T是顶点数据类型，E是边权值数据类型。

#include <iostream>
#include <string>
#include<iostream>
using namespace std;

template <class T>
class LinkNode
{
public:
	
 LinkNode<T>  *link;
 LinkNode(const T&item,LinkNode<T> *ptr = NULL)
{data = item;link = ptr;}
 LinkNode(LinkNode<T> *ptr = NULL){link = ptr;}
   T data;
};
template<class T>
class LinkedQueue{
public:
	LinkedQueue():rear(NULL),front(NULL){}
	~LinkedQueue(){makeEmpty();}
	bool EnQueue(T&x);
	bool DeQueue(T&x);
	bool getFront(T&x);
	void makeEmpty();
	bool IsEmpty(){return(front==NULL)?true:false;}
	int getSize();
	friend ostream& operator<<(ostream& os,LinkedQueue<T>& Q)
		{
	os<<"队列中元素个数有"<<Q.getSize()<<endl;
	LinkNode<T> *p=Q.front;int i=0;
	while(p!=NULL)
	{
		os<<++i<<":"<<p->data<<endl;
		p=p->link;
	}
	return os;
}
protected:
	LinkNode<T> *front,*rear;

};
template<class T>
void LinkedQueue<T>::makeEmpty(){
LinkNode<T>*p;
	while(front!=NULL)
	{
		p=front; 
		front=front->link; 
		delete p;
	}
};

template<class T>
bool LinkedQueue<T>::EnQueue(T &x){
	if(front==NULL)
	{
	 front=rear=new LinkNode<T>(x);
	 if(front==NULL)return false;
     }
	else
	{
	 rear->link=new LinkNode<T>(x);
	 if(rear->link==NULL) return false;
	 rear=rear->link;
	}
	return true;
};


template<class T>    
bool LinkedQueue<T>::DeQueue(T &x){
 if(IsEmpty()==true)return false;
 LinkNode<T> *p=front;
 x=front->data;
 front=front->link;delete p;
 return true;
};


template <class T>
bool LinkedQueue<T>::getFront(T &x){
if(IsEmpty()==true)return false;
x=front->data;
return true;
};

template<class T>
int LinkedQueue<T>::getSize()
{
LinkNode<T> *p=front;int k=0;
while(p!=NULL)
{
	p=p->link;
	k++;
}
return k;
};

template<class T,class E>
struct Edge
{
int dest;  //边的另一顶点位置
E cost;    //边上的权值
Edge<T,E> *link;//下一条边链指针
Edge(){}
Edge(int num,E weight):dest(num),cost(weight),link(NULL){}
bool operator!=(Edge<T,E>&R)const{

	return (dest!=R.dest)?true:false;
}
};

template<class T,class E>
struct Vertex{
  T data;
  Edge<T,E> *adj;
};

template<class T,class E>
class Graphlnk
{
friend istream& operator>>(istream& in,Graphlnk<T,E>&G)
{
int i,j,k,n,m;
T e1,e2;
E weight;
cout<<"输入顶点数和边数"<<endl;
in>>n>>m;  //输入顶点数n和边数m
cout<<"输入顶点的数值"<<endl;
for(i=0;i<n;i++)     //建立顶点表数据
{
  in>>e1;
  G.insertVertex(e1);
}
i=0;
cout<<"输入两个顶点，和之间的权值"<<endl;
while(i<m)
{
in>>e1>>e2>>weight;
j=G.getVertexPos(e1);
k=G.getVertexPos(e2);
if(j==-1||k==-1)
{cout<<"边两端点信息有误，重新输入！"<<endl;}
else
{
    G.insertEdge(j,weight);
	   i++;
}
}
return in;
}
friend ostream& operator<<(ostream& out,E>&G)
{
      int i,m;
	  T e1,e2;
	  E w;
	  n=G.numVertices;
	  m=G.numEdges;
	  out<<"有"<<n<<"个顶点"<<","<<m<<"条边"<<endl;
	  for(i=0;i<n;i++)
            for(j=0;j<n;j++)
			{
			  w=G.getWeight(i,j);
			  if(w>0)
			   {
			       e1=G.getValue(i);e2=G.getValue(j);
				   out<<"("<<e1<<","<<e2<<","<<w<<")"<<endl;
			   }
			}
		  return out;
}
public:
	Graphlnk(int sz=DefaultVertices);
	   ~Graphlnk();
	   T getValue(int i)
	   {return(i>=0&&i<numVertices)?NodeTable[i].data:0;}
	   E getWeight(int v1,int v2);  
	   bool insertVertex(const T& vertex);
	   bool removeVertex(int v);
	   bool insertEdge(int v1,int v2,E cost);
	   int getFirstNeighbor(int v);
	   int getNextNeighbor(int v,int w);
	   void BFS();
private:
	int maxVertices;
	int numEdges;
	int numVertices;
	 Vertex<T,E>*NodeTable;
	 int getVertexPos(T vertex)
	 {
	 for(int i=0;i<numVertices;i++)
		 if(NodeTable[i].data==vertex) return i;
	 return -1;
	 }
};
template<class T,class E>
void Graphlnk<T,E>::BFS()
{
int i,w,n=numVertices;
int j=0;
bool *visited=new bool[n];
for(i=0;i<n;i++)visited[i]=false;
int loc=0;


LinkedQueue<int> Q;



for(j=0,loc=0;j<numVertices;loc++,j++)
{           loc=j;
     if(visited[loc]==false)
	 {
             visited[loc]=true;
			 Q.EnQueue(loc);
			 cout<<getValue(loc)<<" ";
	 }
while(!Q.IsEmpty())
{    
	Q.DeQueue(loc);
	w=getFirstNeighbor(loc);
	while(w!=-1)
	{
	if(visited[w]==false)
	{
	cout<<getValue(w)<<" ";
	visited[w]=true;
	Q.EnQueue(w);
	}
	 w=getNextNeighbor(loc,w);
	}
}
}


delete[] visited;
};


template<class T,class E>
Graphlnk<T,E>::Graphlnk(int sz)
{
maxVertices=sz;
numVertices=0;
numEdges=0;
NodeTable=new Vertex<T,E>[maxVertices];  //创建顶点表数组
if(NodeTable==NULL){cerr<<"存储分配错！"<<endl; exit(1);}
for(int i=0;i<maxVertices;i++)
NodeTable[i].adj=NULL;

};

template<class T,E>::~Graphlnk()
{
  for(int i=0;i<numVertices;i++)
  {
  Edge<T,E>*p=NodeTable[i].adj;
  while(p!=NULL)
  {
   NodeTable[i].adj=p->link;
   delete p;
   p=NodeTable[i].adj;
  }
  
  }
  delete[]NodeTable;
};

template<class T,class E>
int Graphlnk<T,E>::getFirstNeighbor(int v)
{
if(v!=-1)
{
   Edge<T,E>*p=NodeTable[v].adj;
   if(p!=NULL) return p->dest;
}
return -1;
};

template<class T,E>::getNextNeighbor(int v,int w)
{
if(v!=-1)
{
 Edge<T,E> *p=NodeTable[v].adj;
 while(p!=NULL&&p->dest!=w)
	 p=p->link;
 if(p!=NULL&&p->link!=NULL)
	 return p->link->dest;
}
return -1;
};

template<class T,class E>
E Graphlnk<T,E>::getWeight(int v1,int v2)
{
if(v1!=-1&&v2!=-1)
{
 Edge<T,E> *p=NodeTable[v1].adj;
 while(p!=NULL&&p->dest!=v2)
	 p=p->link;
 if(p!=NULL)
	 return p->cost;

}
return 0;
};

template<class T,class E>
bool Graphlnk<T,E>::insertVertex(const T&vertex)
{
if(numVertices==maxVertices) return false;
NodeTable[numVertices].data=vertex;
numVertices++;
return true;

};

template<class T,E>::insertEdge(int v1,E weight)
{
if(NodeTable[v1].adj==NULL)
{
Edge<T,E> *newNode=new Edge<T,E>(v2,weight);
newNode->link=NodeTable[v1].adj;
NodeTable[v1].adj=newNode;
numEdges++;
return true;
}
else
{
 Edge<T,E> *q,*p=NodeTable[v1].adj;
   while(p!=NULL)
   {        q=p;
        p=p->link;
		if(p==NULL)
			break;
   }
    Edge<T,E> *newNode2=new Edge<T,weight);
	newNode2->link=q->link;
      q->link=newNode2;
	  numEdges++;
	  return true;
}

};

void main()
{
Graphlnk<char,int> gb(20);
cin>>gb;
cout<<gb;
cout<<"BFS排序结果为"<<endl;
gb.BFS();
}