图的遍历
班级：计算机09级网络工程2班 姓名：+++ 学号：0925113018完成日期：2010.12.30
题目：编制一个创建有向图和无向图然后对它们进行遍历的程序。总结陈词
一、需求分析
1、用邻接矩阵和邻接表的形式表示图，创建图。（设计中其中用邻接表表示的图内没有权重，用邻接矩阵表示的图内有权重。）
2、输入图中节点的个数和边的个数，能够打印出用邻接表或邻接矩阵表示的图的储存结构。（设计中其中用邻接表表示的节点的值只能是数字，但用邻接矩阵表示的节点的值可以是字母。）
3、 本程序只求出用邻接矩阵表示的无向图的深度遍历，和用邻接表表示的无向图的深度和广度遍历
4、程序执行命令为：（1）输入图；（2）输出图；（3）输出遍历。
二、概要设计
//邻接矩阵
typedef struct ArcCell{
int adj;
ArcCell *info;
}ArcCell, AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];
typedef struct{
char vexs[MAX_VERTEX_NUM];
AdjMatrix arcs;
int vexnum,arcnum;
}MGraph;
//邻接表
typedef struct ArcNode //定义边结点
{
int adjvex;
ArcNode *nextarc;
}ArcNode;
typedef struct VNode //定义顶点结点
{
char data;
ArcNode *firstarc;
}VNode,AdjList[MAX_VERTEX_NUM];
typedef struct //定义无向图
{
AdjList vertices;
int vexnum,arcnum;
}ALGraph;
牛油果酱
typedef struct node //定义结点
{
char data;
node *next;
}*Link;
typedef struct //定义链表
{
Link head,tail;
int len;
}LinkList;
//关于邻接表图的操作
int InitList(LinkList &L)//构造一个带头结点和尾结点的空的线性链表L
void add(LinkList &L,int e)//在线性链表L的结尾添加一个结点
void Delete(LinkList &L,int &e)//出列，并将出列的元素值用e返回
void ArcAdd(ALGraph &G,int m,int n){//在无向图中添加以m,n为顶点的边
二年级思维导图数学void CreateDG(ALGraph &G){ //创建无向图
void show(ALGraph G) //在屏幕上输入无向图的邻接表存储形式
void VisitFunc(char a) //对无向图的数据进行访问的函数
int FirstAdjVex(ALGraph G,int v)//返回v的第一个邻接顶点。若顶点在G中没有邻接表顶点，则返回“空”。
int NextAdjVex(ALGraph G,int v,int w) //返回v的（相对于w的）下一个邻接顶点。若w是v的最后一个邻接点，则返回“回”。
bool visit[MAX_VERTEX_NUM];
void DFS(ALGraph G,int v)//从第v个顶点出发递归地深度优先遍历图G。
void DFSTraver(ALGraph G)//对图G作深度优先遍历。
void BFSTraver(ALGraph G)//对图G作广度优先遍历。
//关于邻接矩阵的操作
int LocateVex(MGraph G,char v)
int FirstAdjVex(MGraph G,int v)
int NextAdjVex(MGraph G,int v,int w)
void CreatUDG(MGraph &G)//邻接矩阵的无向图的创建
反躬自问void CreatDG(MGraph &G)//有向图邻接矩阵的创建
bool visited[MAX_VERTEX_NUM];
美好的青春void DFS(MGraph G,int v)
void DFSTraver(MGraph G,int v)
void print1(MGraph G)
三、详细设计
//邻接表的创建
void CreateDG(ALGraph &G){ //创建无向图
cout<<"请输入顶点个数和边数：平板太阳能热水器"<<endl;
cin>>G.vexnum>>G.arcnum;
cout<<"请输入顶点值:"<<endl;
for(int i=1;i<=G.vexnum;i++) {
char t;
cin>>t;
G.vertices[i].data=t;
G.vertices[i].firstarc=NULL;龙珠图片
}
int m,n;
for(int k=1;k<=G.arcnum;k++){
cout<<"请输入第"<<k<<"条边的两个顶点:"<<endl;
cin>>m>>n;
if(m<=G.vexnum&&n<=G.vexnum&&m>0&&n>0){
ArcAdd(G,m,n);
ArcAdd(G,n,m);
}
el cout<<"ERROR."<<endl;
}
}
//在屏幕上输入无向图的邻接表存储形式
void show(ALGraph G)
{
cout<<"无向图的创建完成,该图的邻接表表示为:"<<endl;
ArcNode *p;
for(int i=1;i<=G.vexnum;i++)
{
if(G.vertices[i].firstarc==NULL)
cout<<i<<G.vertices[i].data<<"-->NULL"<<endl;
el
{
p=G.vertices[i].firstarc;
cout<<i<<G.vertices[i].data<<"-->";
while(p->nextarc!=NULL)
{
cout<<p->adjvex<<"-->";
p=p->nextarc;
}
cout<<p->adjvex<<"-->NULL"<<endl;
}
}
}
void DFSTraver(ALGraph G)//对图G作深度优先遍历。
{
cout<<"深度优先搜索的结果为:"<<endl;
for(int v=1;v<=G.vexnum;v++)
visit[v]=fal;
for(int m=1;m<=G.vexnum;m++)
if(!visit[m])
DFS(G,m);
cout<<endl;
}
void BFSTraver(ALGraph G)//对图G作广度优先遍历。
{
cout<<"广度优先搜索的结果为:"<<endl;
LinkList Q;
int u;
for(int m=1;m<=G.vexnum;m++)
visit[m]=fal;
InitList(Q);//借助辅助队列。
for(int v=1;v<=G.vexnum;v++)
if(!visit[v])
{
visit[v]=true;
VisitFunc(G.vertices[v].data);
add(Q,v);
while(Q.len!=0)
{
Delete(Q,u);
for(int w=FirstAdjVex(G,u);w>=1;w=NextAdjVex(G,u,w))
if(!visit[w])
{
visit[w]=true;
VisitFunc(G.vertices[w].data);
add(Q,w);
}
}
}
cout<<endl;
}
void CreatUDG(MGraph &G){//邻接矩阵的无向图的创建
int i,j,k,w;
char v1,v2;
cout<<"请输入顶点个数和边数:"<<endl;mc喊麦
cin>>G.vexnum>>G.arcnum;
cout<<"请输入"<<G.vexnum<<"个顶点的值:"<<endl;
for(i=0;i<G.vexnum;++i) cin>>G.vexs[i];
for(i=0;i<G.vexnum;++i)
for(j=0;j<G.vexnum;++j) {
G.arcs[i][j].adj=0;
G.arcs[i][j].info=NULL;
}
for( k=1;k<=G.arcnum;++k){
cout<<"请输入第"<<k<<"条边的两个顶点值和它们的权重："<<endl;
cin>>v1>>v2>>w;
i=LocateVex(G,v1); j=LocateVex(G,v2);
G.arcs[i][j].adj=w;
G.arcs[j][i]=G.arcs[i][j];
}
}
void DFSTraver(MGraph G,int v){//对邻接矩阵图的递归深度遍历
visited[v]=true;
cout<<G.vexs[v]<<" ";
for(int w=FirstAdjVex(G,v);w>=0;w=NextAdjVex(G,v,w))//>=
if(!visited[w]) DFSTraver(G,w);
}
四、调试分析
在写邻接矩阵的NextAdjVex功能的时候，i从w开始，但是遍历到一半就停止了，后来发现第W个已经遍历过了，所以一直在循环遍历第W个，所以改成w+1。
在写邻接矩阵无向图的深度优先遍历时，
for(int w=FirstAdjVex(G,v);w>=0;w=NextAdjVex(G,v,w))这一句中的W>=0本来少了个等于号，后来发现遍历的时候又停了，因为NextAdjVex中的return 0,此时当w等于0时，循环终止，因此遍历未完成，所以在后面加上等于号。
