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

设计目的
通过对图遍历的程序编写,掌握邻接矩阵的定义,并对其进行深度优先搜索和广度优先搜索。
1. 测试图的手工表示结果。
2. 测试图的数据表示,邻接矩阵特点。
邻接矩阵,对与图G,可用一个方阵A=(aij)n*n表示,其中aij=1,表示vi和vj之间有边,为0表示无边。邻接矩阵可表示自环和重边,在有向图中,aij表示定点vi和vj之间边的条数。
无向图的邻接矩阵一定是对称的,而有向图的邻接矩阵不一定对称。因此,用邻接矩阵来表示一个具有n个顶点的有向图时需要n^2个单元来存储邻接矩阵;对有n个顶点的无向图则只存入上(下)三角阵中剔除了左上右下对角线上的0元素后剩余的元素,故只需1+2+...+(n-1)=n(n-1)/2个单元。
无向图邻接矩阵的第i行(或第i列)非零元素的个数正好是第i个顶点的度。
有向图邻接矩阵中第i行非零元素的个数为第i个顶点的出度,第i列非零元素的个数为第i个顶点的入度,第i个顶点的度为第i行与第i列非零元素个数之和。
用邻接矩阵表示图,很容易确定图中任意两个顶点是否有边相连。
3. 图的类设计方法。
对于深度优先搜索我们采用递归操作;广度优先搜索采用非递归操作,在此过程中引用栈消除递归。
类DFS用于深度优先搜索,栈g1为其边赋值。
类BFS用于广度优先搜索,栈g2为其边赋值。
图类Graphm用于定义图中顶点和边的相关信息。
源程序:
public class BFS {
/**
* ***@param args
*/
public static void main(String[] args) {
// TODO Auto-generated method stub
char m[]={'a','b','c','d','e','f','g','h'};
Graphm g1=new Graphm(8);
//给图的边赋值
(0, 1, 1);
(1, 3, 1);
(1, 4, 1);
(3, 7, 1);
(4, 7, 1);
(0, 2, 1);
(2, 5, 1);
(2, 6, 1);
(5, 6, 1);
//深度优先搜索方法
// ("深度优先输出:");
// DFS(g1,0,m);
// ();
//
// Graphm g2=new Graphm(8);
// //给图的边赋值
// (0, 1, 1);
// (1, 3, 1);
// (1, 4, 1);
// (3, 7, 1);
// (4, 7, 1);
// (0, 2, 1);
// (2, 5, 1);
// (2, 6, 1);
// (5, 6, 1);
// ("广度度优先输出:");
// BFS(g2,0,m,8);
for(int i=0;i<8;i++){
for(int j=0;j<8;j++){
([i][j]+" ");
}
();
}
}
//深度优先搜索方法
static void DFS(Graphm G,int v,char m[])
{
(m[v]+" ");
(v,1);
for(int w=(v);w<();w=(v,w))
if((w)==0)
DFS(G,w,m);
}
//广度优先搜索方法
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(