zwt2726990701 2022-12-28 21:22 采纳率: 33.3%
浏览 159
已结题

c++邻接矩阵创建有向图,利用深度优先判断是否存在路径

以邻接矩阵表示法创建有向图,并基于图的深度优先遍历策略设计一算法,判断有向图中是否存在由顶点A到顶点B的路径。(代码注释详细点)

  • 写回答

2条回答 默认 最新

  • Jettblue_jr 2022-12-28 21:44
    关注

    代码如下:

    #define _CRT_SECURE_NO_WARNINGS 1
    #include <iostream>
    using namespace std;
    #define MVNUM 100                //最大顶点数
    #define MAXINT 32767                //极大值相当于无穷大
     
    int visited[MVNUM] = { 0 };            //辅助数组,判断遍历过了没
    int visit[MVNUM] = { 0 };            //同理
    typedef struct
    {
        char vexs[MVNUM];            //顶点数据数组
        int arr[MVNUM][MVNUM];            //邻接矩阵
        int vexnum, arcnum;            //现有顶点数与边数
    }AMGraph;                            
    typedef struct
    {
        int* base;                //队列数组
        int front;                //队头的下标
        int rear;                //队尾的下标
    }sqQueue;
     
    int initGraph(AMGraph& G);            //初始化邻接矩阵
    void showGraph(AMGraph G);            //打印邻接矩阵
    int locatVex(AMGraph G, char u);        //定位顶点在邻接矩阵的下标
    int createGraph(AMGraph& G);            //建立邻接矩阵
    void dfsAM(AMGraph G,int i);            //深度优先搜索遍历
    void bfsAM(AMGraph G, int i);            //广度优先搜索遍历
    int initQueue(sqQueue& Q);            //初始化队列
    int enQueue(sqQueue& Q, int i);            //入队
    int firstVEX(AMGraph G, int u);            //第一个邻接顶点        
    int nextVEX(AMGraph G,int w ,int u);    //下一个邻接顶点
     
    int main()
    {
        AMGraph G;                            
        initGraph(G);
        createGraph(G);
        showGraph(G);
        cout << "the result of dfs is:";
        dfsAM(G,0);
        cout << endl;
        cout << "the result of bfs is:";
        bfsAM(G,0);
    }
    int initGraph(AMGraph& G)
    {
        cout << "please input some vexnum and arcnum!" << endl;
        cin >> G.vexnum >> G.arcnum;            //输入你想要的顶点数和边数
        cout << "please input data of vex!" << endl;
        for (int i = 0; i < G.vexnum; i++)
        {
            cin >>G.vexs[i];            //输入顶点数据
        }
        
        for (int i = 0; i < G.vexnum; i++)
        {
            for (int j = 0; j < G.vexnum; j++)
            {
                G.arr[i][j] = MAXINT;        //邻接矩阵的初值都为无穷大
            }    
        }
            
        return 1;
    }
    void showGraph(AMGraph G)
    {
        for (int i = 0; i < G.vexnum; i++)
        {
            for (int j = 0; j < G.vexnum; j++)
            {
                if (G.arr[i][j] == MAXINT)    //无穷大弄得更好看点
                    cout << "∞" << " ";
                else
                    cout << " " << G.arr[i][j] << " ";
            }
            cout << endl;
        }
        cout << endl;
    }
     
    int locateVex(AMGraph G, char u)
    {
        for (int i = 0; i < G.vexnum; i++)    
        {
            if (u == G.vexs[i])            //如果u的值和顶点数据匹配,就返回顶点在矩阵中的下标
                return i;
        }
        return -1;
    }
     
    int createGraph(AMGraph& G)
    {
        int i = 0; int j = 0;int w = 0;            //i,j代表顶点下标,w代表权值
        char v1 = 0; char v2 = 0;            //v1,v2为顶点数据
        cout << "please input w of v1 to v2 in graph!" << endl;
        for (int k = 0; k < G.arcnum; k++)
        {
            cin >> v1 >> v2 >> w;            
            i = locateVex(G, v1);            //找到v1在顶点表的下标,并返回赋值给i
            j = locateVex(G, v2);
            G.arr[i][j] = w;
            G.arr[j][i] = G.arr[i][j];        //无向图的矩阵是对称矩阵
        }
     
        cout << endl;
        return 1;
    }
     
    void dfsAM(AMGraph G, int i)
    {//随机选一个顶点下标,这里为0
        cout << G.vexs[i]<<" ";            //输出0下标在顶点表的值    
        visited[i] = 1;                //辅助数组对应下标i的值置为1
        for (int j = 0; j < G.vexnum; j++)
        {
            if (G.arr[i][j] != MAXINT && (!visited[j]))    //只要是邻接的顶点并且没有访问过
            {                        //不然就退回,也是递归结束条件
                dfsAM(G, j);                //递归使用函数
            }
        }
    }
    int initQueue(sqQueue& Q)
    {
        Q.base = (int *)malloc(sizeof(int) * MVNUM);    
        //给base动态分配一个int*类型MVNUM个int大小的一维数组空间
        Q.front = Q.rear = 0;    //队头和对尾下标都置为0
        return 1;
    }
    int enQueue(sqQueue& Q, int i)
    {
        if ((Q.rear + 1) % MVNUM == Q.front)            //队满
            return 0;
        Q.base[Q.rear] = i;                    //先赋值再加
        Q.rear = (Q.rear + 1) % MVNUM;
        return 1;
    }
     
    int deQueue(sqQueue& Q, int &u)
    {
        if (Q.rear == Q.front)                    //队空
            return 0;
        u = Q.base[Q.front];                    //要删的值给u然后再加
        Q.front = (Q.front + 1) % MVNUM;
        return 1;
    }
     
    int firstVEX(AMGraph G, int u)
    {//在邻接矩阵u行0列开始遍历,如果找到不等于无穷的,
    //并且没有访问过的就返回列的下标,否则就返回无穷
        for (int i = 0; i < G.vexnum; i++)        
        {
            if (G.arr[u][i] != MAXINT && visit[i] == 0) 
            {
                return i;
            }
        }
        return MAXINT;
    }
     
    int nextVEX(AMGraph G, int w, int u)
    {//在邻接矩阵u行w+1列开始遍历,如果找到不等于无穷的,
    //并且没有访问过的就返回列的下标,否则就返回无穷
        for (int i = w + 1; i < G.vexnum; i++)
        {
            if (G.arr[u][i] != MAXINT && visit[i] == 0)
            {
                return i;
            }    
        }
        return MAXINT;
    }
     
    void bfsAM(AMGraph G, int i)
    {//随机选一个顶点下标,这里为0
        cout << G.vexs[i] << " ";        //输出i下标在顶点表的值    
        visit[i] = 1;                //辅助数值对应下标i的值置为1
        sqQueue Q;                    
        initQueue(Q);
        enQueue(Q, i);                //i为矩阵中顶点的行下标,让它入队(顶点表的下标和矩阵的列下标,行下标一致,本算法中说谁的下标都一样)
        while (Q.rear != Q.front)        //队不为空
        {
            int u = 0;            //接收矩阵中顶点的行下标,因为是邻接矩阵
            deQueue(Q,u);            //出队并让u接收矩阵中顶点的行下标
            for (int w = firstVEX(G, u); w != MAXINT; w = nextVEX(G, w, u))
            {//注意在一次循环中u不变
                if (!visit[w])
                {
                    cout << G.vexs[w] << " ";
                    visit[w] = 1;
                    enQueue(Q, w);
                }
            }
        }
        
    }
    

    望采纳。

    本回答被题主选为最佳回答 , 对您是否有帮助呢?
    评论
查看更多回答(1条)

报告相同问题?

问题事件

  • 系统已结题 1月6日
  • 已采纳回答 12月29日
  • 请采纳用户回复 12月28日
  • 创建了问题 12月28日

悬赏问题

  • ¥15 BP神经网络控制倒立摆
  • ¥20 要这个数学建模编程的代码 并且能完整允许出来结果 完整的过程和数据的结果
  • ¥15 html5+css和javascript有人可以帮吗?图片要怎么插入代码里面啊
  • ¥30 Unity接入微信SDK 无法开启摄像头
  • ¥20 有偿 写代码 要用特定的软件anaconda 里的jvpyter 用python3写
  • ¥20 cad图纸,chx-3六轴码垛机器人
  • ¥15 移动摄像头专网需要解vlan
  • ¥20 access多表提取相同字段数据并合并
  • ¥20 基于MSP430f5529的MPU6050驱动,求出欧拉角
  • ¥20 Java-Oj-桌布的计算