数据结构与算法-图

图

  • 🎈2.图的存储结构
      • 📖2.4.2邻接表的存储
        • ✅2.4.2.1逆邻接表
        • ✅2.4.2.2邻接表存储结构的定义
        • ✅2.4.2.3邻接表存储结构的类定义
        • ✅2.4.2.4创建n个顶点m条边的无向网
        • ✅2.4.2.5创建n个顶点m条边的有向网
        • ✅2.4.2.6定位操作-查找定点信息在顶点数组中的下标
        • ✅2.4.2.7计算顶点的度数-以无向网为例
        • ✅2.4.2.8插入操作-以无向网为例
  • 🎈3.图的遍历
    • 🔭3.1深度优先搜索
      • 📖3.1.1深度优先搜索算法（邻接表存储）
    • 🔭3.2广度优先搜索
      • 📖3.2.1广度优先搜索算法（邻接表存储）
    • 🔭3.3以连通无向图为例进行广度优先搜索和深度优先搜索

🎈2.图的存储结构

📖2.4.2邻接表的存储

在这里插入图片描述

🔎根据邻接表的定义可知，对于n个顶点和e条边的无向图，其邻接表有n个表头结点和2e个边结点。对于n个结点和e条边的有向图，其邻接表有n个表头结点和e个边结点。

✅2.4.2.1逆邻接表

在这里插入图片描述

✅2.4.2.2邻接表存储结构的定义
#define MaxVex 20//自定义最大顶点数
typedef enum 
{DG,UDG,DN,UDN
}GraphKind;//有向图，无向图，有向网，无向网
typedef int VElemType;
typedef struct ArcNode//边结点定义
{int adjvex;//终点（或弧尾）在数组表中的下标int info;///该边（弧）相关信息（权值）ArcNode* nextarc;//存储下一条边（或弧）结点的地址
}ArcNode;
typedef struct//表头结点的定义
{VElemType data;ArcNode* firstarc;//存储第一条依附该顶点的边（或弧）结点地址
}VNode;
typedef struct
{VNode vertices[MaxVex];int vexnum;int arcnum;GraphKind kind;
}AdjLGraph;
✅2.4.2.3邻接表存储结构的类定义
class ALGraph
{
private:AdjLGraph ag;
public:void CreateGraph(int n, int m);//创建n个顶点，m条边的图，以无向网为例int LocateVex(VElemType u);//图中存在顶点u,则返回该顶点在数组中的下标，否则返回-1int Degree(VElemType u);//计算顶点u的度数void InsertArcGraph(VElemType u, VElemType v, int info);//插入一条边void BFS(VElemType v);//以v为初始点的连通分量的广度优先搜索void DFS(VElemType v);//以v为初始点的连通分量的深度优先搜索void BFSTraverse();//图的广度优先搜索void DFSTreverse();//图的深度优先搜索int Connected();//计算连通分量的个数Edge* Kruskal();//Kruskal算法求最小生成树Edge* Prim(VElemTyp u);//prim算法求最小生成树int TopSort();//拓扑排序int CriticalPath();//求关键路径AdjLGraph GetAg(){return ag;//返回私有成员}
};
✅2.4.2.4创建n个顶点m条边的无向网
void ALGraph::CreateGraph(int n, int m)//以无向网为例
{ag.vexnum = n;ag.arcnum = m;ag.kind = UDN;int i, j, w, h, t;VElemType u, v;ArcNode* p;for (i = 0; i < n; i++){cout << "请输入" << n << "个顶点：";cin >> ag.vertices[i].data;ag.vertices[i].firstarc = NULL;}for (j = 0; j < m; j++)//建立边集{cin >> u >> v >> w;//输入一条弧<u,v,w>h = LocateVex(u);t = LocateVex(v);p = new ArcNode;p->adjvex = t;p->info = w;p->nextarc = ag.vertices[h].firstarc;ag.vertices[h].firstarc = p;p = new ArcNode;p->adjvex = h;p->info = w;p->nextarc = ag.vertices[t].firstarc;ag.vertices[t].firstarc = p;}
}
✅2.4.2.5创建n个顶点m条边的有向网
void ALGraph::CreateGraph(int n, int m)
{ag.vexnum = n;ag.arcnum = m;ag.kind = UDN;int i, j, w, h, t;VElemType u, v;ArcNode* p;for (i = 0; i < n; i++){cout << "请输入" << n << "个顶点：";cin >> ag.vertices[i].data;ag.vertices[i].firstarc = NULL;}for (j = 0; j < m; j++)//建立边集{cin >> u >> v >> w;//输入一条弧<u,v,w>h = LocateVex(u);t = LocateVex(v);p = new ArcNode;//<u,v>p->adjvex = t;p->info = w;p->nextarc = ag.vertices[h].firstarc;ag.vertices[h].firstarc = p;}
}
✅2.4.2.6定位操作-查找定点信息在顶点数组中的下标
int ALGraph::LocateVex(VElemType u)
{for (int i = 0; i < ag.vexnum; i++){if (u == ag.vertices[i].data)return i;}return -1;
}
✅2.4.2.7计算顶点的度数-以无向网为例
int ALGraph::Degree(VElemType u)
{int h = LocateVex(u);//结点u的下标int count = 0;ArcNode* p = ag.vertices[h].firstarc;//p指向第h条链表的第一个结点while (p){count++;p = p->nextarc;}return count;
}
✅2.4.2.8插入操作-以无向网为例
void ALGraph::InsertArcGraph(VElemType u, VElemType v, int info)//无向网为例
{int h = LocateVex(u);int t = LocateVex(v);ArcNode* p;if (h == -1){ag.vertices[ag.vexnum].data = u;ag.vertices[ag.vexnum].firstarc = NULL;h = ag.vexnum;ag.vexnum++;}if (t == -1){ag.vertices[ag.vexnum].data = v;ag.vertices[ag.vexnum].firstarc = NULL;t = ag.vexnum;ag.vexnum++;}p = new ArcNode;p->adjvex = t;p->info = info;p->nextarc = ag.vertices[h].firstarc;ag.vertices[h].firstarc = p;p = new ArcNode;p->adjvex = h;p->info = info;p->nextarc = ag.vertices[t].firstarc;ag.vertices[t].firstarc = p;ag.arcnum++;
}

