深度优先遍历(邻接矩阵)

解释结构模型邻接矩阵结构模型（Structural Model）是指在软件工程中，用于描述系统的静态结构的一种模型。

它通常用于表示系统的组件、类、对象之间的静态关系以及它们的属性和行为。

结构模型可以帮助开发人员理解系统的组成部分以及它们之间的相互关系，从而更好地设计、开发和维护软件系统。

在结构模型中，最常用的表示方法是邻接矩阵（Adjacency Matrix）。

邻接矩阵是一种用来表示图形结构的矩阵。

图形结构是由节点和连接节点的边组成的。

邻接矩阵的行和列分别对应图的节点，矩阵中的元素表示节点之间是否存在边。

如果两个节点之间存在边，则对应矩阵元素的值为1；如果两个节点之间不存在边，则对应矩阵元素的值为0。

邻接矩阵可以提供关于图形结构的丰富信息。

通过分析矩阵的行和列，可以确定图中节点的数量、节点之间的连接关系、节点的度等。

邻接矩阵还可以用于进行图的遍历和算法，如深度优先（DFS）和广度优先（BFS）。

此外，邻接矩阵还可以用于解决一些图形相关的优化问题，如最短路径问题和最小生成树问题。

邻接矩阵在实际应用中有广泛的用途。

例如，在社交网络分析中，可以使用邻接矩阵来表示用户之间的关系，并通过矩阵的运算来发现社交网络中的社群结构。

在路由器和互联网中，邻接矩阵可以用来描述网络节点之间的物理连接，从而实现路由表的生成和更新。

邻接矩阵还可以用于解决诸如稀疏矩阵压缩和图形聚类等问题。

然而，邻接矩阵也存在着一些限制和不足之处。

首先，矩阵的大小由节点的数量决定，对于大型图形结构，矩阵会占用大量的内存空间。

其次，对于稀疏图，即节点之间的连接较少的情况，邻接矩阵会浪费大量的空间来表示不存在的边，从而造成存储的浪费。

此外，邻接矩阵在表示稀疏图时的运算效率较低，不适用于一些复杂的图形分析算法。

为了克服邻接矩阵的不足，还有其他的表示图形结构的方法，如邻接表（Adjacency List）和邻接多重表（Adjacency Multilist）。

深度优先算法和广度优先算法都是图搜索中常见的算法，它们具有不同的特点和适用场景。

在进行全面评估之前，让我们先来了解一下深度优先算法和广度优先算法的基本概念和原理。

### 1. 深度优先算法（Depth-First Search, DFS）深度优先算法是一种用于遍历或搜索树或图的算法。

其核心思想是从起始顶点出发，沿着一条路径直到末端，然后回溯，继续搜索下一条路径，直到所有路径都被探索。

在实际应用中，深度优先算法常常通过递归或栈来实现。

### 2. 广度优先算法（Breadth-First Search, BFS）广度优先算法也是一种用于遍历或搜索树或图的算法。

其核心思想是从起始顶点出发，依次遍历该顶点的所有相邻顶点，然后再以这些相邻顶点作为起点，继续遍历它们的相邻顶点，以此类推，直到所有顶点都被遍历。

在实际应用中，广度优先算法通常通过队列来实现。

### 3. 深度优先算法和广度优先算法的时间复杂度在实际应用中，我们经常需要对算法的时间复杂度进行分析。

针对深度优先算法和广度优先算法，它们的时间复杂度并不相同。

- 深度优先算法的时间复杂度：O(V + E)，其中V为顶点数，E为边数。

在最坏的情况下，如果采用邻接矩阵来表示图的话，深度优先算法的时间复杂度为O(V^2)；如果采用邻接表来表示图的话，时间复杂度为O(V + E)。

- 广度优先算法的时间复杂度：O(V + E)，其中V为顶点数，E为边数。

无论采用邻接矩阵还是邻接表表示图，广度优先算法的时间复杂度都是O(V + E)。

### 4. 个人理解和观点在实际应用中，我们在选择使用深度优先算法还是广度优先算法时，需要根据具体的问题场景来进行选择。

如果要寻找图中的一条路径，或者判断两个节点之间是否存在路径，通常会选择使用深度优先算法；如果要寻找最短路径或者进行层次遍历，通常会选择使用广度优先算法。

深度优先算法和广度优先算法都是非常重要的图搜索算法，它们各自适用于不同的场景，并且具有不同的时间复杂度。

