图的学习，深度和广度遍历

一、什么是图

表示“多对多”的关系
包括：

  • 一组顶点：通常用V（Vertex）表示顶点集合
  • 一组边：通常用E（Edge）表示边的集合
    • 边是顶点对：(v, w)∈E，其中v,w∈V
    • 有向边<v, w>表示从v指向w的边（单行线）
    • 不考虑重边和自回路

在这里插入图片描述
在这里插入图片描述

二、抽象数据类型定义

  • 类型名称：图（Graph）
  • 数据对象集：G（V, E）由一个非空的有限顶点集合v和一个有限边集合E组成。
  • 操作集：对于任意图G ∈ Graph， 以及v ∈ V， e ∈ E
    • Graph Create()：建立并返回空图；
    • Graph InsertVertex(Graph G, Vertex v)：将v插入G；
    • Graph InsertEdge(Graph G, Edge e)：将e插入G；
    • void DFS(Graph G, Vertex v)：从顶点v出发深度优先遍历图G；
    • void BFS(Graph G, Vertex v)：从顶点v触发宽度优先遍历图G；
    • void ShortestPath(Graph G, Vertex v, int Dist[])：计算图G中顶点v到任一其他顶点的最短距离；
    • void MST(Graph G)：计算图G的最小生成树；
    • …
  • 数据结构中对于稀疏图的定义为：有很少条边或弧（边的条数|E|远小于|V|²）的图称为稀疏图（sparse graph），反之边的条数|E|接近|V|²，称为稠密图（dense graph）。

如何表示图：
在这里插入图片描述

/* 图的邻接矩阵表示法 */#define MaxVertexNum 100    /* 最大顶点数设为100 */#define INFINITY 65535        /* ∞设为双字节无符号整数的最大值65535*/typedef int Vertex;         /* 用顶点下标表示顶点,为整型 */typedef int WeightType;        /* 边的权值设为整型 */typedef char DataType;        /* 顶点存储的数据类型设为字符型 *//* 边的定义 */typedef struct ENode *PtrToENode;struct ENode{Vertex V1, V2;      /* 有向边<V1, V2> */WeightType Weight;  /* 权重 */};typedef PtrToENode Edge;/* 图结点的定义 */typedef struct GNode *PtrToGNode;struct GNode{int Nv;  /* 顶点数 */int Ne;  /* 边数   */WeightType G[MaxVertexNum][MaxVertexNum]; /* 邻接矩阵 */DataType Data[MaxVertexNum];      /* 存顶点的数据 *//* 注意：很多情况下，顶点无数据，此时Data[]可以不用出现 */};typedef PtrToGNode MGraph; /* 以邻接矩阵存储的图类型 */MGraph CreateGraph( int VertexNum ){ /* 初始化一个有VertexNum个顶点但没有边的图 */Vertex V, W;MGraph Graph;Graph = (MGraph)malloc(sizeof(struct GNode)); /* 建立图 */Graph->Nv = VertexNum;Graph->Ne = 0;/* 初始化邻接矩阵 *//* 注意：这里默认顶点编号从0开始，到(Graph->Nv - 1) */for (V=0; V<Graph->Nv; V++)for (W=0; W<Graph->Nv; W++)  Graph->G[V][W] = INFINITY;return Graph; }void InsertEdge( MGraph Graph, Edge E ){/* 插入边 <V1, V2> */Graph->G[E->V1][E->V2] = E->Weight;    /* 若是无向图，还要插入边<V2, V1> */Graph->G[E->V2][E->V1] = E->Weight;}MGraph BuildGraph(){MGraph Graph;Edge E;Vertex V;int Nv, i;scanf("%d", &Nv);   /* 读入顶点个数 */Graph = CreateGraph(Nv); /* 初始化有Nv个顶点但没有边的图 */ scanf("%d", &(Graph->Ne));   /* 读入边数 */if ( Graph->Ne != 0 ) { /* 如果有边 */ E = (Edge)malloc(sizeof(struct ENode)); /* 建立边结点 */ /* 读入边，格式为"起点 终点 权重"，插入邻接矩阵 */for (i=0; i<Graph->Ne; i++) {scanf("%d %d %d", &E->V1, &E->V2, &E->Weight); /* 注意：如果权重不是整型，Weight的读入格式要改 */InsertEdge( Graph, E );}} /* 如果顶点有数据的话，读入数据 */for (V=0; V<Graph->Nv; V++) scanf(" %c", &(Graph->Data[V]));return Graph;}

