【 声明:版权所有,欢迎转载,请勿用于商业用途。 联系信箱:feixiaoxing @163.com】
前面我们讨论过图的基本结构是什么样的。它可以是矩阵类型的、数组类型的,当然也可以使指针类型的。当然,就我个人而言,比较习惯使用的结构还是链表指针类型的。本质上,一幅图就是由很多节点构成的,每一个节点上面有很多的分支,仅此而已。为此,我们又对原来的结构做了小的改变:
typedef struct _LINE
{
int end;
int weight;
struct _LINE* next;
}LINE;
typedef struct _VECTEX
{
int start;
int number;
LINE* neighbor;
struct _VECTEX* next;
}VECTEX;
typedef struct _GRAPH
{
int count;
VECTEX* head;
}GRAPH;
为了创建图,首先我们需要创建节点和创建边。不妨从创建节点开始,
VECTEX* create_new_vectex(int start)
{
VECTEX* pVextex = (VECTEX*)malloc(sizeof(VECTEX));
assert(NULL != pVextex);
pVextex->start = start;
pVextex->number = 0;
pVextex->neighbor = NULL;
pVextex->next = NULL;
return pVextex;
}
接着应该创建边了,
LINE* create_new_line(int end, int weight)
{
LINE* pLine = (LINE*)malloc(sizeof(LINE));
assert(NULL != pLine);
pLine->end = end;
pLine->weight = weight;
pLine->next = NULL;
return pLine;
}
有了上面的内容,那么创建一个带有边的顶点就变得很简单了,
VECTEX* create_new_vectex_for_graph(int start, int end, int weight)
{
VECTEX* pVectex = create_new_vectex(start);
assert(NULL != pVectex);
pVectex->neighbor = create_new_line(end, weight);
assert(NULL != pVectex->neighbor);
return pVectex;
}
那么,怎么它怎么和graph相关呢?其实也不难。
GRAPH* create_new_graph(int start, int end, int weight)
{
GRAPH* pGraph = (GRAPH*)malloc(sizeof(GRAPH));
assert(NULL != pGraph);
pGraph->count = 1;
pGraph->head = create_new_vectex_for_graph(start, end, weight);
assert(NULL != pGraph->head);
return pGraph;
}
有了图,有了边,那么节点和边的查找也不难了。
VECTEX* find_vectex_in_graph(VECTEX* pVectex, int start)
{
if(NULL == pVectex)
return NULL;
while(pVectex){
if(start == pVectex->start)
return pVectex;
pVectex = pVectex->next;
}
return NULL;
}
LINE* find_line_in_graph(LINE* pLine, int end)
{
if(NULL == pLine)
return NULL;
while(pLine){
if(end == pLine->end)
return pLine;
pLine = pLine->next;
}
return NULL;
}
总结:
(1)图就是多个链表的聚合
(2)想学好图,最好把前面的链表和指针搞清楚、弄扎实
(3)尽量写小函数,小函数构建大函数,方便阅读和调试
分享到:
相关推荐
受社会性昆虫劳动分工的启发提出一种群机器人地图创建的探索策略, 以提高群机器人创建地图的效率。当机器人所在顶点位置有未访问的路径时, 机器人随机选择一条未访问路径进行访问; 如果当前位置的所有路径都已被访问...
算法步骤如下:(1)创建天牛须朝向的随机向量且做归一化处理式中: rand()为随机函数; ||rands()||表示空间维度。(2)创建天牛左右须空间坐标(3)根据适应度函数判断左右须气味强度,即f(x_l)和f(x_r)的强度, ...
包含创建随机地图,A*算法查找路径,matlab绘图表示。 1 随机创建地图自定义地图大小,随机障碍物数量境地,任务起点和终点; 2 由经典的A*算法计算地图中起点到终点的路径; 3 plot绘图函数将地图,起点终点,路径...
带领读者一步一步亲手制作一个指纹识别系统 深度剖析真实的行业应用案例 业界专家强力推荐 部分章节目录: 目录: 第一篇 指纹模式识别系统入门 第1章 指纹模式识别演示轻松入门 3 1.1 体验VisualC++指纹模式识别...
贪心算法是一种在每一步选择中都采取在当前状态下最好或最优的选择,从而希望导致结果是全局最好或最优的算法策略。贪心算法在有最优子结构的问题中尤为有效。最优子结构的意思是局部最优解可以决定全局最优解。 ...
打开myEclipse,文件->新建->项目->Java项目->项目名与刚才建的目录名(weka-sr)一样,点击下一步就会加载解压的文件,可以看到有main/src test/src。点确定就行了。 3.4 编译运行。选择刚创建的项目WEKA-Rebuild,...
普利姆(Prim)算法是一种用于在加权无向图中查找最小生成树的贪心算法。它的工作原理是,从图中随机选择一个顶点开始,然后不断添加与其相连的最短边(且这条边连接的另一个顶点尚未在生成树中),直到所有顶点都被...
基于C++、文件操作和Huffman算法实现图片压缩源码+使用说明+详细注释+sln解决方案.zip ——使用C++、文件操作和Huffman算法实现“图片压缩程序”。 ## 1. 核心知识 (1) 树的存储结构 (2) 二叉树的三种遍历方法...
■实现Builder角色提供的接口,一步一步完成创建产品实例的过程。 ■在建造过程完成后,提供产品的实例。 ◆指导者(Director): 担任这个角色的类调用具体建造者角色以创建产品对象。导演者并没有产品类的...
使用Visual Studio将NuGet程序包添加到项目时,将自动创建依赖项。 将RaftCore添加到项目后,下一步是选择状态机和连接器。 此时,建议生成API参考或在线访问文档页面()以进行参考。 2.1。 选择状态机 该项目...
按图片搜索“按图像搜索”的基本 Java 实现在这个项目中,我们使用了一种称为“感知哈希算法”的算法,该算法用于创建“指纹”——每个图像的唯一字符串,并将每个指纹与原始图像进行比较。 结果越接近,两幅图像越...
选择microsoft 决策树,继续下一步 图15 创建数据挖掘模型结构 15. 下一步 图16 选择数据源视图 16. 勾选事例,继续下一步 图17 指定表类型 17. 在键列勾选序号码,在输入列勾选出身、国别、魅力、统御、武力、政治...
接着请求该同步对象,随即进入临界区,这一步对应于互斥量的上锁;最后释放该同步对象,这对应于互斥量的解锁。这些同步对象在主进程中创建,在其子线程中都可。 实验二 存储管理 一、目的和要求 1. 实验目的 ...
然后是许可协议,这里是必须无 " "条件接受的,点"YES"按钮,进入提示安装PGP所需要的系统、以及软件配置情 " "况的界面,继续点NEXT按钮,出现创建用户类型的界面,选择如图1: " " " "图1 " "新用户需要创建并设置...
受社会性昆虫劳动分工的启发提出一种群机器人地图创建的探索策略, 以提高群机器人创建地图的效率。当机器人所在顶点位置有未访问的路径时, 机器人随机选择一条未访问路径进行访问; 如果当前位置的所有路径都已被访问...
3. 构建模型:使用Python中的深度学习框,如TensorFlow、Keras或PyTorch,来创建一个适合文本分类的深度学习模型。通常使用循环神经网络(如LSTM或GRU)或卷积神经网络(CNN)来处理文本序列。 4. 特征提取:在模型...
1.1灰度: 原理:在这里用C语言只简单的改变象素矩阵的RGB值,来达到彩色图转变为灰度图,并没有添加调色板。 主要步骤: 1、 获取彩色图片。 2、 读取图片的像素。 3、采用精确加权平均值算法:...5、 创建新的灰度图
该方法利用Mobotsim二维仿真软件构造了环境模型,机器人通过无碰自由巡航获取环境信息,然后把上一步得到的环境信息作为DGSOM_A*算法样本通过SOM神经元自主生长进行地图创建,生成以少数 SOM图神经元分布描述环境...
music_recommender ... 下一步将是正确地重写代码,并为正确使用创建标准的API。 进一步整合的东西 -欧几里得距离 -海明距离 -余弦距离 -曼哈顿距离 使用aubio库进行音频信号处理以从音轨中提取参数。
graph),每个节点表征一步操作(即机器学习算法),每一条边表征从一个节点到后一个即节点的数据流。 任务可被人工定义,或根据现有任务/模板进行克隆。在把任务提交到云端之后,每个节点将根据 DAG 自动执行。...