///////////////////////////
// //
// 图数据结构 graph.h //
// //
//////////////////////////
#include<iostream.h>
#include"Queue.h"
template<class NameType,class DisType>class Graph;
template<class NameType,class DisType> struct Node
{
friend class Graph<NameType,DisType>;
int num;
DisType val;
Node<NameType,DisType> *next;
};
template<class NameType,class DisType> struct GpNode
{
friend class Graph<NameType,DisType>;
NameType data;
Node<NameType,DisType> *link;
};
template<class NameType,class DisType>
class Graph
{
public:
void Creat(); //创建图
void PrintNode(); //打印图中的各个数据项
void DFS(); //图的深度优先搜索,主过程
void DFS(int v,int visited[]); // 子过程
void BFS(); //图的广度优先搜索，主过程
void BFS(int v,int visited[]); //子过程
void ShortPath(); //求最短路径
private:
GpNode<NameType,DisType> *table;
Node<NameType,DisType> *p;
int NumNode; //节点个数
};
template<class NameType,class DisType>
void Graph<NameType,DisType>::Creat()
{
do
{
cout<<"请输入节点个数: ";
cin >> NumNode;
}while(NumNode<=0);
table=new GpNode<NameType,DisType>[NumNode];
cout<<"请输入各节点数据项"<<endl;
for(int i=0;i<NumNode;i++)
{
cin>>table.data;
table.link=NULL;
}
cout<<"请输入各边的关系 (如: A B)"<<endl;
i=1;
NameType nodeA,nodeB;
bool findA,findB;
char ISExit;
int m,n;
do
{
findA=findB=false;
cout<<"请输入第"<<i<<"对边的关系"<<endl;
cin>>nodeA>>nodeB;
for(m=0,n=0;m<NumNode&&n<NumNode&&!(findA & findB);) //查找边的节点
{
if(nodeA!=table[m].data)
m++;
else
findA=true;
if(nodeB!=table[n].data)
n++;
else
findB=true;
}
if(!(findA & findB))
cout<<"输入的节点数据项有错误"<<endl;
else
{
p=new Node<NameType,DisType>;
p->next=table[m].link;
p->num=n;
table[m].link=p;
cout<<"请输入该对边的权值: ";
cin>>p->val;
i++;
}
cout<<"是否继续输入: y)继续,X)任意键退出 ";
cin>>ISExit;
if(ISExit!='y'&&ISExit!='Y')
break;
}while(true);
}
template<class NameType,class DisType>
void Graph<NameType,DisType>::PrintNode()
{
cout<<"图中各节点数据项 : ";
for(int i=0;i<NumNode;i++)
cout<<table.data<<" ";
cout<<endl;
}
template<class NameType,class DisType>
void Graph<NameType,DisType>::DFS()
{
int *visited=new int[NumNode];
cout<<"图的深度优先搜索 : ";
for(int i=0;i<NumNode;i++)
visited=0;
for(i=1;i<NumNode;i++) //遍厉孤立节点
DFS(i,visited);
delete []visited;
cout<<endl;
}
template<class NameType,class DisType>
void Graph<NameType,DisType>::DFS(int v,int visited[])
{
Node<NameType,DisType> *t;
if(visited[v]==0)
cout<<table[v].data<<" ";
visited[v]=1;
t=table[v].link;
while(t!=NULL)
{
if(visited[t->num]==0)
DFS(t->num,visited);
t=t->next;
}
}
template<class NameType,class DisType>
void Graph<NameType,DisType>::BFS()
{
int *visited=new int[NumNode];
cout<<"图的广度优先搜索 : ";
for(int i=0;i<NumNode;i++)
visited=0;
for( i=0;i<NumNode;i++)
BFS(i,visited);
}
template<class NameType,class DisType>
void Graph<NameType,DisType>::BFS(int v,int visited[])
{
Queue<int> q;
int n;
if(visited[v]==0)
{
visited[v]=1;
cout<<table[v].data<<" ";
q.EnQueue(v);
while(!q.ISEmpty())
{
n=q.DelQueue();
p=table[n].link;
while(p!=NULL)
{
n=p->num;
if(visited[n]==0)
{
cout<<table[n].data<<" ";
visited[n]=1;
}
p=p->next;
}
}
}
}