邻接表表示，广度优先搜索，敲了老半天，最后还是用舍友的了。实在找不到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();
}运行截图：
