Question

跪求图的建立（用邻接矩阵或邻接表）与图的深度，广度优先搜索程序，一定要能运行的，最好有注释，谢谢

就是先建一个图，再输出你建的图的深度优先搜索，广度优先搜索的序列

Answer 1

//////////////////////////////////////////////////////////////////
//图是通过文件建立的
//数据元素为char类型
//存储结构为邻接表
//文件中第一行为图的类型
//第二行为节点元素，以#结束
//下边每一行为边，和边的权值
//下边是文件的示例
/*
2
A B C D #
A B 3
A C 4
B C 2
C D 4
D A 1
# #
*/
//////////////////////////////////////////////////////////////////
#include<iostream>
#include<fstream>
using namespace std;

const int MaxNum= 20;
const int Infinity=-1;

typedef char VexType;
typedef int ArcType;
typedef struct QNode
//定义队列节点
{
int data;
QNode *next;
}*LQueuePtr;

struct LQueue
//定义队列结构体
{
LQueuePtr front,rear;
};

void QueueInit(LQueue &Q)
//队列初始化
{
Q.front =new QNode;
Q.front ->next =0;
Q.rear =Q.front ;
}

void Enqueue(LQueue &Q,int e)
{
LQueuePtr s;
s=new QNode;
s->data =e;
s->next =0;
Q.rear ->next =s;
Q.rear =s;
}

bool Dequeue(LQueue &Q,int &e)
{
LQueuePtr p;
if(Q.front ==Q.rear ) return false;
p=Q.front ;
Q.front =p->next ;
e=Q.front ->data ;
delete p;
return true;
}

typedef struct ArcNode
//定义边的结构体
{
int adjvex;
ArcType info;
ArcNode *nextarc;
}*ArcPtr;

struct VexNode
//定义节点的结构体
{
VexType data;
ArcPtr firstarc;
};

struct ALGraph
//定义图的结构体
{
VexNode vexs[MaxNum+1];
int kind,vexnum,arcnum;
};

int LocateVex(ALGraph &G,VexType v)
//在图中找到某一个元素
{
int i;
for(i=G.vexnum ;i>0&&G.vexs [i].data !=v;i--);
return i;
}

void CreateGraph(ALGraph &G,char fn[])
//创建图
{
int i,j;
VexType u,v;
ArcPtr p;
ifstream f;
ArcType w;

f.open (fn);

//打开文件失败
if(!f)
{
G.vexnum =0;
return;
}

//读入图的种类
f>>G.kind ;

//先设置边数为0
G.arcnum =0;
i=0;
while(true)
//向节点数组中添加节点
{
f>>u;
if('#'==u) break;
i++;
G.vexs [i].data =u;
G.vexs [i].firstarc =0;
}

G.vexnum =i;
while(true)
//读入各条边
{
f>>u>>v;
if('#'==u||'#'==v) break;
i=LocateVex(G,u);
if(0==i) continue;
j=LocateVex(G,v);
if(0==j||j==i) continue;

if(1==G.kind||3==G.kind )w=1;
else f>>w;

G.arcnum ++;
p=new ArcNode;
p->adjvex =j;
p->info =w;
p->nextarc =G.vexs[i].firstarc ;
G.vexs[i].firstarc =p;
if(G.kind <=2) continue;
p=new ArcNode;
p->adjvex =i;
p->info =w;
p->nextarc =G.vexs[j].firstarc ;
G.vexs[j].firstarc =p;
}
f.close ();
}

void OutputGraph(ALGraph &G)
//输出图
{
int i;
ArcPtr p;
if(0==G.vexnum )
{
cout<<"空图"<<endl;
return ;
}

cout<<"顶点数="<<G.vexnum <<" 弧数="<<G.arcnum <<endl<<"顶点：";
for(i=1;i<=G.vexnum ;i++) cout<<G.vexs [i].data <<' ';

cout<<endl<<"出弧:"<<endl;
for(i=1;i<=G.vexnum ;i++)
{
cout<<"顶点"<<G.vexs [i].data <<endl;
for(p=G.vexs [i].firstarc ;p;p=p->nextarc )
cout<<" <"<<G.vexs [i].data <<","<<G.vexs [p->adjvex ].data <<"> "<<p->info <<endl;
}
}

void visit(VexType x)
{
cout<<x;
}

void DFS(ALGraph &G,int i,bool visited[],void visit(VexType))
//图的名称，当前节点位置，标记数组，访问函数
{
int j;
ArcPtr p;
//访问当前节点
visit(G.vexs [i].data );
//修改标记值
visited[i]=true;
for(p=G.vexs[i].firstarc ;p;p=p->nextarc )
{
j=p->adjvex ;
if(!visited[j])
//对下一个节点递归
DFS(G,j,visited,visit);
}
}
void DFSTraverse(ALGraph &G,void visit(VexType))
{
int i;
bool visited[MaxNum+1];
for(i=1;i<=G.vexnum ;i++)
//初始化标记数组
{
visited[i]=false;
}
for(i=1;i<=G.vexnum ;i++)
{
if(!visited[i])
{
DFS(G,i,visited,visit);
}
}
}

void BFSTraverse(ALGraph &G,void visit(VexType))
{
int u,v,w;
ArcPtr p;
LQueue q;
bool visited[MaxNum+1];

//初始化标记数组
for(v=1;v<=G.vexnum ;v++)
visited[v]=false;

QueueInit(q);

for(v=1;v<=G.vexnum ;v++)
if(!visited[v])
{
//访问节点
visit(G.vexs[v].data );
visited[v]=true;
//将访问的节点入队
Enqueue(q,v);
while(Dequeue(q,u))
//出队并访问
{
for(p=G.vexs[u].firstarc ;p;p=p->nextarc )
{
w=p->adjvex ;
if(!visited[w])
{
visit(G.vexs[w].data );
visited[w]=true;
Enqueue(q,w);
}
}
}
}
}

int main()
{
ALGraph G;
CreateGraph(G,"aaa.txt");
cout<<"创建的图为:";
OutputGraph(G);

cout<<"深度优先遍历："<<endl;
DFSTraverse(G,visit);
cout<<endl<<"广度优先遍历"<<endl;
BFSTraverse(G,visit);
cout<<endl;

return 0;
}