深度优先遍历算法实现及复杂度分析深度优先遍历算法（Depth First Search, DFS）是一种常用的图遍历算法，用于查找或遍历图的节点。

本文将介绍深度优先遍历算法的实现方法，并进行对应的复杂度分析。

一、算法实现深度优先遍历算法的基本思想是从图的某个节点出发，沿着深度方向依次访问其相邻节点，直到无法继续下去，然后返回上一层节点继续遍历。

下面是深度优先遍历算法的伪代码：```1. 初始化访问标记数组visited[]，将所有节点的访问标记置为false。

2. 从某个节点v开始遍历：- 标记节点v为已访问（visited[v] = true）。

- 访问节点v的相邻节点：- 若相邻节点w未被访问，则递归调用深度优先遍历算法（DFS(w)）。

3. 遍历结束，所有节点都已访问。

```二、复杂度分析1. 时间复杂度深度优先遍历算法的时间复杂度取决于图的存储方式和规模。

假设图的节点数为V，边数为E。

- 邻接表存储方式：对于每个节点，需要访问其相邻节点。

因此，算法的时间复杂度为O(V+E)。

- 邻接矩阵存储方式：需要检查每个节点与其他节点的连通关系，即需要遍历整个邻接矩阵。

因此，算法的时间复杂度为O(V^2)。

2. 空间复杂度深度优先遍历算法使用了一个辅助的访问标记数组visited[]来记录每个节点的访问状态。

假设图的节点数为V。

- 邻接表存储方式：访问标记数组visited[]的空间复杂度为O(V)。

- 邻接矩阵存储方式：访问标记数组visited[]的空间复杂度同样为O(V)。

综上所述，深度优先遍历算法的时间复杂度为O(V+E)，空间复杂度为O(V)。

三、应用场景深度优先遍历算法在图的遍历和搜索问题中广泛应用。

以下是一些典型的应用场景：1. 连通性问题：判断图中两个节点之间是否存在路径。

2. 非连通图遍历：对于非连通图，深度优先遍历算法可以用于遍历所有连通分量。

3. 寻找路径：在图中寻找从起始节点到目标节点的路径。

《数据结构课程设计》报告题目：深度与广度优先搜索--迷宫问题专业计算机科学与技术学生姓名李柏班级B计算机115学号1110704512指导教师巩永旺完成日期2013年1月11日目录1简介 (1)2算法说明 (1)3测试结果 (3)4分析与探讨 (7)5小结 (9)附录 (10)附录1 源程序清单 (10)迷宫问题1 简介1、图的存储结构图的存储结构又称图的表示，其最常用的方法是邻接矩阵和邻接表。

无论采用什么存储方式，其目标总是相同的，既不仅要存储图中各个顶点的信息，同时还要存储顶点之间的所有关系。

2、图的遍历图的遍历就是从指定的某个顶点（称其为初始点）出发，按照一定的搜索方法对图中的所有顶点各做一次访问过程。

根据搜索方法不同，遍历一般分为深度优先搜索遍历和广度优先搜索遍历。

本实验中用到的是广度优先搜索遍历。

即首先访问初始点v i，并将其标记为已访问过，接着访问v i的所有未被访问过的邻接点，顺序任意，并均标记为已访问过，以此类推，直到图中所有和初始点v i有路径相通的顶点都被访问过为止。

鉴于广度优先搜索是将所有路径同时按照顺序遍历，直到遍历出迷宫出口，生成的路径为最短路径。

因此我们采用了广度优先搜索。

无论是深度优先搜索还是广度优先搜索，其本质都是将图的二维顶点结构线性化的过程，并将当前顶点相邻的未被访问的顶点作为下一个顶点。

广度优先搜索采用队列作为数据结构。

本实验的目的是设计一个程序，实现手动或者自动生成一个n×m矩阵的迷宫，寻找一条从入口点到出口点的通路。

具体实验内容如下：选择手动或者自动生成一个n×m的迷宫，将迷宫的左上角作入口，右下角作出口，设“0”为通路，“1”为墙，即无法穿越。

假设一只老鼠从起点出发，目的为右下角终点，可向“上、下、左、右、左上、左下、右上、右下”8个方向行走。

如果迷宫可以走通，则用“■”代表“1”，用“□”代表“0”，用“☆”代表行走迷宫的路径。

输出迷宫原型图、迷宫路线图以及迷宫行走路径。

邻接矩阵的深度优先遍历算法简介邻接矩阵是一种常用的图表示方法，它使用一个二维数组来表示图中各个节点之间的关系。