领接表：G[N]为指针数组，对应矩阵每行一个链表，只存非0元素。

对于网络，结构中要增加权重的域。

   /* 图的邻接表表示法 */#define MaxVertexNum 100    /* 最大顶点数设为100 */typedef int Vertex;         /* 用顶点下标表示顶点,为整型 */typedef int WeightType;        /* 边的权值设为整型 */typedef char DataType;        /* 顶点存储的数据类型设为字符型 *//* 边的定义 */typedef struct ENode *PtrToENode;struct ENode{Vertex V1, V2;      /* 有向边<V1, V2> */WeightType Weight;  /* 权重 */};typedef PtrToENode Edge;/* 邻接点的定义 */typedef struct AdjVNode *PtrToAdjVNode; struct AdjVNode{Vertex AdjV;        /* 邻接点下标 */WeightType Weight;  /* 边权重 */PtrToAdjVNode Next;    /* 指向下一个邻接点的指针 */};/* 顶点表头结点的定义 */typedef struct Vnode{PtrToAdjVNode FirstEdge;/* 边表头指针 */DataType Data;            /* 存顶点的数据 *//* 注意：很多情况下，顶点无数据，此时Data可以不用出现 */} AdjList[MaxVertexNum];    /* AdjList是邻接表类型 *//* 图结点的定义 */typedef struct GNode *PtrToGNode;struct GNode{  int Nv;     /* 顶点数 */int Ne;     /* 边数   */AdjList G;  /* 邻接表 */};typedef PtrToGNode LGraph; /* 以邻接表方式存储的图类型 */LGraph CreateGraph( int VertexNum ){ /* 初始化一个有VertexNum个顶点但没有边的图 */Vertex V;LGraph Graph;Graph = (LGraph)malloc( sizeof(struct GNode) ); /* 建立图 */Graph->Nv = VertexNum;Graph->Ne = 0;/* 初始化邻接表头指针 *//* 注意：这里默认顶点编号从0开始，到(Graph->Nv - 1) */for (V=0; V<Graph->Nv; V++)Graph->G[V].FirstEdge = NULL;return Graph; }void InsertEdge( LGraph Graph, Edge E ){PtrToAdjVNode NewNode;/* 插入边 <V1, V2> *//* 为V2建立新的邻接点 */NewNode = (PtrToAdjVNode)malloc(sizeof(struct AdjVNode));NewNode->AdjV = E->V2;NewNode->Weight = E->Weight;/* 将V2插入V1的表头 */NewNode->Next = Graph->G[E->V1].FirstEdge;Graph->G[E->V1].FirstEdge = NewNode;/* 若是无向图，还要插入边 <V2, V1> *//* 为V1建立新的邻接点 */NewNode = (PtrToAdjVNode)malloc(sizeof(struct AdjVNode));NewNode->AdjV = E->V1;NewNode->Weight = E->Weight;/* 将V1插入V2的表头 */NewNode->Next = Graph->G[E->V2].FirstEdge;Graph->G[E->V2].FirstEdge = NewNode;}LGraph BuildGraph(){LGraph Graph;Edge E;Vertex V;int Nv, i;scanf("%d", &Nv);   /* 读入顶点个数 */Graph = CreateGraph(Nv); /* 初始化有Nv个顶点但没有边的图 */ scanf("%d", &(Graph->Ne));   /* 读入边数 */if ( Graph->Ne != 0 ) { /* 如果有边 */ E = (Edge)malloc( sizeof(struct ENode) ); /* 建立边结点 */ /* 读入边，格式为"起点 终点 权重"，插入邻接矩阵 */for (i=0; i<Graph->Ne; i++) {scanf("%d %d %d", &E->V1, &E->V2, &E->Weight); /* 注意：如果权重不是整型，Weight的读入格式要改 */InsertEdge( Graph, E );}} /* 如果顶点有数据的话，读入数据 */for (V=0; V<Graph->Nv; V++) scanf(" %c", &(Graph->G[V].Data));return Graph;}

