精华内容
下载资源
问答
  • DFS、BFC算法说明代码实现测试用例 说明 BFS算法我们常用的方法就是...下面提供有向和无向图的DFS、BFS的实现 想要得到有向和无向只需要在void createMGraph函数里面修改即可,我也做了标记,供大家参考 代码实现 #de

    说明

    BFS算法我们常用的方法就是利用队列来处理,访问一个结点,就访问所有与它有关的结点,然后反复,比较简单
    DFS算法便是访问一个结点,然后一直访问下去,直到没有结点可访问,可谓“不撞南墙不回头”,该算法最重要的就是实现int FirstAdjVex函数int NextAdjVex函数这两个函数的实现
    下面提供有向和无向图的DFS、BFS的实现
    想要得到有向和无向只需要在void createMGraph函数里面修改即可,我也做了标记,供大家参考

    代码实现

    #define _CRT_SECURE_NO_WARNINGS
    #include <stdio.h>
    #include <stdlib.h>
    #include <stdbool.h>
    #include <limits.h>
    
    #define MAX_VERTEX_NUM 20    //最大顶点个数 
    #define INFINITY 0x3f3f3f3f  //最大值∞ 
    
    typedef char VertexType;   //顶点向量类型 
    typedef int VRType;
    typedef int InfoType;
    typedef int QElemType;
    
    //图的数组存储表示 
    typedef struct {
        VertexType vexs[MAX_VERTEX_NUM];    //顶点向量
        VRType arcs[MAX_VERTEX_NUM][MAX_VERTEX_NUM];
        //邻接矩阵,于无权图1、0表示两个顶点是否相邻,对于有权图为权值
        int vexnum, arcnum; //图的顶点数和弧数
    }MGraph;
    
    bool visited[MAX_VERTEX_NUM];  //标记顶点是否被访问,访问为true,否则为false
    
    //查找顶点在顶点向量中的位置
    int locateVertex(MGraph umg, VertexType v)
    {
        int i;
        for (i = 0; i < umg.vexnum; i++)
        {
            if (v == umg.vexs[i])
                return i;
        }
        return -1;
    }
    //创建无向有权图
    void createMGraph(FILE* fp, MGraph* mg)
    {
        int i, j, v, w;
        char v1, v2;
        printf("输入有权图的顶点数和边数,注意输入的第一个值将作为后序遍历的起始位置\n");
        fscanf_s(fp, "%d%d", &(*mg).vexnum, &(*mg).arcnum);
        for (v = 0; v < (*mg).vexnum; v++)//初始化
            visited[v] = false;
        printf("输入顶点名称\n");
        for (v = 0; v < (*mg).vexnum; v++)
        {
            printf("输入第%d个顶点名称:", v);
            fscanf_s(fp, "%c", &(*mg).vexs[v], 1);
            //     getchar();
        }
        //初始化邻接矩阵
        for (i = 0; i < (*mg).vexnum; i++)
            for (j = 0; j < (*mg).vexnum; j++)
                (*mg).arcs[i][j] = INFINITY;
        //将图中相邻的顶点的邻接矩阵值设为边的权值 
        printf("输入边的信息,输入边的两个顶点名称和权值v1 v2 w\n");
        for (v = 0; v < (*mg).arcnum + 1; v++)
        {
            printf("输入第%d条边两个顶点和权值:", v);
            fscanf_s(fp, "%c", &v1, 1);
            fscanf_s(fp, "%c", &v2, 1);
            fscanf_s(fp, "%d", &w);
            //  fscanf(fp,"%c%c%d",, &v2, &w);
             // getchar();
            i = locateVertex(*mg, v1);
            j = locateVertex(*mg, v2);
           ==(*mg).arcs[i][j] = (*mg).arcs[j][i] = w;    //无向图,一条边关联两个顶点==
           ==// (*mg).arcs[i][j] = w;//有向图,边为单向==
        }
    }
    
    //打印图的邻接矩阵
    void print(MGraph G)
    {
        int i, j;
        printf("图的邻接矩阵\n");
        for (i = 0; i < G.vexnum; i++)
        {
            for (j = 0; j < G.vexnum; j++)
            {
                if (G.arcs[i][j] != INFINITY)
                    printf("%d  ", G.arcs[i][j]);
                else
                    printf("∞ ");
            }
            printf("\n");
        }
        printf("\n");
    }
    
    //深度优先遍历图 
    int FirstAdjVex(MGraph G, int v)
    {
        //获取与顶点v相邻的第一个顶点下标 
        int i;
        for (i = 0; i < G.vexnum; i++)
        {
            if (G.arcs[v][i] != 0 && G.arcs[v][i] != INFINITY && !visited[i])
                return i;
        }
        return -1;
    }
    
    int NextAdjVex(MGraph G, int v, int w)
    {   //得到v的下一个未被访问的相邻顶点下标 
        int i;
        for (i = w; i < G.vexnum; i++)
        {
            if (G.arcs[v][i] != 0 && G.arcs[v][i] != INFINITY && !visited[i])
                return i;
        }
        return -1;
    }
    
    void DFS(MGraph G, int v)
    {
        //请在此处填写代码实现深度优先遍历v顶点所在的连通分量 
        //初始化
        visited[v] = true;
        int w;
        w = FirstAdjVex(G, v);
        while (w != -1)
        {
            printf("%c  ", G.vexs[w]);
            if (visited[w] != true)
                DFS(G, w);
            w = NextAdjVex(G, v, w);//更新w的值
        }
    }
    
    void DFSTraverse(MGraph G)
    {
        printf("DFS遍历的结果为:\n");
        printf("%c ", G.vexs[0]);
        DFS(G, 0);
        printf("\n");
    }
    
    typedef struct QNode
    {
        QElemType data;
        struct QNode* qnext;
    }QNode, * PQNode;
    
    typedef struct Queue
    {
        PQNode front;
        PQNode rear;
    }Queue, * PQueue;
    
    //初始化一个空队列 
    PQueue initQueue()
    {
        PQueue pqueue = (PQueue)malloc(sizeof(Queue));
        PQNode pqnode = (PQNode)malloc(sizeof(QNode));
        if (pqnode == NULL)
        {
            printf("队列头空间申请失败!\n");
            exit(-1);
        }
        if (pqueue && pqnode)
        {
            pqueue->front = pqueue->rear = pqnode;
            pqnode->qnext = NULL;
            return pqueue;
        }
    }
    
    //队尾入队
    void enQueue(PQueue pqueue, QElemType data)
    {
        PQNode pqnode = (PQNode)malloc(sizeof(QNode));
        if (pqnode == NULL)
        {
            printf("队列结点申请失败!\n");
            exit(-1);
        }
        pqnode->data = data;
        pqnode->qnext = NULL;
        pqueue->rear->qnext = pqnode;
        pqueue->rear = pqnode;
    }
    //判断队列是否为空
    bool isEmpty(PQueue pqueue)
    {
        if (pqueue->front == pqueue->rear)
            return true;
        return false;
    }
    //队头出队
    QElemType deQueue(PQueue pqueue)
    {
        if (isEmpty(pqueue))
        {
            printf("队列为空\n");
            exit(-1);
        }
        PQNode pqnode = pqueue->front->qnext;
        pqueue->front->qnext = pqnode->qnext;
        if (pqnode == pqueue->rear)
            pqueue->rear = pqueue->front;
        QElemType data = pqnode->data;
        free(pqnode);
        return data;
    
    }
    void BFSTraverse(MGraph G)
    {
        printf("广度优先遍历序列:");
        int i, v, w;
        for (i = 0; i < G.vexnum; i++)
            visited[i] = false;
        PQueue pqueue = initQueue();    //初始化辅助队列 
        for (i = 0; i < G.vexnum; i++)
        {
            if (!visited[i])             //i未被访问 
            {
                visited[i] = true;
                printf("%c ", G.vexs[i]);
                enQueue(pqueue, i);
                while (!isEmpty(pqueue))
                {
                    v = deQueue(pqueue);    //队头元素出队 
                    for (w = FirstAdjVex(G, v); w >= 0; w = NextAdjVex(G, v, w))
                        if (!visited[w])            //w为v的尚未访问的邻接顶点 
                        {
                            visited[w] = true;
                            printf("%c ", G.vexs[w]);
                            enQueue(pqueue, w);
                        }
                }
            }
        }
        printf("\n");
    }
    
    int main()
    {
        printf("带权有向图测试:\n");
        MGraph mg;
        FILE* fp;
        fp = fopen("Graph.txt", "r");
        createMGraph(fp, &mg);
        print(mg);
        printf("\n");
        DFSTraverse(mg);
        printf("\n");
        printf("BFS搜素结果:\n");
        BFSTraverse(mg);
        printf("\n");
    
        return 0;
    }
    

    测试用例

    有向图测试用例:
    在这里插入图片描述

    在这里插入图片描述
    无向图测试用例:
    在这里插入图片描述

    在这里插入图片描述

    展开全文
  • 一个n行m列的地图 地图上每个格子要么是o,要么是x o表示这个格子是安全的 x表示这个格子不能进入 你现在在第0行,第0列(左上角) 你希望走到第x行,第y列 输入保证(0,0)是安全的 向上走一格耗时a分钟 下走一...

    /*
    有一个n行m列的地图
    地图上每个格子要么是o,要么是x
    o表示这个格子是安全的
    x表示这个格子不能进入

    你现在在第0行,第0列(左上角)
    你希望走到第x行,第y列

    输入保证(0,0)是安全的

    向上走一格耗时a分钟
    向下走一格耗时b分钟
    向左走一格耗时c分钟
    向右走一格耗时d分钟

    问走到目的地点(第x行,第y列)最快需要多少分钟

    如果无法走到,输出-1

    输入描述:
    第一行输入T表示有T组数据(1<=T<=30)
    每组数据
    第一行输入两个整数 n,m(1 <= n, m <= 200)
    第二行输入两个整数 x,y (0 <= x < n, 0 <= y < m)
    第三行输入四个整数 a,b,c,d (0 <= a, b, c, d <= 300)
    接下来n行每行m个字符('o’或者’x’表示地图)

    输出描述:
    对于第i组测试数据,输出一行
    Case#i : ans

    示例1:
    2
    5 5
    2 2
    1 5 25 125
    ooooo
    oxxxo
    oxooo
    oxxxo
    ooooo
    5 5
    2 2
    0 0 0 0
    ooooo
    oxxxo
    oxoxo
    oxxxo
    ooooo

    case #1: 560
    case #2: -1

    说明
    560 = 125 * 4 + 5 * 2 + 25 * 2
    */

    /*
    思路:
    利用BFS 搜索思想,从(0,0)点开始,每次搜索四周可以到达的结点,直到搜到终点, 在求最小权重的问题上(或者最小路径),第一个找到的解就是最小的权重(或者最小路径)(也只能找到一条路径,因为访问过的点已经做了标记不能再访问)
    因为路径远的权重肯定大于路径的近的权重,当路径相等时,权重一定相等。

    */

    /*
    有一个n行m列的地图
    地图上每个格子要么是o,要么是x
    o表示这个格子是安全的
    x表示这个格子不能进入
    
    你现在在第0行,第0列(左上角)
    你希望走到第x行,第y列
    
    输入保证(0,0)是安全的
    
    向上走一格耗时a分钟
    向下走一格耗时b分钟
    向左走一格耗时c分钟
    向右走一格耗时d分钟
    
    问走到目的地点(第x行,第y列)最快需要多少分钟
    
    如果无法走到,输出-1
    
    输入描述:
    第一行输入T表示有T组数据(1<=T<=30)
    每组数据
    第一行输入两个整数 n,m(1 <= n, m <= 200)
    第二行输入两个整数 x,y (0 <= x < n, 0 <= y < m)
    第三行输入四个整数 a,b,c,d (0 <= a, b, c, d <= 300)
    接下来n行每行m个字符('o'或者'x'表示地图)
    
    输出描述:
    对于第i组测试数据,输出一行
    Case#i : ans
    
    示例1:
    2
    5 5
    2 2
    1 5 25 125
    ooooo
    oxxxo
    oxooo
    oxxxo
    ooooo
    5 5
    2 2
    0 0 0 0
    ooooo
    oxxxo
    oxoxo
    oxxxo
    ooooo
    
    case #1: 560
    case #2: -1
    
    说明
    560 = 125 * 4 + 5 * 2 + 25 * 2
    */
    
    
    
    /*
    思路:
    利用BFS 搜索思想,从(0,0)点开始,每次搜索四周可以到达的结点,直到搜到终点, 在求最小权重的问题上(或者最小路径),第一个找到的解就是最小的权重(或者最小路径)(也只能找到一条路径,因为访问过的点已经做了标记不能再访问)
    因为路径远的权重肯定大于路径的近的权重,当路径相等时,权重一定相等。
    */
    #include<stdio.h>
    #include<string.h>
    #include<stdlib.h>
    #include<iostream>
    #include<queue>
    #include<vector>
    using namespace std;
    #define MAXGRAPH 201
    //vector<int> cost;
    int n, m, x, y, a, b, c, d;
    int visited[MAXGRAPH][MAXGRAPH];
    char graph[MAXGRAPH][MAXGRAPH];
    
    int move_x[4] = { -1, 1, 0, 0 }; //移动x的方向
    int move_y[4] = { 0, 0, -1, 1 }; //移动y的方向
    struct node
    {
    	int x;
    	int y;
    	int minutes;
    };
    
    bool check(int x, int y)
    {
    	if (x >= 0 && x < n)
    	{
    		if (y >= 0 && y < m)
    		{
    			if (visited[x][y] != 1 && graph[x][y] == 'o')
    			{
    				return true;
    			}
    		}
    	}
    	return false;
    }
    
    void BFS(int T)
    {
    	struct node init_node;
    	init_node.x = 0;
    	init_node.y = 0;
    	init_node.minutes = 0;
    	queue<struct node> que;  //从图的(0, 0)结点遍历
    	que.push(init_node);
    	visited[init_node.x][init_node.y] = 1;  //记录该点已经走过
    	bool flag = false;
    	while (!que.empty()) //队列不为空,继续遍历
    	{
    		struct node now_node = que.front();
    		que.pop();
    		visited[now_node.x][now_node.y] = 1;
    		if (now_node.x == x && now_node.y == y) //到达终点
    		{
    			flag = true;
    			cout << "Case #" << T << ": " << now_node.minutes << endl;
    			return; 
    			//cost.push_back(now_node.minutes);
    		}
    		struct node next_step = now_node;
    		for (int i = 0; i < 4; i++)
    		{
    			if (check(now_node.x + move_x[i], now_node.y + move_y[i]))
    			{
    				next_step.x = now_node.x + move_x[i];
    				next_step.y = now_node.y + move_y[i];
    				if (move_x[i] == -1 && move_y[i] == 0) //上
    				{
    					next_step.minutes = now_node.minutes + a;
    				}
    				else if (move_x[i] == 1 && move_y[i] == 0) //下
    				{
    					next_step.minutes = now_node.minutes + b;
    				}
    				else if (move_x[i] == 0 && move_y[i] == -1) //左
    				{
    					next_step.minutes = now_node.minutes + c;
    				}
    				else if (move_x[i] == 0 && move_y[i] == 1) //右
    				{
    					next_step.minutes = now_node.minutes + d;
    				}
    				visited[next_step.x][next_step.y] = 1;  //标记访问过的坐标
    				que.push(next_step);
    			}
    		}
    	}
    	if (flag == false)
    	{
    		cout << "Case #" << T << ": " << -1 << endl;
    	}
    	//else
    	//{
    	//	sort(cost.begin(), cost.end());
    	//	cout << cost.at(0) << endl;
    	//}
    }
    
    int main()
    {
    	int T;
    	int count = 1;
    	scanf("%d", &T);
    	while (T--)
    	{
    		scanf("%d %d %d %d %d %d %d %d", &n, &m, &x, &y, &a, &b, &c, &d);
    		getchar();
    
    		for (int i = 0; i < n; i++)
    		{
    			for (int j = 0; j < m; j++)
    			{
    				graph[i][j] = 'x';
    			}
    		}
    
    		for (int i = 0; i < n; i++)
    		{
    			for (int j = 0; j < m; j++)
    			{
    				visited[i][j] = 0;
    			}
    		}
    		//cost.clear();
    		for (int i = 0; i < n; i++)
    		{
    			for (int j = 0; j < m; j++)
    			{
    				scanf("%c", &graph[i][j]);
    			}
    			getchar();
    		}
    		BFS(count);
    		count++;
    	}
    	
    	return 0;
    }
    
    
    

    类似题目:https://www.dotcpp.com/oj/problem1672.html
    参考:https://blog.dotcpp.com/a/8304

    展开全文
  • 本次实验要求设计有向带权图的抽象数据类型,实现的构造、顶点的增删查,边的增删改、深度优先遍历与广度优先遍历、单源最短路径、多源最短路径、判断中是否存在负环。 效果 #include <stdio.h> #...

    题目

    图是一种使用广泛的数据结构。本次实验要求设计有向带权图的抽象数据类型,实现图的构造、顶点的增删查,边的增删改、深度优先遍历与广度优先遍历、单源最短路径、多源最短路径、判断图中是否存在负环。
    在这里插入图片描述

    效果

    在这里插入图片描述

    #include <stdio.h>
    #include <stdlib.h>
    #include <string.h>
    #define MAXX 10000
    #define INF 0x3fffffff
    int g_1[MAXX][MAXX],g_2[MAXX][MAXX];
    char point[MAXX];
    int n;//n个节点,编号最大的
    char v[MAXX];
    int dist[MAXX];
    void add_g_1(int b,int c,int d){
        point[b]=1;
        point[c]=1;
        g_1[b][c]=d;
        if(b > n) n=b;
        if(c > n) n=c;
    }
    void g1tog2(){
        for(int i=0;i<=n;i++){
            for(int j=0;j<=n;j++){
                if(g_1[i][j]<INF){
                    g_2[i][j]=g_1[i][j];
                    g_2[j][i]=g_1[i][j];
                }
            }
        }
    
    }
    void dfs(int x){
        v[x]=1;
        printf("%d ",x);
        for(int i=0;i<=n;i++){
            if(v[i]==0 && g_2[x][i]!=INF){
                dfs(i);
            }
        }
    }
    void bfs(int x){
        int q[MAXX];
        int p=0,o=0;
        q[o++]=x;
        v[x]=1;
        while(p<o){
            x=q[p++];
            printf("%d ",x);
            for(int i=0;i<=n;i++){
                if(v[i]==0 && g_2[x][i]!=INF){
                    q[o++]=i;
                    v[i]=1;
                }
            }
        }
    }
    void Dijkstra(int x){
        dist[x]=0;
        while(1)
    	{
    		int min=INF;
    		int y=-1;
    		for(int i=0;i<=n;i++)
    		{
    			if(dist[i]<min && v[i]==0)
    			{
    				min=dist[i];
    				y=i;
    			}
    		}
    		if(y==-1)	return;
    		v[y]=1;
    		for(int j=0;j<=n;j++){
                if(v[j]==0 && dist[y]+g_1[y][j]<dist[j]){
                     dist[j]=dist[y]+g_1[y][j];
                }
    		}
    	}
    }
    int bf(int x){
        for(int i=0;i<=n;i++){
            dist[i]=INF;
        }
        memset(v,0,sizeof(v));
        dist[x]=0;
        int flag;
        for (int i = 0; i <= n; i++) {
            flag=0;
            for (int j = 0; j <= n; j++) {
                for (int k = 0; k <= n; k++) {
                    if (dist[k] > dist[j] + g_1[j][k]) {
                        dist[k] = dist[j] + g_1[j][k];
                        flag = 1;
                    }
                }
            }
            if (!flag) return 1;
        }
        flag = 0;
        for (int j = 0; j <= n; j++) {
            for (int k = 0; k <= n; k++) {
                if (dist[k] > dist[j] + g_1[j][k]) {
                    flag = 1;
                }
            }
        }
        return !flag;
    }
    int main()
    {
        memset(point,0,sizeof(point));
        for(int i=0;i<MAXX;i++){
            for(int j=0;j<MAXX;j++){
                g_1[i][j]=INF;
                g_2[i][j]=INF;
            }
        }
        int now=0;//当前操作指令
        while(1){
            printf("请输入需求\r\n");
            printf(" 0 输入节点\r\n");
            printf(" 1 节点\r\n");
            printf(" 2 边\r\n");
            printf(" 3 无向图dfs\r\n");
            printf(" 4 无向图bfs\r\n");
            printf(" 5 单源最短路\r\n");
            printf(" 6 任意两点最短路\r\n");
            printf(" 7 判断负环\r\n");
            scanf("%d",&now);
            if(now==0){
                int a,b,c,d;
                scanf("%d %d",&n,&a);
                n-=1;
                for(int i=0;i<a;i++){
                    scanf("%d %d %d",&b,&c,&d);
                    add_g_1(b,c,d);
                }
            }else if(now==1){
                printf("  1增加 2删除 3查找\r\n");
                int a,b,c,d;
                scanf("%d",&a);
                if(a==1){
                    scanf("%d",&b);
                    point[b]=1;
                }else if(a==2){
                    scanf("%d",&b);
                    point[b]=0;
                    if(b==n){
                        n--;
                    }
                }else if(a==3){
                    scanf("%d",&b);
                    if(point[b]==1){
                        printf("    存再\r\n");
                    }else{
                        printf("   不存再\r\n");
                    }
                }
            }else if(now==2){
                printf("  1增加 2删除 3改变\r\n");
                int a,b,c,d;
                if(a==1 || a==3){
                    scanf("%d %d %d",&b,&c,&d);
                    add_g_1(b,c,d);
                }else if(a==2){
                    scanf("%d %d" ,&b,&c);
                    g_1[b][c]=INF;
                }
            }else if(now==3){
                int a;
                g1tog2();
                scanf("%d",&a);
                memset(v,0,sizeof(v));
                dfs(a);
                printf("\r\n");
            }else if(now==4){
                g1tog2();
                int a;
                scanf("%d",&a);
                memset(v,0,sizeof(v));
                bfs(a);
                printf("\r\n");
            }else if(now==5){
                for(int i=0;i<=n;i++){
                    dist[i]=INF;
                }
                memset(v,0,sizeof(v));
                int a;
                scanf("%d",&a);
                Dijkstra(a);
                for(int j=0;j<=n;j++){
                    if(j==a)continue;
                    if(dist[j]==INF){
                        printf(" %d->%d:error ",a,j);
                    }else{
                        printf(" %d->%d:%d ",a,j,dist[j]);
                    }
                }
            }else if(now==6){
                for(int i=0;i<=n;i++){
                    for(int i=0;i<=n;i++){
                        dist[i]=INF;
                    }
                    memset(v,0,sizeof(v));
                    Dijkstra(i);
                    for(int j=0;j<=n;j++){
                        if(j==i)continue;
                        if(dist[j]==INF){
                            printf("%d->%d:error ",i,j);
                        }else{
                            printf("%d->%d:%d ",i,j,dist[j]);
                        }
                    }
                    printf("\r\n");
                }
            }else if(now==7){
                int fl=1;
                for(int i=0;i<=n;i++){
                    if(bf(i)==0){
                        fl=0;
                        break;
                    }
                }
                if(fl){
                    printf("不存在负环\r\n");
                }else{
                    printf("存在负环\r\n");
                }
            }else break;
        }
        return 0;
    }
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    展开全文
  • 带权值的 BFS

    2019-09-20 16:32:19
    bfs遍历最求最短路径时通常借用优先队列即优先考虑最大的或者最小的权值 方法1 优先队列:(内置函数,优先考虑较小的权值) #include<iostream> #include<cstring> #include<queue> ...

    用bfs遍历最图求最短路径时通常借用优先队列即优先考虑最大的或者最小的权值

    方法1 优先队列:(内置函数,优先考虑较小的权值)

    #include<iostream>
    #include<cstring>
    #include<queue>
    using namespace std;
    struct node{
        int x,y,c;
        bool friend operator < (node a,node b){
            return a.c > b.c;//小的优先出来哦(没错就是大于号)
        }
    }r,w;
    int n;
    int dis[100+10][100+10];
    int vis[100+10][100+10];
    int ma[100+10][100+10];
    int d[4][2]={1,0,0,1,-1,0,0,-1};
    void bfs(int xx,int yy){            //bfs求终点到其余各点的最短路 
        priority_queue<node> q;
        r.x = r.y = xx;
        r.c = ma[n-1][n-1];        //以终点作为起点 
        dis[n-1][n-1] = ma[n-1][n-1];    
        vis[n-1][n-1] = 1;
        q.push(r);
        while(!q.empty()){
            r = q.top();
            q.pop();
            for(int i = 0; i < 4; i++){
                int nx = r.x + d[i][0];
                int ny = r.y + d[i][1];
                if(nx < 0 || ny < 0 || nx >= n || ny >= n || vis[nx][ny]) continue;
                w.x = nx;
                w.y = ny;
                w.c = r.c + ma[nx][ny];//把点(nx,ny)处的权值加上 
                vis[nx][ny] = 1;//标记 
                q.push(w);
                dis[nx][ny]=w.c;//跟新数组,保证每次都是最优的 
            }
        }
         
    }
    int main(){
        cin>>n;
        for(int i=0;i< n;i++){
            for(int j=0;j< n;j++){
                cin>>ma[i][j];
            }
        }
        bfs(n-1,n-1);//这样一来数组里保存的就是其他点到点(n-1,n-1)的距离了; 
        for(int i=0;i<n;i++)
        {
            cout<<endl;
            for(int j=0;j<n;j++) 
                printf("%d ",dis[i][j]);
        }
        return 0;
        
    }

    方法2:队列加判断条件(开一个数组step,加一个判断条件step [ d x ] [ d y ] > step [x] [y] + mp [dx] [dy] ) 

    #include<iostream>
    #include<cstdio>
    #include<algorithm>
    #include<queue>
    #include<cstring>
    #define INF 100000000
    using namespace std;
    typedef long long ll;
    struct stu{
        int a,b;
    };
    int n;
    ll arr[52][52];
    ll step[52][52];
    ll dp[52][52];
    int d[4][2]={1,0,0,1,0,-1,-1,0};
    void bfs(int x,int y){
        queue<stu>que;
        que.push({x,y});
        step[x][y]=arr[x][y];
        while(que.size()){
            int xx=que.front().a;
            int yy=que.front().b;
            que.pop();
            for(int i=0;i<4;i++){
                int dx=xx+d[i][0];
                int dy=yy+d[i][1];
                if(dx>=1&&dy>=1&&dx<=n&&dy<=n){
                    if(step[dx][dy]>step[xx][yy]+arr[dx][dy]){
                        step[dx][dy]=step[xx][yy]+arr[dx][dy];//更新step数组,使他保存较小的的距离 
                        que.push({dx,dy});
                    }
                }
            }
        } 
    }
    
    int main(){
        while(cin>>n)
        {
            for(int i=0;i<=50;i++){
                for(int j=0;j<=50;j++)
                    step[i][j]=INF;
            }
            for(int i=1;i<=n;i++){
                for(int j=1;j<=n;j++){
                    cin>>arr[i][j];
                }
            }
            bfs(n,n);
            for(int i=1;i<=n;i++){
                cout<<endl;
                for(int j=1;j<=n;j++)
                    cout<<step[i][j];//数组里的每一个点都是到(n,n)的最短距离
            }
        }
        return 0;
    }
    数据:
    3 1 2 3 1 2 3 1 2 3

    转载于:https://www.cnblogs.com/Accepting/p/11273276.html

    展开全文
  • 用广度优先遍历求有向带权图的最短路径
  • BFS - 有向图的拓扑序列 给定一个n个点m条边的有向图,点的编号是1到n,中可能存在重边和自环。 请输出任意一个该有向图的拓扑序列,如果拓扑序列不存在,则输出-1。 若一个由中所有点构成的序列A满足:对于中...
  • 图论-BFS解无权有向图最短路径距离

    千次阅读 2015-08-13 00:28:16
    概述本篇博客主要内容: 对广度优先搜索算法(Breadth-First-Search)进行介绍; 介绍用邻接表的存储结构实现一个(附...介绍用BFS算法求解无权有向图(附C++实现源码)。 最后给出完整的代码和朋友们一起讨论进步。
  • 该算法是用C#实现的,要用Visual Studio2005
  • 1.生成一个100个点,3000条边的有向随机,任选一点作为源点,计算S到其他节点的距离。(注:用邻接链表存储) 2.将实验一中的有向图变为DAG。(从中去掉一些边,不允许用递归) 计算上述DAG中的最长路径。
  • 设计并验证如下算法:带权图采用邻接表表示,实现无向图的广度优先搜索与有向图的深度优先搜索。 #define MAX_VERTEX_NUM 20 //的邻接表存储表示 typedef struct ArcNode{ int adjvex; //该弧所指向的顶点的...
  • 无权无向图带权向图的实现 java 邻接矩阵实现无权无向图带权向图 java 1.的接口 import java.util.List; public interface Graph { public int getSize(); //返回中的顶点数 public List getVertices();...
  • 其实回答这个问题很简单,请大家仔细观察下,也就是使用 BFS 完成对树的搜索。比如,我要搜索节点 A 到节点 G 的最短路径。如下动图所示: 在 BFS 中,我们使用了数据结构中的一个队列(queue),我们知道队列的...
  • 向图-DFS和BFS

    2020-11-04 21:50:33
    向图 1 是由一组顶点和一组能够将两个顶点相连的边组成的。 (Graph)结构是一种非线性的数据结构,在实际生活中很多例子,比如交通运输网,地铁网络,社交网络,计算机中的状态执行等等都可以抽象成...
  • 描述 简单介绍一下就是由一些小圆点(称为顶点)和连接这些小圆点的直线(称为边)组成的。...bfs理论结果为 1 2 3 5 4 dfs理论结果为 1 2 4 3 5 思路 现在咱们从1号节点开始遍历这个,如果是广度优先bf
  • 狄克斯特拉算法用于找到带权图中,某点到其他各点的最短路径(BFS用于找出无权中的最短路径) 只适用于 有向无环 无负权重,因为狄克斯特拉算法在处理节点时候采用贪心思想,即某节点一旦被处理了,就说明不...
  • 【数据结构与算法】带权有向图

    千次阅读 2017-04-10 19:27:42
    MyGraph.h#pragma once #include #include #include using namespace std;// 邻接矩阵 // 带权有向图const int MAXSIZE = 20; const int INFINITE = 100;template class CMyGraph { publ
  • 是由顶点的穷非空集合和顶点之间边的集合组成,通常表示为: G=(V,E) 其中:G表示一个,V是G中顶点的集合,E是G中顶点之间边的集合。 注: 在线性表中,元素个数可以为零,称为空表; 在树中,结点个数...
  • 带权图最短路径问题

    千次阅读 2019-07-06 15:53:41
    Dijsktra算法 :(优先队列+bfs) O(|E|×log|V|) 二、任意两点间最短路 Floyd-Warshall算法: O(|V|^3^) 一、单源最短路问题 Bellman-Ford算法: O(|V|×|E|) (浪费时间,遍历每一条边的时候不知道当前边...
  • 一、实验目的及要求 ... 在带权有向图上求解从某一原点出发到其余顶点的最短路径。 以界面的形式展现出相关的选项。 二、实验代码 #include <stdio.h> #include <stdlib.h> #define INFIN
  • 假设以下带权有向无环(连通或非连通,我这里用的是非连通的): 每个节点(node)可能与其他节点有向地相连 ... 设计一个算法,採用BFS方式输出G中从顶点u到v的最短路径(不带权的无向连通G採用邻接表存储) ...
  • 最短路径算法是图论中的常见问题,... 无权是有权最短路径的特例,即边的权重均是1。算法类似于BFS(宽度优先搜索),在实现时需要一个宽度优先搜索的队列。全局变量Distance用来保存所有点到输入顶点的距离。以邻接
  • 向图的广度优先遍历算法(bfs

    千次阅读 2021-04-24 21:59:38
    的广度优先搜索(Broad First Search) 。 类似于一个 分层搜索的过程,广度优先遍历需要使用一个队列以保持访问过的结点的顺序,以便按这个顺序来 访问这些结点的邻接结点 算法步骤 访问初始结点 v 并标记结点 ...
  • 向图的遍历 DFS 算法思想 深度优先搜索思想:假设初始状态是中所有顶点均未被访问,则从某个顶点v出发,首先访问该顶点,然后依次从它的各个未被访问的邻接点出发深度优先搜索遍历,直至中所有和v路径...
  • 一、传递闭包: 定义: n个顶点的有向图的传递闭包可以定义为一个n阶布尔矩阵T...但有向图不能并查集,所以现在可以用传递闭包了(当然无向图也可以用) 通过Floyd-Warshall算法https://blog.csdn.net/qq_4069105...
  • 该系列文章是本人整理的有关带权向图的数据结构和算法的分析与实现,如问题或者建议欢迎各位指出。 目录 基于C++的带权向图的实现 (一)- 数据结构 基于C++的带权向图的实现 (二)- 遍历算法 基于C++的...
  • #include <iostream> using namespace std; #define Maxsize 100 typedef char VertexType; typedef int EdgeType; type struct{ VertexType Vex[Maxsize]; EdgeType edge[Maxsize][Maxsize...void BFS(MGra.
  • 带权图的存储模板

    2019-04-07 12:50:33
    带权有向图的存储模板,无聊 做做玩玩。 #include<iostream> #include<vector> #include<queue> #define MAXN 100 using namespace std; struct Node { int data; //权值 int number; //编号 ...
  • 1. 深度优先遍历深度优先遍历(Depth First Search)的主要思想是:1、首先以一个未被访问过的顶点作为起始...1.1 无向图的深度优先遍历图解以下"无向图"为例:对上无向图进行深度优先遍历,从A开始:第1步:访问A...
  • 一般来说,用来帮助解决的问题类型与本书中已经讨论过的问题类型很大差别。如果处理一般的数据存储问题,可能用不到,但对某些问题,是必不可少的。 1.1 简介 是一种与树有些相像的数据结构。实际上,从...

空空如也

空空如也

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

有向带权图的bfs