#include<iostream.h>
#include<stdlib.h>
#include"SqQueue.h"//队列的头文件，肯定没有错误
#define ok 1
#define error 0
typedef int status;
#define max 20// 定义最大顶点个数
#define INFINITY 1000 //定义无穷大
bool visited[max]; //访问标志数组
typedef char VertexType;
typedef struct ArcNode //弧结点的定义,表节点
{
int adjvex;//节点位置
struct ArcNode *nextarc;//下一条弧的指针
}ArcNode;
typedef struct VNode// 顶点结构体定义
{
VertexType data;//节点包含的数据
ArcNode *firstarc;//指向第一条弧的指针
}VNode,AdjList[max];
typedef struct //图的定义
{
AdjList vertices;
int vexnum,arcnum;
int kind;
}ALGraph;
void CreateALG(ALGraph &G)//采用邻接表创建图
{
int i;//变量
cout<<"输入顶点数"<<endl;
cin>>G.vexnum;
cout<<"输入边数"<<endl;
cin>>G.arcnum;
for(i=0;i<G.vexnum;i++)// 输入顶点信息
{
cout<<"请输入第"<<i<<": 个顶点信息--字符形式"<<endl;
cin>>G.vertices[i].data;
G.vertices[i].firstarc=NULL;
}//到词为止创建了一个数组保存节点,个数为G.vexnum
for(i=0;i<G.vexnum;i++)//生成树
{
int index=-1;
ArcNode *r,*p;//r指向当前链表的最后一个表结点；
while(true)
{
cout<<"输入第"<<i<<"个顶点的邻接点下标"<<endl;
cout<<"输入-1表示第i个顶点的单链表结束"<<endl;
cin>>index;
if(index==-1)
break;
else //尾插法建单链表
{
p=(ArcNode *)malloc(sizeof(ArcNode));
p->nextarc=NULL;
p->adjvex=index;
if(G.vertices[i].firstarc==NULL)
r=p;
else
{
r->nextarc=p;
r=r->nextarc;
}
//尾插法建单链表储存弧来建立图
}
}
}
}
int FirstAdjVex(ALGraph G,int v)
{ return (G.vertices[v].firstarc!=NULL)?G.vertices[v].firstarc->adjvex:-1;//查找第v个顶点的第一个临接点所在的下标,若没有则返回-1.
}
int NextAdjVex(ALGraph G,int v,int w)
{ ArcNode *q;
q=G.vertices[v].firstarc;
while(q)
{
if(G.vertices[q->adjvex].data==w)
if(q->nextarc)
return G.vertices[q->nextarc->adjvex].data;
else return -1;
q=q->nextarc;
}
return -1;
} //查找G中第v个顶点的单链表中,值为w的下一个表结点的值,若没有则返回-1.
void DFS(ALGraph G,int v); //DFS函数声明
void DFSTraverse(ALGraph G) //图的深度优先搜索
{
for(int v=0;v<G.vexnum;++v)
visited[v]=false;
for(v=0;v<G.vexnum;++v)
{ if(!visited[v])
{
DFS(G,v);
}
}
}
void DFS(ALGraph G,int v)
{
visited[v]=true;
cout<<G.vertices[v].data<<endl;//输出第v个顶点的数据
for(int w=FirstAdjVex(G,v);w>=0;w=NextAdjVex(G,v,w))
{
if(!visited[w])
DFS(G,w);
}
}
void BFSTraverse(ALGraph G)
{
SqQueue Q;
for(int v=0;v<G.vexnum;v++)
visited[v]=false;
InitQueue(Q);
for(v=0;v<G.vexnum;v++)
{
int u;
if(!visited[v])
{
visited[v]=true;
cout<<G.vertices[v].data<<endl;
EnQueue(Q,v);//将v入队
while(!QueueEmpty(Q))
{
DeQueue(Q,u);//出队一个元素放到u中
for(int w=FirstAdjVex(G,u);w>=0;w=NextAdjVex(G,u,w))
{
if(!visited[w])
{
visited[w]=true;
cout<<G.vertices[w].data<<endl;
EnQueue(Q,w);
}
}
}
}
}
}
void main()
{
ALGraph g;
CreateALG(g);//采用邻接表存储图
cout<<"深度优先遍历图"<<endl;
DFSTraverse(g);//深度优先遍历图
cout<<"广度优先遍历图"<<endl;
BFSTraverse(g);//广度优先遍历图
}
－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－
程序没有语法和调试错误但不能实现所要求的功能
帮偶看一下 是建立图时有错误嘛 thx
