精华内容
下载资源
问答
  • //s为路径长度 }; char mapp[maxn][maxn]; bool book[maxn][maxn]; void input() { for(int i=0;i;i++) { for(int j=0;j;j++) { cin>>mapp[i][j]; } } } void bfs(int sx,int sy,int gx,int gy) { ...
    #include<iostream>
    #include<cstdio>
    #include<cstring>
    #include<cstdlib>
    #include<cmath>
    #include<vector>
    #include<map>
    #include<queue>
    #include<set>
    #define maxn 105
    #define LL long long
    #define lson step<<1
    #define rson step<<1|1
    #define INF 4294967295
    using namespace std;
    int n,m;
    int sx,sy,gx,gy;
    struct node
    {
    	int x,y,s;//s为路径长度 
    };
    char mapp[maxn][maxn];
    bool book[maxn][maxn];
    void input()
    {
    	for(int i=0;i<n;i++)
    	{
    		for(int j=0;j<m;j++)
    		{
    			cin>>mapp[i][j];
    		}	
    	}	
    } 
    void bfs(int sx,int sy,int gx,int gy)
    {
    	int next[4][2]={{0,1},{1,0},{-1,0},{0,-1}};
    	int tx,ty;
    	node h,fw;
    	h.x=sx;h.y=sy;h.s=0;
    	queue<node>q;
    	q.push(h);
    	int flag=0;
    	while(!q.empty())
    	{
    		h=q.front();
    		q.pop();
    		for(int k=0;k<4;k++)
    		{
    			tx=h.x+next[k][0];
    			ty=h.y+next[k][1];
    			if(tx<0||tx>=n||ty<0||ty>=m)
    				continue;
    			if(mapp[tx][ty]=='.'&&book[tx][ty]==false)
    			{
    				fw.x=tx;
    				fw.y=ty;
    				fw.s=h.s+1;
    				book[tx][ty]=true;
    				q.push(fw);
    			}
    			if(tx==gx&&ty==gy)
    			{
    				flag=1;
    				break;
    			}
    		}
    		if(flag)
    			break;
    	}
    	cout << fw.s << endl;
    }
    int main()
    {
    	ios_base::sync_with_stdio(false);
    	cin>>n>>m;
    	input();
    	memset(book,false,sizeof(book));
    	cin>>sx>>sy>>gx>>gy;
    	sx--;sy--;gx--;gy--;
    	bfs(sx,sy,gx,gy);
        return 0;
    }
    

    展开全文
  • python算法分析与设计实验:宽度优先查找最短路径 一、实验目的 1、熟悉图的两种常见表示方法,熟练掌握如何在计算机中存储图。了解图在计算机应用领域常见的应用场景。 2、熟练掌握图上宽度优先搜索算法及其算法...

    python算法分析与设计实验:宽度优先查找最短路径

    一、实验目的
    1、熟悉图的两种常见表示方法,熟练掌握如何在计算机中存储图。了解图在计算机应用领域常见的应用场景。
    2、熟练掌握图上宽度优先搜索算法及其算法复杂度分析,了解利用宽度优先搜索解决计算问题的建模过程。
    3、熟练掌握图上深度优先搜索算法及其算法复杂度分析,了解深度优先算法的建模过程。

    二、实验工具
    Win10操作系统、python3.7编译环境、IDLE编译器

    三、实验内容
    给定无向图G=(V,E),求从源点s到图中各个结点v∈V的最近距离。如图1所示,从源点s到结点d,c和z的最短距离均为2,而到结点f和v的最短距离则为3。

    四、实验过程
    图的存储依然采用邻接列表的方式存储,通过设计一个Graph类来表示图。Graph类中的成员变量为字典类型变量adj,用于存储图中每一个结点的邻边,成员函数add_edge(u,v)将两个结点u和v建立连接。设计一个BFSResult类来存储BFS的输出结果,一个字典类型的变量level来存储各层结点。level的key对应层的结点,level的value则是层的标号。使用一个字典变量parent来记录结点的父结点。
    BFS的实现的函数bfs的输入参数为图G和初始结点s。bfs先初始化输出对象r。变量i索引参数,列表变量frontier存储当前层的结点,列表变量next存储frontier中的所有下一层的结点。
    五、实验结果分析
    按照BFS遍历该图的过程如下:首先,将初始结点s设置为第0层,然后找出结点s的所有邻居结点,其中还没有被遍历到的结点就将它们作为第1层的结点。再找出第1层的结点的邻居结点,所有未遍历的结点作为第2层的结点。依次遍历完图中所有结点,可得BFS的流程为:
    ·将源点置为第0层
    ·从源点s到该第i层每一个结点需要经过i条边
    ·第i层的每一个结点均来自前一层i-1。i为层数索引
    BFS的实现函数bfs,对于frontier中每一个结点u,找出u的所有邻居节点v,如果邻居结点没有遍历,则该结点v是下一层的结点。处理完frontier中所有结点后,用next对它重置。通过判断frontier是否为空来作为循环是否继续的条件。用bfs对图1进行宽度优先搜索,frontier0的初始值等于{s},下标0表示循环次数。第一次循环后,frontier1={a,x}。第二次循环后,frontier2={z,d,c}。第三次循环后,frontier3={f,v}。第四次循环时,frontier等于空,循环结束。

    六、附:实验代码

    class Graph:
        def __init__(self):
            self.adj={}
        def add_edge(self, u, v):
            if self.adj[u] is None:
                self.adj[u] = []
            self.adj[u].append(v)
    
    class BFSResult:
        def __init__(self):
            self.level = {}
            self.parent = {}
    
    def bfs(g,s):
        r = BFSResult()
        r.parent = {s:None}
        r.level = {s:0}
        i = 1
        frontier = [s]
        while frontier:
            next = []
            for u in frontier:
                for v in g.adj[u]:
                    if v not in r.level:
                        r.level[v] = i
                        r.parent[v] = u
                        next.append(v)
            frontier = next
            i += 1
            
        return r
    
    
    def find_shortest_path(result,v):
        source_vertex = [verterx for verterx, level in result.level.items() if level ==0]
        v_parent_list = []
        if v != source_vertex[0]:
            v_parent = result.parent[v]
            v_parent_list.append(v_parent)
            while v_parent != source_vertex[0] and v_parent != None:
                v_parent = result.parent[v_parent]
                v_parent_list.append(v_parent)
        return v_parent_list
    
    if __name__ == "__main__":
        g = Graph()
        g.adj = { "s" : ["a","x"],
                  "a" : ["z","s"],
                  "d" : ["f","c","x"],
                  "c" : ["x","d","f","v"],
                  "v" : ["f","c"],
                  "f" : ["c","d","v"],
                  "x" : ["s","d","c"],
                  "z" : []
                  }
        bfs_result = bfs(g,'s')
        print(bfs_result.level)
        print(find_shortest_path(bfs_result,'f'))
    
    展开全文
  • 宽度优先查找最短路径(可用于迷宫和,电路布线等),并输出最好的路径的长度。
  • 核心:用队列实现宽度优先搜索,队列里面放的都是将要走的位置, 队列pop出来的位置是当前要走的位置 队列push进去的位置是周围所有可走但还未走的位置 到终点或队列为空时退出。分别表示可达和不可达. ...

     

    /*
        P34: 迷宫的最短路径
    
        核心:用队列实现宽度优先搜索,队列里面放的都是将要走的位置,
              队列pop出来的位置是当前要走的位置
              队列push进去的位置是周围所有可走但还未走的位置
              到终点或队列为空时退出。分别表示可达和不可达.
    
        技巧:可以用大小相同的flag[][]来标记一些信息。这里我用-1表示未走,0表示0步后可达,1表示1步后可达,2表示。。。。。
              用pre[][]表示路径信息,找到终点后可以打印出所有路径
    
        注意:方向向量的方向,左上角为坐标原点,(1,0)为下,(-1,0)为上,(0,1)为右,(0,-1)为左
    
    运行结果:
    *************************************************************************************
                10 10
    
                #S######.#
                ......#..#
                .#.##.##.#
                .#........
                ##.##.####
                ....#....#
                .#######.#
                ....#.....
                .####.###.
                ....#...G#
                22
                墙 起 墙 墙 墙 墙 墙 墙 |` 墙
                <- |. -> -> -> -> 墙 <- |` 墙
                |. 墙 |. 墙 墙 |. 墙 墙 |` 墙
                |. 墙 |. -> -> |. -> -> -> ->
                墙 墙 |. 墙 墙 |. 墙 墙 墙 墙
                <- <- |. -> 墙 |. -> -> -> 墙
                |. 墙 墙 墙 墙 墙 墙 墙 |. 墙
                |. -> -> -> 墙 <- <- <- |. ->
                |. 墙 墙 墙 墙 |. 墙 墙 墙 |.
                |. -> -> -> 墙 |. -> -> 终 墙
    
    ****************************************************************************************
    */
    #include <utility>
    #include <queue>
    #include <iostream>
    #include <iterator>
    #include <vector>
    #include <memory.h>
    using namespace std;
    const int MAX = 110;
    int N, M;
    char maze[MAX][MAX];
    
    queue< pair<int, int> > que;//用队列实现bfs
    int dx[] = {-1, 0, 0, 1};//行向量
    int dy[] = {0, -1, 1, 0};//列向量,四个方向向量, 左上角为原点,所以方向为上,左,右,下
    int flag[MAX][MAX];//用做标记(i,j)走多少步可达
    string pre[MAX][MAX];
    int bfs(int i, int j)
    {
        //起点
        pair<int, int> start(i, j);
        que.push(start);
        flag[i][j] = 0;
        pre[i][j] = "";
    
        while (que.size())
        {
            //队列pop出来的是当前要走的位置
            pair<int, int> que_top = que.front();
            que.pop();
    
            //要走的位置是终点
            if (maze[que_top.first][que_top.second] == 'G')
            {
                pre[que_top.first][que_top.second] = "";
                return flag[que_top.first][que_top.second];
            }
    
    
            //队列push进去的是周围可走但未走的位置
            for (int i = 0; i < 4; i++)
            {
                int nx = dx[i] + que_top.first;
                int ny = dy[i] + que_top.second;
    
                if (nx >= 0 && nx < N && ny >= 0 && ny < M && maze[nx][ny] != '#' && flag[nx][ny] == -1)
                {
                    que.push(pair<int, int>(nx, ny));
                    flag[nx][ny] = flag[que_top.first][que_top.second]+1;
                    switch(i)
                    {
                    case 0:
                        pre[nx][ny] = "|`";
                        break;
                    case 1:
                        pre[nx][ny] = "<-";
                        break;
                    case 2:
                        pre[nx][ny] = "->";
                        break;
                    case 3:
                        pre[nx][ny] = "|.";
                        break;
                    }
                }
            }
        }
        return -1;
    
    }
    int main(void)
    {
        memset(flag, -1, sizeof(flag));
        cin >> N >> M;
        for (int i  = 0; i <  N; i++)
            for (int j = 0; j < M; j++)
            {
                cin>>maze[i][j];
                pre[i][j] = "";
            }
    
    
        for (int i  = 0; i <  N; i++)
            for (int j = 0; j < M; j++)
            {
                int temp;
                if (maze[i][j] == 'S')
                {
                    if ((temp = bfs(i, j)) == -1)
                        cout << "can't reach \n";
                    else
                        cout << temp <<"\n";
    
                }
    
            }
    
        for (int i  = 0; i <  N; i++)
            for (int j = 0; j < M; j++)
            {
                cout << pre[i][j] << " ";
                if(j == M-1)
                    cout << "\n";
            }
    
        return 0;
    }

     

    转载于:https://www.cnblogs.com/jkn1234/p/8706112.html

    展开全文
  • 输出的宽度优先搜索结果(注意以字典存放,键表示节点,值表示其先前节点,要表示课本上的宽度搜索结果,只需要将上述代码的结果整理为: {'a': 's','x': 's', 'z': 'a','c': 'x', 'd': 'x', 'f': 'c', 'v': 'c'} ...
    1. 课本上的是手动造轮子,尽管不完善,但是挺好用。这里就不记录课本上的了,通俗易懂,我们主要看看用库函数实现课本上的这俩功能,开阔下思路。
    2. 主要用到了网络分析库和绘图库,看代码:
    import networkx as nx
    import matplotlib.pyplot as plt
    
    G = nx.Graph()
    nodes = ['s', 'a', 'z', 'x', 'd', 'c', 'f', 'v']
    G.add_nodes_from(nodes)
    ebunch = [('a', 'z'), ('a', 's'), ('s', 'x'), ('x', 'd'),
              ('d', 'c'), ('x', 'c'), ('d', 'f'), ('c', 'f'),
              ('c', 'v'), ('f', 'v')]
    G.add_edges_from(ebunch)
    nx.draw(G, pos=nx.spring_layout(G), with_labels=True, font_size=24, node_size=2640)
    plt.show()
    print(nx.bfs_predecessors(G, 's'))
    print(nx.shortest_path(G, 's'))
    
    1. 打印出来的结果,看下图和课本图7.4即可,我们这里稍微解释下输出,和课本上的类似:
      在这里插入图片描述
    {'a': 's', 'c': 'x', 'd': 'x', 'f': 'c', 'v': 'c', 'x': 's', 'z': 'a'}
    {'a': ['s', 'a'], 'c': ['s', 'x', 'c'], 'd': ['s', 'x', 'd'], 'f': ['s', 'x', 'c', 'f'], 's': ['s'], 'v': ['s', 'x', 'c', 'v'], 'x': ['s', 'x'], 'z': ['s', 'a', 'z']}
    
    
    1. 共3个输出:
    • 构造好的图(不解释)
    • 输出的宽度优先搜索结果(注意以字典存放,键表示节点,值表示其先前节点,要表示课本上的宽度搜索结果,只需要将上述代码的结果整理为:{'a': 's','x': 's', 'z': 'a','c': 'x', 'd': 'x', 'f': 'c', 'v': 'c'},可以得出遍历流程为s->(a and x)->(z and c and d)->(f and v)。也即:frontier0={s}, fronter1={a,x}, frontier2={z,c,d}, frontier3={f,v},和课本一样
    • 从源点s出发找到的所有最短路径,也是字典存放,键和值分别对应的是从s到键的最短路径是值。这里要注意上述算法得出的’f’: [‘s’, ‘x’, ‘c’, ‘f’],表示从s到f最短路径和课本的s->x->d->f不同,但都是正确的,对于无向图,最短路径可能不止一条,条条大路通罗马么。
    1. 提醒下,有空学习下库函数,写法忒复杂,不过考虑的很全面,编写风格非常好。
    展开全文
  • 利用宽度优先搜索解决迷宫最短路径问题 题目:给定一个大小为N*M的迷宫,迷宫由通道和墙壁组成,每一步可以向邻接的上下左右四格的通道移动。求从起点到终点所需最小步数。 注意:本题假定从起点一定可以移动到...
  • 宽度优先搜索-----解决迷宫最短路径问题 一、关于宽度优先搜索的知识 1.深度优先搜索利用栈进行计算,因此一般场景中采用递归的方式实现。 2.宽度优先搜索则利用队列进行计算,搜索时首先将初始状态添加到队列里,...
  • 宽度优先搜索,即BFS,有时也叫做广度优先搜索。与深度优先搜索的一条路走到黑不同,它是先遍历离自己最近的一些点,然后逐步向更远的路径进行搜索。它利用的是队列来完成这一操作。在这道迷宫求解问题中它的时间...
  • Dijkstra单源最短路径算法和Prim最小生成树算法都采用了和宽度优先搜索类似的思想。其别名又叫BFS,属于一种盲目搜寻法,目的是系统地展开并检查图中的所有节点,以找寻结果。换句话说,它并不考虑结果的可能位置,...
  • 何谓宽度优先搜索(bfs)? 宽度优先搜索总是先搜索距离初始状态近的状态。开始状态--->只需1次转移就可以到达的所有状态--->只需2次转移就可以到达的所有状态......这样的顺序进行搜索。对于同一个状态,...
  • 该代码解决了最短路径问题(给定带权有向图G=(V, E),对任意顶点vi,vj∈V(i≠j),求顶点vi到顶点vj的最短路径。) 其中使用了广度优先搜索、文件读取技术等。
  • vector<pair<int,int>> transferDir{{0,1}, {0,-1}, {1,0}, {-1,0}}; using p=pair<...//开始点为's',终点为'd',障碍物为'#',其余均为'*' int MinStep...
  • 易语言最短路径走迷宫,BFS(宽度优先搜索) 易语言纯源码实现 简单搜索算法
  • 宽度优先搜索BFS:层序遍历、最短路径问题引言BFS实现的基本框架岛屿问题相关例题:求最大面积、求最大值 引言 DFS(深度优先搜索)问题通常是在树或者图结构上使用递归解决的一种常用算法。「网格」结构中也常常会...
  • 迷宫的最短路径 输出:22 #include<bits/stdc++.h> #define INF 10000000 using namespace std; typedef pair<int,int> P; char c[105][105];//表示迷宫的字符串的数组 int N,M; int sx,sy;//起点...
  • 但相对深度优先搜索来说,宽度优先搜索总是先搜索距离初始状态较近的状态,即由近及远,首先探索满足条件最近的状态。利用原理:队列,“先进先出”。 例题 迷宫的最短路径 给定一个大小为N*M的迷宫,迷宫由通道...
  • 如何利用Matlab 实现棋盘上最短路径搜索宽度优先搜索) 背景 现有如下棋盘(如图1) 图1 这是一个11×11的棋盘,其中黄色为目标区域,红色及绿色圆球为棋子,黑色为障碍物目标是求把小球从起始点移动到目标点的...
  • 迷宫的最短路径 给定一个大小为N*M的迷宫。迷宫由通道和墙壁组成,每一步可以向邻接的上下左右四格的通道移动。请求出从起点到终点所需的最小步数。假定从起点开始一定能够走到终点。 输入: 10 10 #.######.# ...
  • 广度优先搜索最短路径问题

    千次阅读 2020-03-12 11:46:56
    《算法图解》上看到的分析思路,把广度优先搜索直接与最短路径问题放在一起,mark一下 1、BFS解决最短路径问题 假设要从双子峰前往金门大桥。你想乘公交车前往,并希望换乘最少。可乘坐的公交车如下: 为找出...
  • #include #include #include using namespace std; const int INF = 10000000; typedef pair Point; int sx;//起点坐标 ...//到各个位置的最短距离的数组 int d[100][100]; //4个方向移动的向量,对应
  • 深度优先搜索 适用范围:深搜求最短路径的思想和用深搜迷宫寻路很像,能找出所有的从起点到目标点的路径,选出其中最短的一条。 但一般不用,只能处理 n<10n<10n<10 的情况 此算法仅供娱乐参考,实际不会用...
  • 宽度优先搜索按照距开始状态由近即远的顺序进行搜索,因此可以很容易地用来求最短路径、最少操作之类问题的答案。 可以用 d[N][M] 数组把最短距离保存起来,用充分大得常数 INF 来初始化,这样一来,尚未到达的...
  • Algorithm:C++语言实现之图论算法相关(图搜索广度优先BFS、深度优先DFS,最短路径SPF、带负权的最短路径Bellman-ford、拓扑排序) 目录 一、图的搜索 1、BFS (Breadth-First-Search) 广(宽)度优先 2、DFS ...
  • 利用广度优先搜索最短路径

    千次阅读 2016-04-09 13:57:30
    广度优先搜索:http://blog.csdn.net/u012763794/article/details/51081830 1.问题描述 输入: 输入n个顶点,m条边, 起点的编号 跟着再输入边x,y 输出: 该起点到达各个顶点最少经过几条边 样例: 输入: 5 5...
  • 迷宫的最短路径 输入一个NxM的迷宫。’#’,’.’,‘S’,'G’分别表示墙壁、通道、起点、终点。每一步可以向邻接的上下左右四个方向移动,求出从起点到终点所需的最小步数。(N,M<=100) 输入用例: 10 10 #S##...
  • 迷宫的最短路径  给定一个大小为N×M的迷宫。迷宫由通道和墙壁组成,每一步可以向邻接的上下左右四个的通道移动。请求出从起点到终点所需的最小步数。请注意,本题假定从起点一定可以移动到终点。(N,M≤100)('#...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 5,129
精华内容 2,051
关键字:

宽度优先搜索最短路径