🎈3.图的遍历

在这里插入图片描述

🔭3.1深度优先搜索

✅深度优先搜索类似于树的先序遍历，是树的先序遍历的推广。深度优先搜索是一个不断探查和回溯的过程，具体过程如下：

  1. 从图中某顶点v出发，访问顶点v
  2. 从v的未被访问过的邻接点中选择一个顶点出发，继续对图进行深度优先遍历。若从图中某个顶点出发的所有邻接点都已被访问过，则退回前一个结点继续上述过程，若退回初始点，则以v为初始点的搜索结束。
  3. 若为非连通图，图中尚有未被访问过的顶点，则另选图中一个未曾访问过的顶点作为初始点，重复上述过程，直到图中所有顶点均被访问为止。

❗说明：

  1. 若无向图是连通图，则一次遍历就能访问图中所有的顶点。
  2. 若无向图是非连通图，则只能访问到初始点所在连通分量中的所有顶点，还需要从其他分量中再选择初始点，分别进行遍历才能访问到图中所有顶点。
  3. 对于有向图来说，若从初始点到图中每个顶点都有路径，则一次遍历能够访问图中所有顶点，否则，同样需要在选择初始点继续进行遍历，直到图中所有顶点均被访问为止。

在这里插入图片描述

📖3.1.1深度优先搜索算法（邻接表存储）

