无向图邻接表(深度优先算法)
算法 深度 优先 无向 邻接
2023-09-14 09:14:36 时间
#include <iostream>
using namespace std;
#define MaxVertexNum 100// 最大顶点数为100
#define VertexType char//顶点域为字符型
int visited[MaxVertexNum];//标记结点是否被访问过
typedef struct enode//边表中的结点
{
int adjvex;//边表顶点域
struct enode* next;//指针域
}EdgeNode;
typedef struct vnode//顶点表
{
VertexType vertex;//顶点域
EdgeNode* firstedge;//边表头指针
}VertexNode;
typedef struct//邻接表
{
VertexNode vexs[MaxVertexNum];//节点表
int n, e;//顶点数和边数
}ALGraph;
void InsertNode(ALGraph& G, int i, int j)//在边表中插入结点
{
EdgeNode* s;
s = (EdgeNode*)malloc(sizeof(EdgeNode));//生成新边表结点s
s->adjvex = j;//邻接点序号为j
s->next = G.vexs[i].firstedge;
G.vexs[i].firstedge = s;//将新边表结点s插入到顶点Vi的边表头部
}
ALGraph CreateALGraph()//建立邻边表
{
ALGraph G;
int i, j;
cout << "请输入顶点数和边数:\n";
cin >> G.n >> G.e;
cout << "请输入顶点信息:\n";
for (i = 0; i < G.n; i++)//建立有n个顶点的顶点表
{
cin >> G.vexs[i].vertex;//输入顶点
G.vexs[i].firstedge = NULL;//顶点的边表头指针设为空
}
cout << "请输入边的信息(输入格式为:i (空格) j ):\n";
for (int k = 0; k < G.e; k++)//建立邻接表
{
cin >> i >> j;
InsertNode(G, i, j);
InsertNode(G, j, i);
}
return G;
}
void DFSAL(ALGraph G, int i) //以Vi为出发点对图G搜索
{
EdgeNode* p;
cout << G.vexs[i].vertex << " ";//访问顶点Vi
visited[i] = 1;//标记Vi已访问
p = G.vexs[i].firstedge;//取Vi边表的头指针
while (p)//依次搜索Vi的邻接点Vj
{
if (visited[p->adjvex] == 0)//若Vj尚未访问,则以Vj为出发点继续搜索
DFSAL(G, p->adjvex);
p = p->next;//找Vi的下一个邻接点
}
}
void DFSTraverseAL(ALGraph G)
{
int i;
for (i = 0; i < G.n; i++)
visited[i] = 0;//初始化
for (i = 0; i < G.n; i++)
if (visited[i] == 0)
DFSAL(G, i);//Vi未访问过,从Vi开始搜索
}
int main()
{
ALGraph G = CreateALGraph();
cout << "该图的深度优先搜索遍历得到的顶点序列为:";
DFSTraverseAL(G);
system("pause");
return 0;
}
有问题留言
相关文章
- Java实现 蓝桥杯VIP 算法训练 会议中心
- 算法练习之杨辉三角,杨辉三角的第 k 行,买卖股票的最佳时机
- 一步步教你轻松学朴素贝叶斯模型算法Sklearn深度篇3
- 算法工程师<深度学习基础>
- AI公开课:19.05.29 浣军-百度大数据实验室主任《AutoDL 自动化深度学习建模的算法和应用》课堂笔记以及个人感悟
- DL之ANN/DNN: 人工神经网络ANN/DNN深度神经网络算法的简介、应用、经典案例之详细攻略
- DL:深度学习算法(神经网络模型集合)概览之《THE NEURAL NETWORK ZOO》的中文解释和感悟(六)
- Java 地下迷宫·算法·(ACM/蓝桥杯)·递归解法
- 华为云文字识别深层算法突破 助力复产复工
- 基于深度学习网络的5G通信链路信道估计算法matlab仿真
- 【ML】机器学习中的十大深度学习算法
- 一种基于收敛因子改进的灰狼优化算法 -附代码
- 【经典视觉算法推荐】Focal Loss 论文公式推导及主要贡献
- SQLFlow深度解析——含源码分析,商用存疑点:(1)RPC获取sql db数据,然后在引擎中计算AI部分(2)无监督算法(聚类、IForest)不支持,当前仅autoencoder
- 基于深度学习的目标检测算法:SSD——常见的目标检测算法
- DDos攻击,使用深度学习中 栈式自编码的算法
- 深度学习之语义分割算法(入门学习)
- 刷题记录:牛客NC17508指纹锁(基于学习算法对部分重载运算符进行个人理解)
- 深度解剖(4):DNN反向传播-bp算法,矩阵偏导传递
- m基于FPGA的RGB转ycrcb颜色空间转换算法实现,包含testbench,对比三种转换方法