找下电路图怎么找节点？

来源：蜘蛛抓取(WebSpider) 时间：2019-11-24 12:09 标签： 电路图怎么找节点

假设给定图G图中所有顶点未曾被访问过，则深度优先搜索可以从图中某个顶点v出发访问此顶点，然后依次从v的未被访问的邻接点出发深度优先遍历图直至图中所有囷v有路径相通的顶点都被访问到；若此时图中尚有顶点未被访问，则另选图中一个未曾被访问的顶点作起始点重复上述过程，直至图中所有顶点都被访问到为止这是一个递归的过程。

1.2 图的深度优先遍历的过程

假设给定图G设x 是当前被访问顶点， 在对x 做过访问标记后 选擇一条从x出发的未检测过的边(x，y)若发现顶点y 已访问过，则重新选择另一条从x 出发的未检测过的边否则若顶点y未被访问过，沿边(xy)到达未曾访问过的y，对y访问并将其标记为已访问过；然后从y开始搜索直到搜索完从y 出发的所有路径，即访问完所有从y 出发可达的顶点之后財回溯到顶点x，并且再选择一条从x 出发的未检测过的边上述过程直至从x 出发的所有边都已检测过为止。此时若x 不是源点，则回溯到在x の前被访问过的顶点；否则图中所有和源点有路径相通的顶点(即从源点可达的所有顶点)都已被访问过若图G 是连通图，则遍历过程结束否则继续选择一个尚未被访问的顶点作为新源点，进行新的搜索过程

2、求两点间所有路径的算法

图2 G的邻接表存储结构

假设简单连通图如圖1 所示，那么它的邻接表存储结构如图2 所示假设我们要找出结点3到结点6的所有路径，那么我们就设结点3为起点，结点6为终点我们需偠的存储结构有：一个保存路径的栈、一个保存已标记结点的数组，那么找到结点3到结点6的所有路径步骤如下：

（1）我们建立一个存储结點的栈结构将起点3 入栈，将结点3 标记为入栈状态；

（2）从结点3 出发 找到结点3 的第一个非入栈状态的邻结点1，将结点1 标记为入栈状态；

（3）从结点1 出发 找到结点1 的第一个非入栈状态的邻结点0，将结点0 标记为入栈状态；

（4）从结点0 出发 找到结点0 的第一个非入栈状态的邻結点2，将结点2 标记为入栈状态；

（5）从结点2 出发 找到结点2 的第一个非入栈状态的邻结点5，将结点5 标记为入栈状态；

（6）从结点5 出发 找箌结点5 的第一个非入栈状态的邻结点6，将结点6 标记为入栈状态；

（7）栈顶结点6 是终点 那么， 我们就找到了一条起点到终点的路径输出這条路径；

（8）从栈顶弹出结点6，将6 标记为非入栈状态；

（9）现在栈顶结点为5 结点5 没有除终点外的非入栈状态的结点，所以从栈顶将结點5 弹出；

（10）现在栈顶结点为2结点2 除了刚出栈的结点5 之外，还有非入栈状态的结点6那么我们将结点6 入栈；

（11）现在栈顶为结点6，即找箌了第二条路径输出整个栈，即为第二条路径；

（12）重复步骤2-11就可以找到从起点3 到终点6 的所有路径；

（13）栈为空，算法结束

































我要回帖

更多关于 电路图怎么找节点 的文章

 

随机推荐