int visited[MaxVex];//访问标志数组，初始化所有元素值为0
void ALGraph::DFS(VElemType v)//以v为初始点的连通分量的深度优先搜索算法如下
{ArcNode* p;int h = LocateVex(v);cout << v;//访问该顶点visited[h] = 1;//置访问标记为1for (p = ag.vertices[h].firstarc; p; p = p->nextarc){if (visited[p->adjvex] == 0)DFS(ag.vertices[p->adjvex].data);}
}
void ALGraph::DFSTreverse()//对图作深度优先搜索
{int i;for (i = 0; i < ag.vexnum; i++){visited[i] = 0;//访问标志初始化}for (i = 0; i < ag.vexnum; i++){if (!visited[i])//对尚未访问的顶点调用DFSDFS(ag.vertices[i].data);}
}

🔭3.2广度优先搜索

🔎广度优先搜索类似于树的层次遍历方法，其搜索过程如下：

  1. 访问初识顶点v
  2. 访问与v相邻的所有未被访问的邻接点w1,w2,w3…wk
  3. 依次从这些邻接点出发，访问它们的所有未被访问的邻接点。
  4. 依次类推，直到连通图中所有访问过的顶点的邻接点都被访问。
  5. 若为非连通图，图中尚有未被访问过的顶点，则另选图中的一个未曾访问过的顶点作为初始点，重复上述过程，直到图中所有顶点均被访问过为止。

在这里插入图片描述

📖3.2.1广度优先搜索算法（邻接表存储）

void ALGraph::BFS(VElemType v)//以v为初始点的连通分量的广度优先搜索
{int h = LocateVex(v);ArcNode* p;LinkQueue lq;lq.DeQueue(h);visited[h] = 1;while (!lq.EmptyQueue()){lq.DeQueue(h);cout << ag.vertices[h].data;for (p = ag.vertices[h].firstarc; p; p = p->nextarc){if (!visited[p->adjvex]){lq.EnQueue(p->adjvex);visited[p->adjvex] = 1;}}}
}
void ALGraph::BFSTraverse()
{int i;for (i = 0; i < ag.vexnum; i++){visited[i] = 0;}for (i = 0; i < ag.vexnum; i++){if (!visited[i])BFS(ag.vertices[i].data);}
}

🔭3.3以连通无向图为例进行广度优先搜索和深度优先搜索

#define _CRT_SECURE_NO_WARNINGS 1
#include <iostream>
#include <queue>
using namespace std;
#define MaxVex 20//自定义最大顶点数
typedef char VElemType;
typedef struct ArcNode//边结点定义
{int adjvex;//终点（或弧尾）在数组表中的下标int info;///该边（弧）相关信息（权值）ArcNode* nextarc;//存储下一条边（或弧）结点的地址
}ArcNode;
typedef struct//表头结点的定义
{VElemType data;ArcNode* firstarc;//存储第一条依附该顶点的边（或弧）结点地址
}VNode;
typedef struct
{VNode vertices[MaxVex];int vexnum;int arcnum;
}AdjLGraph;
class ALGraph
{
private:AdjLGraph ag;
public:void CreateGraph(int n, int m);//创建n个顶点，m条边的图，以无向网为例int LocateVex(VElemType u);//图中存在顶点u,则返回该顶点在数组中的下标，否则返回-1int Degree(VElemType u);//计算顶点u的度数void InsertArcGraph(VElemType u, VElemType v, int info);//插入一条边void BFS(VElemType v);//以v为初始点的连通分量的广度优先搜索void DFS(VElemType v);//以v为初始点的连通分量的深度优先搜索void BFSTraverse();//图的广度优先搜索void DFSTreverse();//图的深度优先搜索AdjLGraph GetAg(){return ag;//返回私有成员}
};
void ALGraph::CreateGraph(int n, int m)//以无向网为例
{ag.vexnum = n;ag.arcnum = m;int i, j, w, h, t;VElemType u, v;ArcNode* p;cout << "请输入" << n << "个顶点：";for (i = 0; i < n; i++){cin >> ag.vertices[i].data;ag.vertices[i].firstarc = NULL;}cout << "请输入" << m << "条边（u,v,w):" << endl;for (j = 0; j < m; j++)//建立边集{cin >> u >> v >> w;//输入一条弧<u,v,w>h = LocateVex(u);t = LocateVex(v);p = new ArcNode;//<u,v>p->adjvex = t;p->info = w;p->nextarc = ag.vertices[h].firstarc;ag.vertices[h].firstarc = p;p = new ArcNode;//<v,u>p->adjvex = h;p->info = w;p->nextarc = ag.vertices[t].firstarc;ag.vertices[t].firstarc = p;}
}
int ALGraph::LocateVex(VElemType u)
{for (int i = 0; i < ag.vexnum; i++){if (u == ag.vertices[i].data)return i;}return -1;
}
int ALGraph::Degree(VElemType u)
{int h = LocateVex(u);//结点u的下标int count = 0;ArcNode* p = ag.vertices[h].firstarc;//p指向第h条链表的第一个结点while (p){count++;p = p->nextarc;}return count;
}
void ALGraph::InsertArcGraph(VElemType u, VElemType v, int info)//无向网为例
{int h = LocateVex(u);int t = LocateVex(v);ArcNode* p;if (h == -1){ag.vertices[ag.vexnum].data = u;ag.vertices[ag.vexnum].firstarc = NULL;h = ag.vexnum;ag.vexnum++;}if (t == -1){ag.vertices[ag.vexnum].data = v;ag.vertices[ag.vexnum].firstarc = NULL;t = ag.vexnum;ag.vexnum++;}p = new ArcNode;p->adjvex = t;p->info = info;p->nextarc = ag.vertices[h].firstarc;ag.vertices[h].firstarc = p;p = new ArcNode;p->adjvex = h;p->info = info;p->nextarc = ag.vertices[t].firstarc;ag.vertices[t].firstarc = p;ag.arcnum++;
}
int visited[MaxVex];//访问标志数组，初始化所有元素值为0
void ALGraph::DFS(VElemType v)//以v为初始点的连通分量的深度优先搜索算法如下
{ArcNode* p;int h = LocateVex(v);cout << v;//访问该顶点visited[h] = 1;//置访问标记为1for (p = ag.vertices[h].firstarc; p; p = p->nextarc){if (visited[p->adjvex] == 0)DFS(ag.vertices[p->adjvex].data);}
}
void ALGraph::DFSTreverse()//对图作深度优先搜索
{cout << "深度优先搜索的序列为：";int i;for (i = 0; i < ag.vexnum; i++){visited[i] = 0;//访问标志初始化}for (i = 0; i < ag.vexnum; i++){if (!visited[i])//对尚未访问的顶点调用DFSDFS(ag.vertices[i].data);}cout << endl;
}
void ALGraph::BFS(VElemType v)//以v为初始点的连通分量的广度优先搜索
{int h = LocateVex(v);ArcNode* p;queue<VElemType> lq;lq.push(h);visited[h] = 1;while (!lq.empty()){h = lq.front();lq.pop();cout << ag.vertices[h].data;for (p = ag.vertices[h].firstarc; p; p = p->nextarc){if (!visited[p->adjvex]){lq.push(p->adjvex);visited[p->adjvex] = 1;}}}
}
void ALGraph::BFSTraverse()
{cout << "广度优先搜索的序列为：";int i;for (i = 0; i < ag.vexnum; i++){visited[i] = 0;}for (i = 0; i < ag.vexnum; i++){if (!visited[i])BFS(ag.vertices[i].data);}cout << endl;
}
int main()
{ALGraph p;p.CreateGraph(8, 9);p.BFSTraverse();p.DFSTreverse();return 0;
}

✅运行示例：
在这里插入图片描述

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：http://www.rhkb.cn/news/197630.html

如若内容造成侵权/违法违规/事实不符，请联系长河编程网进行投诉反馈email:809451989@qq.com，一经查实，立即删除！

相关文章

3GPP协议解读（一）_23.501_23.502_PDU Session_SMF与UDP的交互

3GPP协议解读（一）_23.501_23.502_PDU Session_SMF与UDP的交互

UE发起计算服务申请后&#xff0c;网络侧处理的流程 UE发起服务的流程&#xff1a;service request网络侧处理服务涉及的通信数据通过PDU Session进行传输&#xff0c;涉及到SMF与UPF的交互。PDU Session的建立、管理全部由SMF&#xff08;Session Management Function&#x…
阅读更多...
【uniapp】 video视频层级、遮挡其他弹窗或顶部导航 使用nvue覆盖

【uniapp】 video视频层级、遮挡其他弹窗或顶部导航 使用nvue覆盖

uniapp 顶部导航和弹窗被video遮挡解决办法 第一步&#xff1a;配置 subNVues {"path": "pages/index/index","style": {"navigationBarTitleText": "uni-app","navigationStyle": "custom","app-…
阅读更多...
SQL零基础入门教程，贼拉详细！贼拉简单！ 速通数据库期末考！（八）

SQL零基础入门教程，贼拉详细！贼拉简单！ 速通数据库期末考！（八）

FULL OUTER JOIN 除了前面讲到的 INNER JOIN&#xff08;内连接&#xff09;、LEFT JOIN&#xff08;左连接&#xff09;、RIGHT JOIN&#xff08;右连接&#xff09;&#xff0c;还有另外一种关联方式&#xff0c;即 FULL OUTER JOIN&#xff08;全外连接&#xff09; FULL O…
阅读更多...
Javaweb之Vue指令案例的详细解析

Javaweb之Vue指令案例的详细解析

2.3.5 案例 需求&#xff1a; 如上图所示&#xff0c;我们提供好了数据模型&#xff0c;users是数组集合&#xff0c;提供了多个用户信息。然后我们需要将数据以表格的形式&#xff0c;展示到页面上&#xff0c;其中&#xff0c;性别需要转换成中文男女&#xff0c;等级需要…
阅读更多...
java游戏制作-拼图游戏

java游戏制作-拼图游戏

一.制作主界面 首先创建一个Java项目命名为puzzlegame。 再在src中创建一个包&#xff0c;用来制作主界面 代码&#xff1a; 结果&#xff1a; 二.设置界面 代码&#xff1a; 三.初始化界面 代码&#xff1a; 优化代码&#xff1a; 结果&#xff1a; 四.添加图片 先在Java项…
阅读更多...
HDFS、MapReduce原理--学习笔记

HDFS、MapReduce原理--学习笔记

1.Hadoop框架 1.1框架与Hadoop架构简介 &#xff08;1&#xff09;广义解释 从广义上来说&#xff0c;随着大数据开发技术的快速发展与逐步成熟&#xff0c;在行业里&#xff0c;Hadoop可以泛指为&#xff1a;Hadoop生态圈。 也就是说&#xff0c;Hadoop指的是大数据生态圈整…
阅读更多...
机器学习的医疗乳腺癌数据的乳腺癌疾病预测

机器学习的医疗乳腺癌数据的乳腺癌疾病预测

项目视频讲解：基于机器学习的医疗乳腺癌数据的乳腺癌疾病预测 完整代码数据分享_哔哩哔哩_bilibili 效果演示： 代码： #第一步！导入我们需要的工具 import numpy as np import pandas as pd import matplotlib.pyplot as plt import seaborn as sns %matplotlib inlin…
阅读更多...
Postman实现接口的加密和解密

Postman实现接口的加密和解密

近期在复习Postman的基础知识&#xff0c;在小破站上跟着百里老师系统复习了一遍&#xff0c;也做了一些笔记&#xff0c;希望可以给大家一点点启发。 1、目前市面上的加密的方式 对称式加密&#xff1a;DES&#xff0c;AES&#xff0c;Base64加密算法 非对称加密&#xff1a…
阅读更多...
跟随鼠标的粒子特效分享

跟随鼠标的粒子特效分享

前些天发现了一个巨牛的人工智能学习网站，通俗易懂，风趣幽默，忍不住分享一下给大家。点击跳转到网站。 广告打完，我们进入正题，先看效果： 上代码： html, body {padding: 0;margin: 0;overflow: hidden; }import * as PIXI from https://cdn.skypack.dev/pixi.js@7.2.…
阅读更多...
若依启动步骤

若依启动步骤

1.创建数据库 2.启动redis 3.改后端的数据库连接配置 4.配置redis redis的地址&#xff1a;cmd中ipconfig命令查看 6.启动后端&#xff1a;如下 7.启动前端ruoyi-ui中 先运行npm install&#xff0c;再npm run dev。项目就启动成功了。 用户名&#xff1a;admin 密码&#x…
阅读更多...
C#入门（1）：程序结构、数据类型

C#入门（1）：程序结构、数据类型

一、C#程序结构 第一个C#程序 using System;namespace base_01 {class Program{#region 代码折叠块static void Main(string[] args){//控制台输出Console.WriteLine("Hello World!");Console.Write("C#是微软的编程语言"); //不换行输出//Console.Rea…
阅读更多...
蓝桥杯 map

蓝桥杯 map

map 代码示例 #include<iostream> #include<map> using namespace std; int main(){//创建并初始化mapmap<int,string> myMap{{1,"Apple"},{2,"Banana"},{3,"Orange"}} ;//插入元素myMap.insert(make_pair(4,"Grapes&qu…
阅读更多...
神经网络常见评价指标AUROC（AUC-ROC）、AUPR（AUC-PR）

神经网络常见评价指标AUROC（AUC-ROC）、AUPR（AUC-PR）

神经网络的性能可以通过多个评价指标进行衡量&#xff0c;具体选择哪些指标取决于任务的性质。以下是神经网络中常见的评价指标&#xff1a; 准确性&#xff08;Accuracy&#xff09;&#xff1a; 准确性是最常见的分类任务评价指标&#xff0c;表示模型正确预测的样本数占总样…
阅读更多...
资深测试总结，现在软件测试有未来吗？“你“的底气在哪里？

资深测试总结，现在软件测试有未来吗？“你“的底气在哪里？

目录&#xff1a;导读 前言一、Python编程入门到精通二、接口自动化项目实战三、Web自动化项目实战四、App自动化项目实战五、一线大厂简历六、测试开发DevOps体系七、常用自动化测试工具八、JMeter性能测试九、总结&#xff08;尾部小惊喜&#xff09; 前言 1、为什么会有 “…
阅读更多...
3DMAX森林树木植物插件ForestPackLite教程

3DMAX森林树木植物插件ForestPackLite教程

3DMAX森林树木植物插件ForestPackLite教程 Forest Pack是世界上最受欢迎的散布插件。它提供了一个完整的解决方案来创建大面积的物体&#xff0c;从树木和植物到建筑、人群、骨料、地面覆盖物、岩石等等。如果你能为它建模&#xff0c;森林包就能把它分散开来。 无数工作室依靠…
阅读更多...
计算机毕业设计选题推荐-高校后勤报修微信小程序/安卓APP-项目实战

计算机毕业设计选题推荐-高校后勤报修微信小程序/安卓APP-项目实战

✨作者主页&#xff1a;IT研究室✨ 个人简介&#xff1a;曾从事计算机专业培训教学&#xff0c;擅长Java、Python、微信小程序、Golang、安卓Android等项目实战。接项目定制开发、代码讲解、答辩教学、文档编写、降重等。 ☑文末获取源码☑ 精彩专栏推荐⬇⬇⬇ Java项目 Python…
阅读更多...
月子会所信息展示服务预约小程序的作用是什么

月子会所信息展示服务预约小程序的作用是什么

传统线下门店经营只依赖自然流量咨询或简单的线上付费推广是比较低效的&#xff0c;属于靠“天”吃饭&#xff0c;如今的年轻人学历水平相对较高&#xff0c;接触的事物或接受的思想也更多更广&#xff0c;加之生活水平提升及互联网带来的长期知识赋能&#xff0c;因此在寻找/咨…
阅读更多...
Adversarially Robust Neural Architecture Search for Graph Neural Networks

Adversarially Robust Neural Architecture Search for Graph Neural Networks

Adversarially Robust Neural Architecture Search for Graph Neural Networks----《面向图神经网络的对抗鲁棒神经架构搜索》 摘要 图神经网络&#xff08;GNN&#xff09;在关系数据建模方面取得了巨大成功。尽管如此&#xff0c;它们仍然容易受到对抗性攻击&#xff0c;这对…
阅读更多...
2023年亚太杯数学建模思路 - 案例：异常检测

2023年亚太杯数学建模思路 - 案例：异常检测

文章目录 赛题思路一、简介 -- 关于异常检测异常检测监督学习 二、异常检测算法2. 箱线图分析3. 基于距离/密度4. 基于划分思想 建模资料 赛题思路 &#xff08;赛题出来以后第一时间在CSDN分享&#xff09; https://blog.csdn.net/dc_sinor?typeblog 一、简介 – 关于异常…
阅读更多...
10、背景分离 —— 大津算法

10、背景分离 —— 大津算法

上一节学习了通过一些传统计算机视觉算法，比如Canny算法来完成一个图片的边缘检测，从而可以区分出图像的边缘。 今天再看一个视觉中更常见的应用，那就是把图片的前景和背景的分离。 前景和背景 先看看什么是前景什么是背景。 在图像处理和计算机视觉中，"前景"…
阅读更多...
最新文章
推荐文章

Copyright @ 2022~2023