zwt2726990701 2022-12-28 21:22 采纳率: 33.3%

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

• 写回答

#### 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月6日
• 已采纳回答 12月29日
• 请采纳用户回复 12月28日
• 创建了问题 12月28日

#### 悬赏问题

• ¥15 关于网上一个easyx制作的见缝插针小游戏(c++)
• ¥15 开地址法双散列函数处理碰撞
• ¥15 想问一下这个是什么情况 虚拟机Linux打不开了
• ¥15 联通光猫掉注册了怎么重新注册上去
• ¥15 关于unity开发steamvr程序遇到的问题