深度优先遍历（Depth First Search，DFS）是一种常用的图遍历算法，它通过递归或栈的方式依次访问图中的所有节点。

本文将介绍邻接矩阵的深度优先遍历算法，并提供相应的代码实现。

邻接矩阵邻接矩阵是一种二维数组，它的行和列分别代表图中的各个节点。

如果两个节点之间存在边，则对应位置上的元素为1；否则为0。

对于无向图来说，邻接矩阵是对称的；而对于有向图来说，邻接矩阵不一定对称。

下面是一个示例的邻接矩阵：A B C DA 0 1 0 1B 1 0 1 1C 0 1 0 0D 1 1 0 0深度优先遍历算法算法思想深度优先遍历算法从起始节点开始，递归或使用栈的方式依次访问与当前节点相邻的未访问过的节点，直到所有节点都被访问过为止。

算法步骤1.创建一个栈，并将起始节点入栈；2.创建一个数组，用于记录已经访问过的节点；3.当栈不为空时，执行以下操作：–从栈顶弹出一个节点，标记为已访问，并输出该节点；–遍历该节点的邻居节点，如果邻居节点未被访问，则将其入栈；4.重复步骤3，直到栈为空。

算法实现def dfs(adj_matrix, start_node):stack = [start_node]visited = [False] * len(adj_matrix)while stack:node = stack.pop()visited[node] = Trueprint(node)for i in range(len(adj_matrix)):if adj_matrix[node][i] == 1 and not visited[i]:stack.append(i)示例假设有以下图的邻接矩阵：A B C DA 0 1 0 1B 1 0 1 1C 0 1 0 0D 1 1 0我们以A作为起始节点进行深度优先遍历，那么遍历的顺序将会是A、B、C、D。

算法设计：深度优先遍历和广度优先遍历实现深度优先遍历过程1、图的遍历和树的遍历类似，图的遍历也是从某个顶点出发，沿着某条搜索路径对图中每个顶点各做一次且仅做一次访问。

它是许多图的算法的基础。

深度优先遍历和广度优先遍历是最为重要的两种遍历图的方法。

它们对无向图和有向图均适用。

注意：以下假定遍历过程中访问顶点的操作是简单地输出顶点。

2、布尔向量visited[0．．n-1]的设置图中任一顶点都可能和其它顶点相邻接。

在访问了某顶点之后，又可能顺着某条回路又回到了该顶点。

为了避免重复访问同一个顶点，必须记住每个已访问的顶点。

为此，可设一布尔向量visited[0．．n-1]，其初值为假，一旦访问了顶点Vi之后，便将visited[i]置为真。

--------------------------深度优先遍历(Depth-First Traversal)1．图的深度优先遍历的递归定义假设给定图G的初态是所有顶点均未曾访问过。

在G中任选一顶点v为初始出发点(源点)，则深度优先遍历可定义如下：首先访问出发点v，并将其标记为已访问过；然后依次从v出发搜索v的每个邻接点w。

若w未曾访问过，则以w为新的出发点继续进行深度优先遍历，直至图中所有和源点v有路径相通的顶点(亦称为从源点可达的顶点)均已被访问为止。

若此时图中仍有未访问的顶点，则另选一个尚未访问的顶点作为新的源点重复上述过程，直至图中所有顶点均已被访问为止。

图的深度优先遍历类似于树的前序遍历。

采用的搜索方法的特点是尽可能先对纵深方向进行搜索。

这种搜索方法称为深度优先搜索(Depth-First Search)。

相应地，用此方法遍历图就很自然地称之为图的深度优先遍历。

2、深度优先搜索的过程设x是当前被访问顶点，在对x做过访问标记后，选择一条从x出发的未检测过的边(x，y)。

若发现顶点y已访问过，则重新选择另一条从x出发的未检测过的边，否则沿边(x，y)到达未曾访问过的y，对y访问并将其标记为已访问过；然后从y开始搜索，直到搜索完从y出发的所有路径，即访问完所有从y出发可达的顶点之后，才回溯到顶点x，并且再选择一条从x出发的未检测过的边。

邻接矩阵的实验原理及应用实验原理邻接矩阵是一种图的表示方法，通过矩阵的形式记录图中各个顶点之间的连接关系。

邻接矩阵可以用于描述有向图和无向图。

无向图的邻接矩阵无向图的邻接矩阵是一个方阵，其中的每个元素表示图中两个顶点之间是否存在边。