其中

typedef struct Vnode{PtrToAdjVNode FirstEdge;/* 边表头指针 */DataType Data;            /* 存顶点的数据 *//* 注意：很多情况下，顶点无数据，此时Data可以不用出现 */
} AdjList[MaxVertexNum];    /* AdjList是邻接表类型 *///AdjList是一个Vnode为元素的数组的别名

图的度是和顶点相关联的边的数目

三、图的遍历

3.1 深度优先算法

在这里插入图片描述
邻接表

/* 邻接表存储的图 - DFS*/void Visit(Vertex V)
{printf("Now visit Vertex %d\n", V);
}/* Visited[]为全局变量，已经初始化false */
void DFS(LGraph Graph, Vertex V, void (*Visit)(Vertex))
{   /* 以V为出发点对邻接表存储的图Graph进行DFS搜索 */PtrToAdjVNode W;Visit(V);   /* 访问第V个顶点 */Visited[V] = true;  /* 标记V已访问 */for(W=Graph->G[V].FirstEdge;W;W=W->Next)    /* 对V的每个邻接点W->AdjV */if(!Visited[W->AdjV])       /* 若W->AdjV未被访问 */DFS(Graph, W->AdjV, Visit);     /* 则递归访问之 */
}

邻接矩阵

void Visit(Vertex V)
{printf("Now visit Vertex %d\n", V);
}void DFS(MGraph Graph, Vertex V, int *Visited)
{Vertex W;Visit(V);Visited[V] = 1;         //已访问for(W=0;W<Graph->Nv;W++)if(Graph->G[V][W]==1 && Visited[W]==0)DFS(Graph, W, Visited);
}

3.2 广度优先算法

邻接矩阵

/* 邻接矩阵存储的图 - BFS *//* IsEdge(Graph, V, W)检查<V, W>是否图Graph中的一条边，即W是否V的邻接点 */
/* 此函数根据图的不同类型要做不同的实现，关键取决于对不存在的边的表示方法  */
/* 例如对有权图，如果不存在的边被初始化为INFINITY，则函数实现如下：       */
bool IsEdge(MGraph Graph, Vertex V, Vertex W)
{return Graph->G[V][W]<INFINITY?true:false;
}/* Visited[]为全局变量，已经初始化为false */
void BFS(MGraph Graph, Vertex S, void(*Visit)(Vertex))
{   /* 以S为出发点对邻接矩阵存储的图Graph进行BFS搜索 */Queue Q;Vertex V, W;Q = CreateQueue(MaxSize);   /* 创建空队列，MaxSize为外部定义的常数 *//* 访问顶点S:此处可根据具体访问需要改写 */Visit(S);Visited[S] = true;  /* 标记S已访问 */AddQ(Q, S);          /* S入对列 */while(!IsEmpty(Q)) {V = DeleteQ(Q);     /* 弹出V */for(W=0;W<Graph->Nv;W++)    /* 对图中的每个顶点W *//* 若W是V的邻接点并且未访问过 */if(!Visited[W] && IsEdge(Graph, V, W)) {/* 访问顶点W */Visist(W);Visited[W] = true;  /* 标记W已访问 */AddQ(Q, W);         /* W入队列 */}} /* while结束 */
}

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

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

相关文章

go开发之个微机器人的二次开发

go开发之个微机器人的二次开发

简要描述&#xff1a; 设置某条朋友圈为隐私 请求URL&#xff1a; http://域名地址/snsSetAsPrivacy 请求方式&#xff1a; POST 请求头Headers&#xff1a; Content-Type&#xff1a;application/jsonAuthorization&#xff1a;login接口返回 参数&#xff1a; 参数名…
阅读更多...
CFTC可能比SEC更可怕，将监管炮口直接对准DeFi?

CFTC可能比SEC更可怕，将监管炮口直接对准DeFi?

还未开始享受Uniswap在法庭上为DeFi行业带来的“胜利果实”&#xff0c;美国商品期货委员会&#xff08;CFTC&#xff09;在一个星期之后立即将其无情砸碎&#xff0c;并将其监管大炮直接对准了DeFi衍生品市场&#xff0c;乃至整个DeFi行业。 2023年9月7日&#xff0c;CFTC宣布…
阅读更多...
leetcode 215.数组中第k大的元素

