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

1

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

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

``````

4 5
ABCD
AB
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日
• 展开全部

#### 悬赏问题

• ¥15 如何输入百度，显示本地下载的html文件页面，地址栏还显示百度的地址
• ¥15 通过kinect制作换装程序但是服装不贴合(标签-ar)
• ¥20 matlab如何绘制三维瀑布图
• ¥15 关于用abap来解决动态规划的问题，但是要求输出索引值，这个是难点
• ¥15 在ISIS中什么是IP从地址
• ¥15 压测时，并发量过高时，响应时间出现尖刺
• ¥15 关于vmprotect3.8.4虚拟文件一项
• ¥15 在不用IT调试的情况下怎样能连外网
• ¥20 C#调用虚拟键盘TabTip.exe
• ¥15 Qt4代码实现下面的界面