如果顶点i和顶点j之间存在边，则邻接矩阵的第i行第j列和第j行第i列的元素值都为1；否则，为0。

邻接矩阵的对角线上的元素表示各个顶点的度数。

有向图的邻接矩阵有向图的邻接矩阵同样是一个方阵，其中的每个元素表示从顶点i到顶点j是否存在边。

如果顶点i到顶点j存在边，则邻接矩阵的第i行第j列的元素值为1；否则，为0。

邻接矩阵的表示方法邻接矩阵可以用二维数组来表示，数组的大小为n×n，其中n为图中顶点的个数。

数组的下标表示顶点的编号，而数组中的元素表示邻接关系。

应用邻接矩阵在图的算法和应用领域有重要的应用。

图的遍历使用邻接矩阵可以进行图的遍历操作，包括深度优先遍历和广度优先遍历。

通过对邻接矩阵的遍历，可以访问图中所有的顶点和边。

最短路径算法邻接矩阵可以作为最短路径算法的基本数据结构。

通过邻接矩阵，可以方便地计算两个顶点之间的最短路径。

最小生成树算法最小生成树算法可以使用邻接矩阵作为数据结构。

通过构建邻接矩阵，并使用Prim算法或Kruskal算法，可以生成图的最小生成树。

图的连通性判断邻接矩阵可以用来判断图的连通性。

通过对邻接矩阵进行深度优先搜索或广度优先搜索，可以确定图中的连通分量。

图的可达性分析邻接矩阵可以用于分析图中顶点之间的可达性。

通过对邻接矩阵进行矩阵运算，可以得到图中任意两个顶点之间的可达性。

总结邻接矩阵是一种表示图的方法，通过矩阵的形式记录图中各个顶点之间的连接关系。

邻接矩阵具有简单、直观、易于操作等优点，在图的算法和应用中有广泛的应用。

通过对邻接矩阵的遍历、最短路径算法、最小生成树算法、连通性判断和可达性分析等操作，可以解决各种与图相关的问题。

以上就是邻接矩阵的实验原理及应用，希望对你有所帮助。

浅析深度优先和⼴度优先遍历实现过程、区别及使⽤场景⼀、什么是深度/⼴度优先遍历？ 深度优先遍历简称DFS（Depth First Search），⼴度优先遍历简称BFS（Breadth First Search），它们是遍历图当中所有顶点的两种⽅式。

这两种遍历⽅式有什么不同呢？我们来举个栗⼦： 我们来到⼀个游乐场，游乐场⾥有11个景点。

我们从景点0开始，要玩遍游乐场的所有景点，可以有什么样的游玩次序呢？1、深度优先遍历 第⼀种是⼀头扎到底的玩法。

我们选择⼀条⽀路，尽可能不断地深⼊，如果遇到死路就往回退，回退过程中如果遇到没探索过的⽀路，就进⼊该⽀路继续深⼊。

在图中，我们⾸先选择景点1的这条路，继续深⼊到景点7、景点8，终于发现⾛不动了： 于是，我们退回到景点7，然后探索景点10，⼜⾛到了死胡同。

于是，退回到景点1，探索景点9： 按照这个思路，我们再退回到景点0，后续依次探索景点2、3、5、4、发现相邻的都玩过了，再回退到3，再接着玩6，终于玩遍了整个游乐场： 具体次序如下图，景点旁边的数字代表探索次序。

当然还可以有别的排法。

像这样先深⼊探索，⾛到头再回退寻找其他出路的遍历⽅式，就叫做深度优先遍历（DFS）。

这⽅式看起来很像⼆叉树的前序遍历。

没错，其实⼆叉树的前序、中序、后序遍历，本质上也可以认为是深度优先遍历。

2、⼴度优先遍历 除了像深度优先遍历这样⼀头扎到底的玩法以外，我们还有另⼀种玩法：⾸先把起点相邻的⼏个景点玩遍，然后去玩距离起点稍远⼀些（隔⼀层）的景点，然后再去玩距离起点更远⼀些（隔两层）的景点… 在图中，我们⾸先探索景点0的相邻景点1、2、3、4： 接着，我们探索与景点0相隔⼀层的景点7、9、5、6： 最后，我们探索与景点0相隔两层的景点8、10： 像这样⼀层⼀层由内⽽外的遍历⽅式，就叫做⼴度优先遍历（BFS）。

这⽅式看起来很像⼆叉树的层序遍历。

