利用邻接矩阵进行的深度优先和广度优先遍历（含全部代码+图解） |
您所在的位置：网站首页 › 邻接矩阵的用途不包括 › 利用邻接矩阵进行的深度优先和广度优先遍历（含全部代码+图解） |
利用邻接矩阵进行的深度优先和广度优先遍历（含全部代码+图解）
|
目录 --------------------------------------目录------------------------------------------ 图的定义和术语 图的邻接矩阵构建法 深度优先遍历算法（DFS） 广度优先遍历算法 （BFS） 全部代码 图的定义和术语图：G = （V,E) V:顶点的有穷非空集合 E:边的有穷集合 无向图：每条边都是无向的 有向图：每条边都是有方向的 邻接：有边相连的两个顶点之间的关系
想要构建图，则首先得知道图的存储结构，从上图可以看出，我们需要有个数组存储各个顶点的数据，如v1、v2、v3等等。。再者因为我们今天要用邻接矩阵来表示图，所以我们需要个二维数组，再为了方便，我们需要再设两个变量，表示现有的结点与边，可以不难看出是个结构体结构，如下图： #define MVNUM 100 //最大顶点数 typedef struct { char vexs[MVNUM]; //顶点数据数组 int arr[MVNUM][MVNUM]; //邻接矩阵 int vexnum, arcnum; //现有顶点数与边数 }AMGraph;假设我们现在顶点数为5个，边数为5，顶点数据为 a,b,c,d,e，矩阵元素都为无穷，并定义个结构体变量则结构表示出来为：
存储结构知道后，我们就可以对它进行初始化操作啦，而我们的初始化操作，就是对照上图，其中数字，数据都是随机的，根据你的喜好，并且你还可以美化它，这里不多赘述，下面为思想： 1、确定顶点数和边数， 2、给顶点表赋值 3、arr二维数组都初始化为极大值（这里的极大值一般为int的最大值32767，而上图为了美观写成∞）表示现在每个顶点之间都没有线（关系），我们接下来构造就是加线操作而已。 #define MAXINT 32767 //极大值相当于无穷大 int initGraph(AMGraph& G) { cout G.vexnum >> G.arcnum; //输入你想要的顶点数和边数 cout G.vexs[i]; //输入顶点数据 } for (int i = 0; i < G.vexnum; i++) { for (int j = 0; j < G.vexnum; j++) { G.arr[i][j] = MAXINT; //邻接矩阵的初值都为无穷大 } } return 1; }初始化完成后，我们就可以，看看自己邻接矩阵长什么样啦，写一个遍历二维数组的算法（比较简单，这里就不写了），而后就是构造顶点之间的联系，思想就是： 1、先输入两个点（这两个点是邻接的，就是有关系的），并赋予权值， 2、用这两个点去顶点表里去找，找到了返回对应坐标 3、找到坐标后就在矩阵（二维数组）对应下标赋值 4、因为为无向图，则为对称的，所以行列坐标对换后再赋值一遍即可（如为有向图这步省略） int locateVex(AMGraph G, char u) { for (int i = 0; i < G.vexnum; i++) { if (u == G.vexs[i]) //如果u的值和顶点数据匹配，就返回顶点在矩阵中的下标 return i; } return -1; } int createGraph(AMGraph& G) { int i = 0; int j = 0;int w = 0; //i,j代表顶点下标,w代表权值 char v1 = 0; char v2 = 0; //v1,v2为顶点数据 cout v1 >> v2 >> w; i = locateVex(G, v1); //找到v1在顶点表的下标，并返回赋值给i j = locateVex(G, v2); //找到v2在顶点表的下标，并返回赋值给j G.arr[i][j] = w; G.arr[j][i] = G.arr[i][j]; //无向图的矩阵是对称矩阵 } cout |
【本文地址】
今日新闻 |
推荐新闻 |