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

Question

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

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

Answer 1

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();
    }
}