没错，其实⼆叉树的层序遍历，本质上也可以认为是⼴度优先遍历。

邻接矩阵的深度优先遍历算法简介邻接矩阵是一种常见的图存储结构，它使用二维数组来表示图中各个顶点之间的关系。

而深度优先遍历算法是一种常用的图遍历算法，用于遍历和搜索图的各个顶点。

本文将介绍邻接矩阵的深度优先遍历算法，包括其基本思想、实现步骤以及应用场景等内容。

基本思想深度优先遍历算法（Depth-First Search，DFS）是一种针对图和树的遍历算法，它通过从起始顶点开始，逐个探索图中的顶点，并沿着某一条路径一直深入，直到无法继续为止，然后回溯到前一顶点继续探索其它路径，直到所有顶点都被访问过为止。

邻接矩阵是一种常见的图表示方法，它通过一个二维数组来表示图中各个顶点之间的关系。

邻接矩阵中的每个元素表示两个顶点之间是否存在一条边，具体而言，如果顶点i和顶点j之间存在一条边，则邻接矩阵中下标为(i, j)和(j, i)的元素值为1；否则，它们的元素值为0。

邻接矩阵的深度优先遍历算法是通过对邻接矩阵进行遍历，找出与起始顶点相连接的顶点，并依次对这些顶点进行深度优先遍历。

实现步骤邻接矩阵的深度优先遍历算法可以使用递归或迭代的方式来实现。

下面分别介绍这两种实现方法的具体步骤。

递归实现1.创建一个数组visited，用来记录每个顶点是否已被访问过，初始时所有元素都设为0。

2.选择一个起始顶点v，并将visited[v]设置为1，表示该顶点已被访问过。

3.遍历邻接矩阵中与v相连的所有顶点w，如果visited[w]为0，则递归调用深度优先遍历函数，将w作为新的起始顶点。

4.重复步骤3，直到所有顶点都被访问过为止。

迭代实现1.创建一个数组visited，用来记录每个顶点是否已被访问过，初始时所有元素都设为0。

2.创建一个栈，用来存储待访问的顶点。

3.选择一个起始顶点v，并将visited[v]设置为1，表示该顶点已被访问过。

4.将v入栈。

5.当栈不为空时，执行以下操作：–出栈一个顶点u，访问它。

–遍历邻接矩阵中与u相连的所有顶点w，如果visited[w]为0，则将w入栈，并将visited[w]设置为1。

基于栈的非递归深度优先遍历算法设计与实现作者：李光杰王聪来源：《电脑知识与技术》2014年第03期摘要：深度优先遍历是图的一种重要遍历方法，该文主要介绍在邻接矩阵存储方式下，利用栈实现对稠密图进行深度优先非递归遍历的算法设计及实现过程。

关键词：深度优先；算法；非递归；栈中图分类号：TP311 文献标识码：A 文章编号：1009-3044（2014）03-0470-03图是一种重要的数据结构，在实际生活中应用非常广泛，如计算机网络、电力网络、交通信号网路等。

图可分为有向图，无向图，连通图，非联通图，稠密图，稀疏图等，该文仅以图1为例介绍无向连通稠密图的存储以及基于栈的非递归深度优先遍历算法。

1 图的存储表示图在计算机中的物理存储方式主要有邻接矩阵和邻接表两种，其中邻接矩阵适用于稠密图，邻接表适用于稀疏图。

