初始化图的邻接矩阵表示法,为什么要把边的权值均置为极大值

点击联系发帖人 时间：2021-05-28 01:28

图的邻接矩阵表示法

主题：用图的邻接矩阵表示法实現 DFS(递归) 与 BFS(非递归) 请选择图的类型(a - 无向图 b - 有向图)：a 请输入总顶点数，总边数：8 9 请选择遍历方式(1.深度优先搜索; 2.广度优先搜索)： /* ————图的圖的邻接矩阵表示法存储表示 ————*/ /* 存在则返回 u 在顶点表中的下标；否则返回 -1 */ /* ————采用图的邻接矩阵表示法表示法创建无向网 ————*/ /* 返回顶点v的第一个邻接顶点序号 */ /* 返回顶点v的相对于w的下一个邻接顶点序号 */ /* 广搜,类似于树的层次遍历 */ 主题：用邻接表实现 DFS(递归) 与 BFS(非递归) 請输入顶点数和边数：8 9 请选择遍历方式(1.深度优先搜索; 2.广度优先搜索)：1 ArcNode* firstarc; // 第一个表结点的地址指向第一条依附该顶点的弧的指针 /* 返回顶点u在圖中的位置 */ /* 插入v1的邻接表,为了提高效率，总在表头插入结点 */ /* 插入v2的邻接表,为了提高效率总在表头插入结点 */ /* 遍历每个顶点的邻接表 */ /* 返回顶點v的第一个邻接点序号 */ /* 返回顶点v的相对于w的下一个邻接点序号 */

}

从已给的连通图中某一顶点出发沿着一些边访遍图中所有的顶点，且使每个顶点仅被访问一次就叫做图的遍历，它是图的基本运算

遍历实质：找每个顶点的邻接点嘚过程。

图中可能存在回路且图的任一顶点都可能与其它顶点想通，在访问完某个顶点之后可能会沿着某些边又回到了曾经访问过的顶點

设置辅助数组visited [n],用来标记每个被访问过的顶点初始为0，被访问过就是1

深度优先搜索的遍历类似于树的先序遍历及根左右的方式遍历，圖的深度优先是树的先序遍历的推广

从图的某一结点出发首先一次访问该结点的所有邻接点,再按这些顶点被访问的先后顺序访问与他们楿邻接的所有未被访问的顶点，重复此过程

其实类似于树的顺序遍历。

空间复杂度相同都是O（n）(DFS运用递归，BFS接用队列)
时间复杂度只与存储结构（图的邻接矩阵表示法或邻接表）有关而与搜索路径无关，图的邻接矩阵表示法复杂的为O(n ^ n),邻接表时间复杂读为O(n + e)

}

淘宝游戏网