关淳 2022-11-25 00:52 采纳率: 73.9%
浏览 31
已结题

如何用邻接矩阵存储结构求无向图中两个点的所有路径

不是很会代码写的也不对,谢谢看看

1


#include <bits/stdc++.h>
#define Infinity 32766
#define MaxVertexNum 50
using namespace std;   

//图的邻接矩阵存储结 AdjacencyMatrixGraph
typedef struct AMGraph {
    char vex[MaxVertexNum]; //结点名表 
    int arc[MaxVertexNum][MaxVertexNum]; //边表 
    int vexnum, arcnum; //结点数和边数 
}AMGraph;

int FindVex (AMGraph G, char v)
{
    for (int i = 0; i < G.vexnum; i++)
    {
        if (G.vex[i] == v)
        return i;
    }
return -1;    
}

//无向图 
void GraphCreate (AMGraph &G)
{
    //输入结点数,边数,结点序列 
    cin >> G.vexnum >> G.arcnum;
    for (int i = 0; i < G.vexnum; i++)
        cin >> G.vex[i];
    //初始化
    for (int i = 0; i < G.vexnum; i++)
    for (int j = 0; j < G.vexnum; j++)
    G.arc[i][j] = 0;    
    //构造邻接矩阵 
    char v1, v2;
    for (int k = 0; k < G.arcnum; k++)
    {
        cin >> v1 >> v2;
        int i = FindVex (G, v1);
        int j = FindVex (G, v2);
        G.arc[i][j] = G.arc[j][i] = 1;        
    }      
}

int visited[MaxVertexNum] = {0};
vector <int> v;
//基于DFS查找图中所有路径 
void AllPathDFS (AMGraph G, int StartV, int EndV)
{
    visited[StartV] = 1;
    v.push_back (StartV);
    for (int j = 0; j < G.vexnum; j++)
    {
        if (StartV == EndV)
        {    
            for (int k = 0; k < v.size(); k++)
            {
                cout << G.vex[v[k]] << " ";
            }
            puts (""); 
            v.pop_back ();
            visited[StartV] = 0;
            break;
        }
        
        if (visited[j] == 0 && G.arc[StartV][j] == 1)
           AllPathDFS (G, j, EndV);
        
    }
}

int main ()
{
    AMGraph G;
    GraphCreate (G);
    AllPathDFS (G, 0, G.vexnum - 1);
return 0;
}

用DFS实现所有路径的查找

样例
4 5
ABCD
AB
AD
BC
BD
CD

  • 写回答