该文例图可视为稠密图，因此图的物理存储采用邻接矩阵（二维数组adj[][]）实现，下面是创建邻接矩阵adj[][]的C语言代码：void create_matrix（int adj[V+1][V+1]）{int E，u，v，wgt；//表示边的条数printf（"请输入边数："）；scanf（"%d"，&E）；for（int i=1；i{printf（"请输入第%d条边"，i）；scanf（"%d %d %d"，&u，&v，&wgt）；adj[u][v]=adj[v][u]=wgt；}}图1利用create_matrix函数建立的邻接矩阵存储示意图如图2所示，我们可以发现图的邻接矩阵是对称矩阵。

2 图的深度优先遍历思想深度优先搜索是图的重要遍历方法之一，遍历过程的实质是对每个顶点查找其邻接点的过程，类似于树的先根遍历，具体思路为：1）从图中任一顶点v开始，当顶点v未被访问过时，做访问标记；2）遍历v的所有邻接点：如果邻接点u未被访问过：①输出顶点u；②做访问标记；③遍历u的所有邻接点；为了保证图中的各顶点在遍历过程中访问且仅访问一次，需要为每个顶点设一个访问标记，该文利用数组visited[V]实现，数组初始值设置为0，表示所有顶点均未被访问。

一、实验目的1. 理解邻接矩阵的概念及其在图论中的应用。

2. 掌握邻接矩阵的构建方法。

3. 学会使用邻接矩阵进行图的深度优先遍历和广度优先遍历。

4. 比较邻接矩阵和邻接表两种图的存储结构的优缺点。

二、实验内容1. 构建邻接矩阵2. 使用邻接矩阵进行图的深度优先遍历3. 使用邻接矩阵进行图的广度优先遍历4. 分析邻接矩阵和邻接表的优缺点三、实验环境1. 操作系统：Windows 102. 编程语言：C++3. 开发工具：Visual Studio 2019四、实验步骤1. 构建邻接矩阵（1）定义图的顶点数量n。

（2）创建一个nn的二维数组A，用于存储邻接矩阵。

（3）根据图的边信息，将对应的A[i][j]值设置为1（表示存在边）或0（表示不存在边）。

2. 使用邻接矩阵进行图的深度优先遍历（1）初始化访问标记数组visited，用于记录顶点是否被访问过。

（2）从某个顶点v开始，将其标记为已访问，并将其加入访问序列。

（3）对于v的每个邻接顶点u，如果u未被访问过，则递归调用深度优先遍历算法，并将u加入访问序列。

（4）重复步骤3，直到所有顶点都被访问过。

3. 使用邻接矩阵进行图的广度优先遍历（1）初始化队列Q和一个访问标记数组visited。

（2）将起始顶点v入队，并将其标记为已访问。

（3）当队列不为空时，执行以下步骤：a. 从队列中取出一个顶点v。

b. 将v的邻接顶点u入队，并将u标记为已访问。

c. 将v加入访问序列。

（4）重复步骤3，直到队列空为止。

4. 分析邻接矩阵和邻接表的优缺点（1）邻接矩阵的优点：a. 查找边的时间复杂度为O(1)。

b. 遍历图的时间复杂度为O(n^2)。

c. 适用于稠密图。

（2）邻接矩阵的缺点：a. 空间复杂度为O(n^2)，对于稀疏图，空间利用率低。

b. 查找边和遍历图的时间复杂度较高。

（3）邻接表的优点：a. 空间复杂度为O(n+e)，对于稀疏图，空间利用率高。

b. 查找边和遍历图的时间复杂度为O(n+e)。

数据结构专科辅导六------图的辅导练习题及解答（一）单项选择题1. 在一个具有n个顶点的有向图中，若所有顶点的出度数之和为s，则所有顶点的入度数之和为( )。

A sB s-1C s+1D n2. 在一个具有n个顶点的有向图中，若所有顶点的出度数之和为s，则所有顶点的度数之和为( )。

A sB s-1C s+1D 2s3. 在一个具有n个顶点的无向图中，若具有e条边，则所有顶点的度数之和为( )。

A nB eC n+eD 2e4. 在一个具有n个顶点的无向完全图中，则所含的边数为( )。

A nB n(n-1)C n(n-1)/2D n(n+1)/25. 在一个具有n个顶点的有向完全图中，则所含的边数为( )。

A nB n(n-1)C n(n-1)/2D n(n+1)/26. 在一个无权图中，若两顶点之间的路径长度为k，则该路径上的顶点数为( )。

A kB k+1C k+2D 2k7. 对于一个具有n个顶点的无向连通图，它包含的连通分量的个数为( )。

A 0B 1C nD n+18. 若一个图中包含有k个连通分量，若要按照深度优先搜索的方法访问所有顶点，则必须调用( )次深度优先搜索遍历的算法。

A kB 1C k-1D k+19. 若要把n个顶点连接为一个连通图，则至少需要( )条边。

A nB n+1C n-1D 2n10. 在一个具有n个顶点和e条边的无向图的邻接矩阵中，表示边存在的元素（又称为有效元素）的个数为( )。

A nB n⨯eC eD 2⨯e11. 在一个具有n个顶点和e条边的有向图的邻接矩阵中，表示边存在的元素个数为( )。

A nB n⨯eC eD 2⨯e12. 在一个具有n个顶点和e条边的无向图的邻接表中，边结点的个数为( )。

A nB n⨯eC eD 2⨯e13. 在一个具有n个顶点和e条边的有向图的邻接表中，保存顶点单链表的表头指针向量的大小至少为( )。

A nB 2nC eD 2e14. 在一个无权图的邻接表表示中，每个边结点至少包含( )域。

（转载）图的深度优先遍历⾮递归算法纠结图的深度优先搜索算法好久，⾮递归算法需要⽤到栈来记录上⼀次访问的结果，但是⼤脑中反应不出来。

这⾥做⼀个记录：栈的⽤处：在这⼀步执⾏完成之后，下⼀步需要⽤到上⼀步执⾏的结果，⽤栈来实现往往是最有效的。

以下是转载的内容：深度优先遍历算法的⾮递归实现需要了解深度优先遍历的执⾏过程，设计⼀个栈来模拟递归实现中系统设置的⼯作栈，算法的伪代码描述为：假设图采⽤邻接矩阵作为存储结构，具体算法如下：[cpp]1. 深度优先遍历算法的⾮递归实现需要了解深度优先遍历的执⾏过程，设计⼀个栈来模拟递归实现中系统设置的⼯作栈，算法的伪代码描述为：2.3.4. 假设图采⽤邻接矩阵作为存储结构，具体算法如下：5.6.7. <PRE class=cpp name="code">#include<iostream>8. #include <queue>9. using namespace std;10. #define MAX_NODE 1211. bool visited[MAX_NODE] ;12. int stack[ MAX_NODE] ;13. queue<int> q;14. int Matric[MAX_NODE][MAX_NODE] =15. {16. {-1,1,1,0,0,0,0,0,0,0,0,0},17. {1,-1,1,0,1,1,0,0,0,0,0,0},18. {1,1,-1,1,0,0,0,0,0,0,0,0},19. {0,0,1,-1,1,0,0,0,0,0,1,1},20. {0,1,0,1,-1,0,0,0,0,0,0,0},21. {0,1,0,0,0,-1,0,0,0,0,1,0},22. {0,0,0,0,0,0,-1,1,1,1,0,0},23. {0,0,0,0,0,0,1,-1,0,0,0,0},24. {0,0,0,0,0,0,1,0,-1,1,1,0},25. {0,0,0,0,0,0,1,0,1,-1,0,1},26. {0,0,0,1,0,1,0,0,1,0,-1,0},27. {0,0,0,1,0,0,0,0,0,1,0,-1},28. };29. void DFS( int v)30. {31. cout << " v"<< v ;32. int top = -1 ;33. visited[v] = true ;34. stack[++top] = v ;35. while ( top != -1)36. {37. v = stack[top] ;38. for (int i = 0 ; i < MAX_NODE ; i++)39. {40. if (Matric[v][i] == 1 &&!visited[i])41. {42. cout << " v" << i ;43. visited[i] = true ;44. stack[ ++top ] = i ;45. break ;46. }47. }48. if( i == MAX_NODE)49. {50. top -- ;51. }52. }53.54. }55.56.57. void BFS( int v)58. {59. int node = 0;60. q.push(v);61. visited[v] = true;62. while( !q.empty())63. {64. node = q.front();65. for ( int i = 0; i < MAX_NODE; i++ )66. {67. if ( Matric[node][i] == 1 && !visited[i])68. {69. visited[i] = true;70. q.push(i);71. }72. }73. cout <<" v" << node;74. q.pop();75. }76.77.78. }79. void Init()80. {81.82. int i = 0;83. for ( i = 0; i < MAX_NODE; i++)84. {85. visited[i] = false;86. }87. }88. int main()89. {90. Init();91. DFS( 1 ) ;92. cout << endl ;93. Init();94. BFS( 1 );95. cout << endl;96. Init();97. DFS( 6 );98. cout <<endl;99. return 0 ;100. }</PRE>101. <PRE></PRE>102. <PRE class=cpp name="code"></PRE>　深度优先遍历算法的⾮递归实现需要了解深度优先遍历的执⾏过程，设计⼀个栈来模拟递归实现中系统设置的⼯作栈，算法的伪代码描述为： 假设图采⽤邻接矩阵作为存储结构，具体算法如下：[cpp]1. #include<iostream>2. #include <queue>3. using namespace std;4. #define MAX_NODE 125. bool visited[MAX_NODE] ;6. int stack[ MAX_NODE] ;7. queue<int> q;8. int Matric[MAX_NODE][MAX_NODE] =9. {10. {-1,1,1,0,0,0,0,0,0,0,0,0},11. {1,-1,1,0,1,1,0,0,0,0,0,0},12. {1,1,-1,1,0,0,0,0,0,0,0,0},13. {0,0,1,-1,1,0,0,0,0,0,1,1},14. {0,1,0,1,-1,0,0,0,0,0,0,0},15. {0,1,0,0,0,-1,0,0,0,0,1,0},16. {0,0,0,0,0,0,-1,1,1,1,0,0},17. {0,0,0,0,0,0,1,-1,0,0,0,0},18. {0,0,0,0,0,0,1,0,-1,1,1,0},19. {0,0,0,0,0,0,1,0,1,-1,0,1},20. {0,0,0,1,0,1,0,0,1,0,-1,0},21. {0,0,0,1,0,0,0,0,0,1,0,-1},22. };23. void DFS( int v)24. {25. cout << " v"<< v ;26. int top = -1 ;27. visited[v] = true ;28. stack[++top] = v ;29. while ( top != -1)30. {31. v = stack[top] ;32. for (int i = 0 ; i < MAX_NODE ; i++)33. {34. if (Matric[v][i] == 1 &&!visited[i])35. {36. cout << " v" << i ;37. visited[i] = true ;38. stack[ ++top ] = i ;39. break ;40. }41. }42. if( i == MAX_NODE)43. {44. top -- ;45. }46. }47.48. }49.50.51. void BFS( int v)52. {53. int node = 0;54. q.push(v);55. visited[v] = true;56. while( !q.empty())57. {58. node = q.front();59. for ( int i = 0; i < MAX_NODE; i++ )60. {61. if ( Matric[node][i] == 1 && !visited[i])62. {63. visited[i] = true;64. q.push(i);65. }66. }67. cout <<" v" << node;68. q.pop();69. }70.71.72. }73. void Init()74. {75.76. int i = 0;77. for ( i = 0; i < MAX_NODE; i++)78. {79. visited[i] = false;80. }81. }82. int main()83. {84. Init();85. DFS( 1 ) ;86. cout << endl ;87. Init();88. BFS( 1 );89. cout << endl;90. Init();91. DFS( 6 );92. cout <<endl;93. return 0 ;94. }。

*问题描述：建立图的存储结构（图的类型可以是有向图、无向图、有向网、无向网，学生可以任选两种类型），能够输入图的顶点和边的信息，并存储到相应存储结构中，而后输出图的邻接矩阵。

1、邻接矩阵表示法:设G=(V,E)是一个图，其中V={V1,V2,V3…,Vn}。

G的邻接矩阵是一个他有下述性质的n阶方阵：1，若(Vi,Vj)∈E 或<Vi,Vj>∈E；A[i,j]={0，反之图5-2中有向图G1和无向图G2的邻接矩阵分别为M1和M2:M1=┌0 1 0 1 ┐│ 1 0 1 0 ││ 1 0 0 1 │└0 0 0 0 ┘M2=┌0 1 1 1 ┐│ 1 0 1 0 ││ 1 1 0 1 │└ 1 0 1 0 ┘注意无向图的邻接是一个对称矩阵，例如M2。

用邻接矩阵表示法来表示一个具有n个顶点的图时，除了用邻接矩阵中的n*n个元素存储顶点间相邻关系外，往往还需要另设一个向量存储n个顶点的信息。

因此其类型定义如下：VertexType vertex[MAX_VERTEX_NUM]; // 顶点向量AdjMatrix arcs; // 邻接矩阵int vexnum, arcnum; // 图的当前顶点数和弧(边)数GraphKind kind; // 图的种类标志若图中每个顶点只含一个编号i(1≤i≤vnum)，则只需一个二维数组表示图的邻接矩阵。

此时存储结构可简单说明如下：type adjmatrix=array[1..vnum,1..vnum]of adj;利用邻接矩阵很容易判定任意两个顶点之间是否有边（或弧）相联，并容易求得各个顶点的度。

对于无向图，顶点Vi的度是邻接矩阵中第i行元素之和，即n nD(Vi)＝∑A[i,j]（或∑A[i,j]）j=1 i=1对于有向图，顶点Vi的出度OD(Vi)为邻接矩阵第i行元素之和，顶点Vi 的入度ID(Vi)为第i列元素之和。

即n nOD(Vi)＝∑A[i,j]，OD(Vi)＝∑A[j,i]）j=1j=1用邻接矩阵也可以表示带权图，只要令Wij, 若<Vi,Vj>或(Vi,Vj)A[i,j]＝{∞, 否则。