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

图的邻接矩阵实现问题讨论组成员: ?设计目的通过对图遍历的程序编写,掌握邻接矩阵的定义,并对其进行深度优先搜索和广度优先搜索。? 1. 测试图的手工表示结果。? 2. 测试图的数据表示,邻接矩阵特点。?邻接矩阵,对与图 G,可用一个方阵 A=(a ij) n*n表示,其中 a ij =1,表示 v i和v j之间有边,为 0表示无边。邻接矩阵可表示自环和重边,在有向图中, a ij表示定点 v i和v j之间边的条数。?无向图的邻接矩阵一定是对称的,而有向图的邻接矩阵不一定对称。因此,用邻接矩阵来表示一个具有 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 用于定义图中顶点和边的相关信息。 2017-4-1 源程序: 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); 2017-4-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); 2017-4-1 ? 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); ?}?//广度优先搜索方法 2017-4-1 ? 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]; ? (