1条回答 默认 最新

  • WaitIKnowYou 2022-11-25 10:58
    关注

    DFS

    
    #include <vector>
    class MyGraph
    {
    protected:
        int vertexNum;//顶点数量
        bool** matrix;//邻接矩阵
        bool* visitedFlag;//顶点是否访问过的标记
        std::vector<int> pathStack;//记录路径的栈
    public:
        MyGraph(int VertexNum);
        MyGraph();
        void printMatrix();//输出邻接矩阵
        void updateMatrix(int row,int column);//更新row行column列的邻接矩阵值
        bool getMatrixValue(int row, int column);//获取邻接矩阵中对应行列号的值
        void getPathofTwoNode(int startNode,int endNode);//计算两个节点之间的所有路径
        void findPath(int startNode, int endNode);
        ~MyGraph();
    };
    
    #include "MyGraph.h"
    #include <iostream>
    using namespace std;
     
    MyGraph::MyGraph(int VertexNum)
    {
        this->vertexNum = VertexNum;
        //开辟访问标记数组
        this->visitedFlag = new bool[vertexNum];
        //开辟邻接矩阵
        this->matrix = new bool*[vertexNum];
        for (int i=0;i<vertexNum;i++)
        {
            this->visitedFlag[i] = false;
            this->matrix[i] = new bool[vertexNum];
            //将所有数组元素全部初始化为0
            for(int j=0;j<vertexNum;j++)
                this->matrix[i][j] = 0;
        }
    }
     
    /**
     * 无参数构造函数,通过createTestData函数来构造一个邻接矩阵测试数据
     * 方便其他算法的测试
     */
    MyGraph::MyGraph()
    {
        this->vertexNum = 5;
        //开辟访问标记数组
        this->visitedFlag = new bool[vertexNum];
        //开辟邻接矩阵
        this->matrix = new bool*[vertexNum];
        for (int i = 0; i<vertexNum; i++)
        {
            this->matrix[i] = new bool[vertexNum];
            this->visitedFlag[i] = false;
            //将所有数组元素全部初始化为0
            for (int j = 0; j<vertexNum; j++)
                this->matrix[i][j] = 0;
        }
        //初始化邻接矩阵
        bool initMatrix[5][5] = {
            {0,1,1,0,1},
            {1,0,1,0,0},
            {1,1,0,1,1},
            {0,0,1,0,0},
            {1,0,1,0,0}};
        //赋值
        for (int i = 0; i < vertexNum; i++)
            for (int j = 0; j < vertexNum; j++)
                this->matrix[i][j] = initMatrix[i][j];
        printMatrix();
    }
     
     
    MyGraph::~MyGraph()
    {
        for(int i=0;i<vertexNum;i++)
            delete[] matrix[i];
        delete matrix;
        delete[]visitedFlag;
    }
     
    /**
     * 输出邻接矩阵
     */
    void MyGraph::printMatrix()
    {
        for (int i=0;i<vertexNum;i++)
        {
            for (int j = 0; j < vertexNum; j++)
                cout << matrix[i][j]<<"  ";
            cout << endl;
        }
    }
     
    /**
     * 更新row行column列的邻接矩阵值
     */
    void MyGraph::updateMatrix(int row, int column)
    {
        //由于是无向图,故更新后的矩阵值是一个对称矩阵
        matrix[row][column] = true;
        matrix[column][row] = true;
    }
     
    /**
     * 获取row行column列的邻接矩阵的值
     */
    bool MyGraph::getMatrixValue(int row, int column)
    {
        return this->matrix[row][column];
    }
     
    /**
     * 计算两个节点之间的所有路径
     */
    void MyGraph::getPathofTwoNode(int startNode, int endNode)
    {
        //利用深度优先遍历的方式来计算两个节点之间的所有路径
        visitedFlag[startNode] = true;
        pathStack.push_back(startNode);
        findPath(startNode, endNode);
    }
     
    void MyGraph::findPath(int startNode, int endNode)
    {
        if (startNode == endNode)
        {
            //找到一条路径,输出路径
            cout << "找到一条路径";
            for (int node : pathStack)
                cout << node << "  ";
            cout << endl;
            visitedFlag[*(pathStack.end()-1)] = false;
            pathStack.pop_back();
            return;
        }
        else
        {
            //找到startNode所有没有入栈的邻接点
            int unStackedNum = 0;
             for (int i = 0; i<vertexNum; i++)
            {
                if (matrix[startNode][i] && !visitedFlag[i])
                {
                    unStackedNum++;
                    visitedFlag[i] = true;
                    pathStack.push_back(i);
                    findPath(i, endNode);
                }
            }
            visitedFlag[*(pathStack.end() - 1)] = false;
            pathStack.pop_back();
        }
    }
    
    
    本回答被题主选为最佳回答 , 对您是否有帮助呢?
    评论

报告相同问题?

问题事件

  • 系统已结题 12月3日
  • 已采纳回答 11月25日
  • 修改了问题 11月25日
  • 修改了问题 11月25日
  • 展开全部

悬赏问题

  • ¥150 寻找王者荣耀开发作者,合作或者解答
  • ¥15 关于cpci总线的几个问题,有点迷糊
  • ¥15 乳腺癌数据集 相关矩阵 特征选择
  • ¥15 我的游戏账号被盗取,请问我该怎么做
  • ¥15 通关usb3.0.push文件,导致usb频繁断连
  • ¥15 有没有能解决微信公众号,只能实时拍照,没有选择相册上传功能,我不懂任何技术,,有没有给我发个软件就能搞定的方法
  • ¥15 Pythontxt文本可视化
  • ¥15 如何基于Ryu环境下使用scapy包进行数据包构造
  • ¥15 springboot国际化
  • ¥15 搭建QEMU环境运行OP-TEE出现错误