leetcode 215.数组中第k大的元素

⭐️ 题目描述 &#x1f31f; leetcode链接&#xff1a;数组中第k大的元素 思路&#xff1a; 使用堆数据结构&#xff0c;大堆的堆顶是堆内最大的元素&#xff0c;也就是把当前堆 pop k - 1 次&#xff0c;第 k 次 top 出来的元素就是第 k 大的数。 代码&#xff1a; class …
阅读更多...
Spring-MVC使用JSR303及拦截器，增强网络隐私安全

Spring-MVC使用JSR303及拦截器，增强网络隐私安全

目录 一、JSR303 ( 1 ) 是什么 ( 2 ) 作用 ( 3 ) 常用注解 ( 4 ) 入门使用 二、拦截器 2.1 是什么 2.2 拦截器与过滤器的区别 2.3 应用场景 2.4 基础使用 2.5 用户登录权限控制 给我们带来的收获 一、JSR303 ( 1 ) 是什么 JSR 303是Java规范请求&#xff…
阅读更多...
LeetCode 1126.查询活跃业务

LeetCode 1126.查询活跃业务

数据准备 Create table If Not Exists Events (business_id int, event_type varchar(10), occurences int); Truncate table Events; insert into Events (business_id, event_type, occurences) values (1, reviews, 7); insert into Events (business_id, event_type, occu…
阅读更多...
职场新人对测试用例的困惑

职场新人对测试用例的困惑

职场新人对测试用例的困惑无非有以下几点&#xff1a; 什么是测试用例&#xff0c;为什么要写测试用例&#xff1f; 不知道怎么写&#xff0c;写了也不知道写的是否完整。 一、什么是测试用例&#xff1f; 百科的释义&#xff1a; 测试用例是对一项特定的软件产品进行测试任…
阅读更多...
【CSS系列】writing-mode —— 文字方向（水平/垂直；左右/右左）

【CSS系列】writing-mode —— 文字方向（水平/垂直；左右/右左）

文章目录 一、引子二、writing-mode1.语法horizontal-tb&#xff08;默认&#xff1a;水平方向&#xff0c;文字 从左到右&#xff0c;行 从上到下&#xff09;vertical-rl&#xff08;垂直方向&#xff0c;文字 从上到下&#xff0c;行 从右到左&#xff09;vertical-lr&#…
阅读更多...
数字化转型背景下企业知识管理能力提升路径

数字化转型背景下企业知识管理能力提升路径

近年来&#xff0c;科技不断进步&#xff0c;颠覆性技术&#xff08;例如 5G、云计算、物联网、大数据分析和人工智能等&#xff09;正在重新定义企业如何管理项目和运营效率。知识管理体系亦需要随着科技的进步而改变&#xff0c;以适应新的数字时代环境&#xff0c;并且高效知…
阅读更多...
SpringMVC的简介及工作流程

SpringMVC的简介及工作流程

一.简介 Spring MVC是一个基于Java的开发框架&#xff0c;用于构建灵活且功能强大的Web应用程序。它是Spring Framework的一部分&#xff0c;提供了一种模型-视图-控制器&#xff08;Model-View-Controller&#xff0c;MVC&#xff09;的设计模式&#xff0c;用于组织和管理Web…
阅读更多...
微信小程序Day2笔记

微信小程序Day2笔记

1、WXML模板语法 1. 数据绑定 数据绑定的基本原则 在data中定义数据在WXML中使用数据 2. 在data中定义页面的数据 在页面对应的.js文件中&#xff0c;把数据定义到data对象中。 3. Mustache语法的格式 把data中的数据绑定到页面中渲染&#xff0c;使用Mustache语法&…
阅读更多...
C语言学习系列--＞字符函数和字符串函数

C语言学习系列--＞字符函数和字符串函数

文章目录 一、字符函数1、字符分类函数2、字符转换函数 二、字符串函数1、strlen概述模拟实现 2、strcpy概述模拟实现 3、strcat概述模拟实现 3、strcmp概述模拟实现 4、有限制的字符串函数strncpystrncatstrncmp 4、strstr概述模拟实现 一、字符函数 1、字符分类函数 包含头…
阅读更多...
【算法】二分查找算法——leetcode二分查找、搜索插入位置

【算法】二分查找算法——leetcode二分查找、搜索插入位置

文章目录 二分查找704. 二分查找35. 搜索插入位置 二分查找 二分查找算法是一种在有序数组中查找特定元素的搜索算法。算法的工作原理是&#xff0c;通过比较数组中间元素和目标值&#xff0c;如果目标值等于中间元素&#xff0c;那么查找结束。如果目标值小于或大于中间元素&a…
阅读更多...
Linux驱动【day2】

Linux驱动【day2】

mychrdev.c: #include <linux/init.h> #include <linux/module.h> #include <linux/fs.h> #include<linux/uaccess.h> #include<linux/io.h> #include"head.h" unsigned int major; // 保存主设备号 char kbuf[128]{0}; unsigned int…
阅读更多...
产品波士顿矩阵

产品波士顿矩阵

随着公司产品的增多&#xff0c;每个产品的生命周期节点各不相同&#xff0c;很多时候我们往往在产品结构、资源分配方面会产生各种问题&#xff0c;导致需要发展的产品得不到资源&#xff0c;消耗资源的产品却有无法增长&#xff0c;所谓不聚焦导致的问题其实是资源和发展错配…
阅读更多...
ETCD详解

ETCD详解

一、etcd概念 ETCD 是一个高可用的分布式键值key-value数据库&#xff0c;可用于服务发现。 ETCD 采用raft 一致性算法&#xff0c;基于 Go语言实现。 etcd作为一个高可用键值存储系统&#xff0c;天生就是为集群化而设计的。由于Raft算法在做决策时需要多数节点的投票&…
阅读更多...
编程中的信号处理和系统 - 初学者指南

编程中的信号处理和系统 - 初学者指南

信号处理是工程和编程的一个重要领域。 基本上，它允许工程师和程序员改进数据，以便人们可以更有效地使用它。 例如，由于信号处理，电话中的大部分背景噪音都被消除了。这样，通话的另一端就只能听到您的声音。 其他例子有： 音频和音乐软件图像视频处理软件医学影像软件语…
阅读更多...
Modelsim仿真问题解疑二：ERROR: [USF-ModelSim-70]

Modelsim仿真问题解疑二：ERROR: [USF-ModelSim-70]

现象&#xff1a;在Vivado中已配置modelsim为仿真工具后&#xff0c;运行仿真&#xff0c;报错USF-ModelSim-70和ERROR: [Vivado 12-4473] 详细报错内容如下 ERROR: [USF-ModelSim-70] compile step failed with error(s) while executing C:/Users/ZYP_PC/Desktop/verilog_t…
阅读更多...
JavaScript构造函数

JavaScript构造函数

1、构造函数&#xff1a; 是一个函数&#xff0c;是通过new运算符进行调用&#xff0c;生成一个特殊的对象并返回。 function 函数名([参数]){ this.属性名 ‘属性值’ ... this.属性名 function([参数]){ 函数体语句 } } 通常情况下&#xff0c;建议构造函数的首字母大写 …
阅读更多...
ELK日志框架图总结

ELK日志框架图总结

ELK日志框架图总结 本文目录 ELK日志框架图总结Elastic Stack介绍模式分层图beatselasticsearchkibana模式logstashelasticsearchkibana模式beatslogstashelasticsearchkibana模式beats缓存/消息队列logstashelasticsearchkibana模式elkspringboot Elastic Stack介绍 官网&…
阅读更多...
无涯教程-JavaScript - MIRR函数

无涯教程-JavaScript - MIRR函数

描述 MIRR函数针对一系列定期现金Stream返回修改后的内部收益率。 MIRR会同时考虑投资成本和现金再投资收到的利息。 语法 MIRR (values, finance_rate, reinvest_rate)争论 Argument描述Required/OptionalValues 包含数字的单元格的数组或引用。这些数字表示定期发生的一系…
阅读更多...
最新文章
推荐文章

Copyright @ 2022~2023