图的邻接矩阵实现问题.ppt

图的邻接矩阵实现问题
第1页，共16页，编辑于2022年，星期五
设计目的
通过对图遍历的程序编写，掌握邻接矩阵的定义，并对其进行深度优先搜索和广度优先搜索。
1. 测试图的手工表示结果。
第2 //广度优先搜索方法
第8页，共16页，编辑于2022年，星期五
static void BFS(Graphm G,int start,char m[],int v1)
{
int v,w;
int vn=v1+1;
int qu[]=new int[vn];
int front,rear;
front=rear=0;
rear++;
qu[rear]=m[start];
(start,1);
while(front!=rear)
{
front=(front+1)%vn;
v=qu[front]-97;
(m[v]+" ");
for(w=(v);w<();w=(v,w))
if((w)==0)
{
(w,1);
qu[++rear]=m[w];
}
}
}
}
第9页，共16页，编辑于2022年，星期五
/**
* 图类
* ***@author Administrator
*
*/
class Graphm{

int numvertex,numedge; //图中顶点的个数numvertex，与边的个数numedge
public int matrix[][]=new int[8][8]; //二维矩阵，用于存储边的信息
int mark[]=new int[8]; //数组，用于存储图中的顶点是否被访问
public Graphm(int numvert) //图的构造函数
{
int i,j;
numvertex=numvert; numedge=0;
第10页，共16页，编辑于2022年，星期五
for(i=0;i<numvertex;i++)
for(j=0;j<numvertex;j++)
matrix[i][j]=0;//赋初值没被访问0
}
int n() //返回图中顶点的个数
{
return numvertex;
}
int e() //返回图中边的个数
{
return numedge;
}
int first(int v) //寻找与顶点v相邻最近的元素
{
int i;
for(i=0;i<numvertex;i++)
{
if(matrix[v][i]!=0)
return i;
}
return i;
}
第11页，共16页，编辑于2022年，星期五
int next(int v1,int v2) //寻找在顶点v2后与顶点v1相邻最近的元素
{
int i;
for(i=v2+1;i<numvertex;i++)
{
if(matrix[v1][i]!=0)
return i;
}
return i;
}
void setedge(int v1,int v2,int wgt) //设置由顶点v1与v2构成的边的权重
{
if(matrix[v1][v2]==0)
numedge++;
matrix[v1][v2]=wgt;
}
void deledge(int v1,int v2) //删除由顶点v1与v2构成的边
第12页，共16页，编辑于2022年，星期五
{
if(matrix[v1][v2]!=0)
numedge--;
matrix[v1][v2]=0;
}
int weight(int v1,int v2) //返回由顶点v1与v2构成的边的权重
{
return matrix[v1][v2];
}
int getmark(int v) //返回顶点v的标识信息
{
return mark[v];
}
void setmark(int v,int val) //设置顶点v的标识信息
{
mark[v]=val;
}
void clear() //