算法graph种类

1. 图计算引擎Neo4j和Graphscope有什么区别

Neo4j是单机系统，主要做图数据库。GraphScope是由阿里巴巴达摩院智能计算实验室研发的图计算平台，是全球首个一站式超大规模分布式图计算平台，并且还入选了中 国科学技术协会“科创中 国”平台。Graphscope的代码在github.com/alibaba/graphscope上开源。SSSP算法上,GraphScope单机模式下平均要比Neo4j快176.38倍，最快在datagen-9.2_zf数据集上快了292.2倍。

2. 对于社交网络的数据挖掘应该如何入手，使用哪些算法

3月13日下午，南京邮电大学计算机学院、软件学院院长、教授李涛在CIO时代APP微讲座栏目作了题为《大数据时代的数据挖掘》的主题分享，深度诠释了大数据及大数据时代下的数据挖掘。

众所周知，大数据时代的大数据挖掘已成为各行各业的一大热点。
一、数据挖掘
在大数据时代，数据的产生和收集是基础，数据挖掘是关键，数据挖掘可以说是大数据最关键也是最基本的工作。通常而言，数据挖掘也称为DataMining，或知识发现Knowledge Discovery from Data，泛指从大量数据中挖掘出隐含的、先前未知但潜在的有用信息和模式的一个工程化和系统化的过程。
不同的学者对数据挖掘有着不同的理解，但个人认为，数据挖掘的特性主要有以下四个方面：
1.应用性（A Combination of Theory and Application）：数据挖掘是理论算法和应用实践的完美结合。数据挖掘源于实际生产生活中应用的需求，挖掘的数据来自于具体应用，同时通过数据挖掘发现的知识又要运用到实践中去，辅助实际决策。所以，数据挖掘来自于应用实践，同时也服务于应用实践，数据是根本，数据挖掘应以数据为导向，其中涉及到算法的设计与开发都需考虑到实际应用的需求，对问题进行抽象和泛化，将好的算法应用于实际中，并在实际中得到检验。
2.工程性（An Engineering Process）：数据挖掘是一个由多个步骤组成的工程化过程。数据挖掘的应用特性决定了数据挖掘不仅仅是算法分析和应用，而是一个包含数据准备和管理、数据预处理和转换、挖掘算法开发和应用、结果展示和验证以及知识积累和使用的完整过程。而且在实际应用中，典型的数据挖掘过程还是一个交互和循环的过程。
3.集合性（A Collection of Functionalities）：数据挖掘是多种功能的集合。常用的数据挖掘功能包括数据探索分析、关联规则挖掘、时间序列模式挖掘、分类预测、聚类分析、异常检测、数据可视化和链接分析等。一个具体的应用案例往往涉及多个不同的功能。不同的功能通常有不同的理论和技术基础，而且每一个功能都有不同的算法支撑。
4.交叉性（An Interdisciplinary Field）：数据挖掘是一门交叉学科，它利用了来自统计分析、模式识别、机器学习、人工智能、信息检索、数据库等诸多不同领域的研究成果和学术思想。同时一些其他领域如随机算法、信息论、可视化、分布式计算和最优化也对数据挖掘的发展起到重要的作用。数据挖掘与这些相关领域的区别可以由前面提到的数据挖掘的3个特性来总结，最重要的是它更侧重于应用。
综上所述，应用性是数据挖掘的一个重要特性，是其区别于其他学科的关键，同时，其应用特性与其他特性相辅相成，这些特性在一定程度上决定了数据挖掘的研究与发展，同时，也为如何学习和掌握数据挖掘提出了指导性意见。如从研究发展来看，实际应用的需求是数据挖掘领域很多方法提出和发展的根源。从最开始的顾客交易数据分析（market basket analysis）、多媒体数据挖掘（multimedia data mining）、隐私保护数据挖掘（privacy-preserving data mining）到文本数据挖掘（text mining）和Web挖掘（Web mining），再到社交媒体挖掘（social media mining）都是由应用推动的。工程性和集合性决定了数据挖掘研究内容和方向的广泛性。其中，工程性使得整个研究过程里的不同步骤都属于数据挖掘的研究范畴。而集合性使得数据挖掘有多种不同的功能，而如何将多种功能联系和结合起来，从一定程度上影响了数据挖掘研究方法的发展。比如，20世纪90年代中期，数据挖掘的研究主要集中在关联规则和时间序列模式的挖掘。到20世纪90年代末，研究人员开始研究基于关联规则和时间序列模式的分类算法（如classification based on association），将两种不同的数据挖掘功能有机地结合起来。21世纪初，一个研究的热点是半监督学习（semi-supervised learning）和半监督聚类（semi-supervised clustering），也是将分类和聚类这两种功能有机结合起来。近年来的一些其他研究方向如子空间聚类（subspace clustering）（特征抽取和聚类的结合）和图分类（graph classification）（图挖掘和分类的结合）也是将多种功能联系和结合在一起。最后，交叉性导致了研究思路和方法设计的多样化。
前面提到的是数据挖掘的特性对研究发展及研究方法的影响，另外，数据挖掘的这些特性对如何学习和掌握数据挖掘提出了指导性的意见，对培养研究生、本科生均有一些指导意见，如应用性在指导数据挖掘时，应熟悉应用的业务和需求，需求才是数据挖掘的目的，业务和算法、技术的紧密结合非常重要，了解业务、把握需求才能有针对性地对数据进行分析，挖掘其价值。因此，在实际应用中需要的是一种既懂业务，又懂数据挖掘算法的人才。工程性决定了要掌握数据挖掘需有一定的工程能力，一个好的数据额挖掘人员首先是一名工程师，有很强大的处理大规模数据和开发原型系统的能力，这相当于在培养数据挖掘工程师时，对数据的处理能力和编程能力很重要。集合性使得在具体应用数据挖掘时，要做好底层不同功能和多种算法积累。交叉性决定了在学习数据挖掘时要主动了解和学习相关领域的思想和技术。
因此，这些特性均是数据挖掘的特点，通过这四个特性可总结和学习数据挖掘。
二、大数据的特征
大数据（bigdata）一词经常被用以描述和指代信息爆炸时代产生的海量信息。研究大数据的意义在于发现和理解信息内容及信息与信息之间的联系。研究大数据首先要理清和了解大数据的特点及基本概念，进而理解和认识大数据。
研究大数据首先要理解大数据的特征和基本概念。业界普遍认为，大数据具有标准的“4V”特征：
1.Volume（大量）：数据体量巨大，从TB级别跃升到PB级别。
2.Variety（多样）：数据类型繁多，如网络日志、视频、图片、地理位置信息等。
3.Velocity（高速）：处理速度快，实时分析，这也是和传统的数据挖掘技术有着本质的不同。
4.Value（价值）：价值密度低，蕴含有效价值高，合理利用低密度价值的数据并对其进行正确、准确的分析，将会带来巨大的商业和社会价值。
上述“4V”特点描述了大数据与以往部分抽样的“小数据”的主要区别。然而，实践是大数据的最终价值体现的唯一途径。从实际应用和大数据处理的复杂性看，大数据还具有如下新的“4V”特点：
5.Variability（变化）：在不同的场景、不同的研究目标下数据的结构和意义可能会发生变化，因此，在实际研究中要考虑具体的上下文场景（Context）。
6.Veracity（真实性）：获取真实、可靠的数据是保证分析结果准确、有效的前提。只有真实而准确的数据才能获取真正有意义的结果。
7.Volatility（波动性）/Variance（差异）：由于数据本身含有噪音及分析流程的不规范性，导致采用不同的算法或不同分析过程与手段会得到不稳定的分析结果。
8.Visualization（可视化）：在大数据环境下，通过数据可视化可以更加直观地阐释数据的意义，帮助理解数据，解释结果。
综上所述，以上“8V”特征在大数据分析与数据挖掘中具有很强的指导意义。
三、大数据时代下的数据挖掘
在大数据时代，数据挖掘需考虑以下四个问题：
大数据挖掘的核心和本质是应用、算法、数据和平台4个要素的有机结合。
因为数据挖掘是应用驱动的，来源于实践，海量数据产生于应用之中。需用具体的应用数据作为驱动，以算法、工具和平台作为支撑，最终将发现的知识和信息应用到实践中去，从而提供量化的、合理的、可行的、且能产生巨大价值的信息。
挖掘大数据中隐含的有用信息需设计和开发相应的数据挖掘和学习算法。算法的设计和开发需以具体的应用数据作为驱动，同时在实际问题中得到应用和验证，而算法的实现和应用需要高效的处理平台，这个处理平台可以解决波动性问题。高效的处理平台需要有效分析海量数据，及时对多元数据进行集成，同时有力支持数据化对算法及数据可视化的执行，并对数据分析的流程进行规范。
总之，应用、算法、数据、平台这四个方面相结合的思想，是对大数据时代的数据挖掘理解与认识的综合提炼，体现了大数据时代数据挖掘的本质与核心。这四个方面也是对相应研究方面的集成和架构，这四个架构具体从以下四个层面展开：
应用层（Application）：关心的是数据的收集与算法验证，关键问题是理解与应用相关的语义和领域知识。
数据层（Data）：数据的管理、存储、访问与安全，关心的是如何进行高效的数据使用。
算法层（Algorithm）：主要是数据挖掘、机器学习、近似算法等算法的设计与实现。
平台层（Infrastructure）：数据的访问和计算，计算平台处理分布式大规模的数据。
综上所述，数据挖掘的算法分为多个层次，在不同的层面有不同的研究内容，可以看到目前在做数据挖掘时的主要研究方向，如利用数据融合技术预处理稀疏、异构、不确定、不完整以及多来源数据；挖掘复杂动态变化的数据；测试通过局部学习和模型融合所得到的全局知识，并反馈相关信息给预处理阶段；对数据并行分布化，达到有效使用的目的。
四、大数据挖掘系统的开发
1.背景目标
大数据时代的来临使得数据的规模和复杂性都出现爆炸式的增长，促使不同应用领域的数据分析人员利用数据挖掘技术对数据进行分析。在应用领域中，如医疗保健、高端制造、金融等，一个典型的数据挖掘任务往往需要复杂的子任务配置，整合多种不同类型的挖掘算法以及在分布式计算环境中高效运行。因此，在大数据时代进行数据挖掘应用的一个当务之急是要开发和建立计算平台和工具，支持应用领域的数据分析人员能够有效地执行数据分析任务。
之前提到一个数据挖掘有多种任务、多种功能及不同的挖掘算法，同时，需要一个高效的平台。因此，大数据时代的数据挖掘和应用的当务之急，便是开发和建立计算平台和工具，支持应用领域的数据分析人员能够有效地执行数据分析任务。
2.相关产品
现有的数据挖掘工具
有Weka、SPSS和SQLServer，它们提供了友好的界面，方便用户进行分析，然而这些工具并不适合进行大规模的数据分析，同时，在使用这些工具时用户很难添加新的算法程序。
流行的数据挖掘算法库
如Mahout、MLC++和MILK，这些算法库提供了大量的数据挖掘算法。但这些算法库需要有高级编程技能才能进行任务配置和算法集成。
最近出现的一些集成的数据挖掘产品
如Radoop和BC-PDM，它们提供友好的用户界面来快速配置数据挖掘任务。但这些产品是基于Hadoop框架的，对非Hadoop算法程序的支持非常有限。没有明确地解决在多用户和多任务情况下的资源分配。
3.FIU-Miner
为解决现有工具和产品在大数据挖掘中的局限性，我们团队开发了一个新的平台——FIU-Miner，它代表了A Fast,Integrated,and User-Friendly System for Data Miningin Distributed Environment。它是一个用户友好并支持在分布式环境中进行高效率计算和快速集成的数据挖掘系统。与现有数据挖掘平台相比，FIU-Miner提供了一组新的功能，能够帮助数据分析人员方便并有效地开展各项复杂的数据挖掘任务。
与传统的数据挖掘平台相比，它提供了一些新的功能，主要有以下几个方面：
A.用户友好、人性化、快速的数据挖掘任务配置。基于“软件即服务”这一模式，FIU-Miner隐藏了与数据分析任务无关的低端细节。通过FIU-Miner提供的人性化用户界面，用户可以通过将现有算法直接组装成工作流，轻松完成一个复杂数据挖掘问题的任务配置，而不需要编写任何代码。
B.灵活的多语言程序集成。允许用户将目前最先进的数据挖掘算法直接导入系统算法库中，以此对分析工具集合进行扩充和管理。同时，由于FIU-Miner能够正确地将任务分配到有合适运行环境的计算节点上，所以对这些导入的算法没有实现语言的限制。
C.异构环境中有效的资源管理。FIU-Miner支持在异构的计算环境中（包括图形工作站、单个计算机、和服务器等）运行数据挖掘任务。FIU-Miner综合考虑各种因素（包括算法实现、服务器负载平衡和数据位置）来优化计算资源的利用率。
D.有效的程序调度和执行。
应用架构上包括用户界面层、任务和系统管理层、逻辑资源层、异构的物理资源层。这种分层架构充分考虑了海量数据的分布式存储、不同数据挖掘算法的集成、多重任务的配置及系统用户的交付功能。一个典型的数据挖掘任务在应用之中需要复杂的主任务配置，整合多种不同类型的挖掘算法。因此，开发和建立这样的计算平台和工具，支持应用领域的数据分析人员进行有效的分析是大数据挖掘中的一个重要任务。
FIU-Miner系统用在了不同方面：如高端制造业、仓库智能管理、空间数据处理等，TerraFly GeoCloud是建立在TerraFly系统之上的、支持多种在线空间数据分析的一个平台。提供了一种类SQL语句的空间数据查询与挖掘语言MapQL。它不但支持类SQL语句，更重要的是可根据用户的不同要求，进行空间数据挖掘，渲染和画图查询得到空间数据。通过构建空间数据分析的工作流来优化分析流程，提高分析效率。
制造业是指大规模地把原材料加工成成品的工业生产过程。高端制造业是指制造业中新出现的具有高技术含量、高附加值、强竞争力的产业。典型的高端制造业包括电子半导体生产、精密仪器制造、生物制药等。这些制造领域往往涉及严密的工程设计、复杂的装配生产线、大量的控制加工设备与工艺参数、精确的过程控制和材料的严格规范。产量和品质极大地依赖流程管控和优化决策。因此，制造企业不遗余力地采用各种措施优化生产流程、调优控制参数、提高产品品质和产量，从而提高企业的竞争力。
在空间数据处理方面，TerraFly GeoCloud对多种在线空间数据分析。对传统数据分析而言，其难点在于MapQL语句比较难写，任务之间的关系比较复杂，顺序执行之间空间数据分许效率较低。而FIU-Miner可有效解决以上三个难点。
总结而言，大数据的复杂特征对数据挖掘在理论和算法研究方面提出了新的要求和挑战。大数据是现象，核心是挖掘数据中蕴含的潜在信息，并使它们发挥价值。数据挖掘是理论技术和实际应用的完美结合。数据挖掘是理论和实践相结合的一个例子。
-
-

3. 图遍历的算法

图的遍历方法目前有深度优先搜索法和广度（宽度）优先搜索法两种算法。 深度优先搜索法是树的先根遍历的推广，它的基本思想是：从图G的某个顶点v0出发，访问v0，然后选择一个与v0相邻且没被访问过的顶点vi访问，再从vi出发选择一个与vi相邻且未被访问的顶点vj进行访问，依次继续。如果当前被访问过的顶点的所有邻接顶点都已被访问，则退回到已被访问的顶点序列中最后一个拥有未被访问的相邻顶点的顶点w，从w出发按同样的方法向前遍历，直到图中所有顶点都被访问。其递归算法如下：
Boolean visited[MAX_VERTEX_NUM]; //访问标志数组
Status (*VisitFunc)(int v); //VisitFunc是访问函数，对图的每个顶点调用该函数
void DFSTraverse (Graph G, Status(*Visit)(int v)){
VisitFunc = Visit;
for(v=0; v<G.vexnum; ++v)
visited[v] = FALSE; //访问标志数组初始化
for(v=0; v<G.vexnum; ++v)
if(!visited[v])
DFS(G, v); //对尚未访问的顶点调用DFS
}
void DFS(Graph G, int v){ //从第v个顶点出发递归地深度优先遍历图G
visited[v]=TRUE; VisitFunc(v); //访问第v个顶点
for(w=FirstAdjVex(G,v); w>=0; w=NextAdjVex(G,v,w))
//FirstAdjVex返回v的第一个邻接顶点，若顶点在G中没有邻接顶点，则返回空（0）。
//若w是v的邻接顶点，NextAdjVex返回v的（相对于w的）下一个邻接顶点。
//若w是v的最后一个邻接点，则返回空（0）。
if(!visited[w])
DFS(G, w); //对v的尚未访问的邻接顶点w调用DFS
} 图的广度优先搜索是树的按层次遍历的推广，它的基本思想是：首先访问初始点vi，并将其标记为已访问过，接着访问vi的所有未被访问过的邻接点vi1,vi2,…, vi t，并均标记已访问过，然后再按照vi1,vi2,…, vi t的次序，访问每一个顶点的所有未被访问过的邻接点，并均标记为已访问过，依次类推，直到图中所有和初始点vi有路径相通的顶点都被访问过为止。其非递归算法如下：
Boolean visited[MAX_VERTEX_NUM]; //访问标志数组
Status (*VisitFunc)(int v); //VisitFunc是访问函数，对图的每个顶点调用该函数
void BFSTraverse (Graph G, Status(*Visit)(int v)){
VisitFunc = Visit;
for(v=0; v<G.vexnum, ++v)
visited[v] = FALSE;
initQueue(Q); //置空辅助队列Q
for(v=0; v<G.vexnum; ++v)
if(!visited[v]){
visited[v]=TRUE; VisitFunc(v);
EnQueue(Q, v); //v入队列
while(!QueueEmpty(Q)){
DeQueue(Q, u); //队头元素出队并置为u
for(w=FirstAdjVex(G,u); w>=0; w=NextAdjVex(G,u,w))
if(!Visited[w]){ //w为u的尚未访问的邻接顶点
Visited[w]=TRUE; VisitFunc(w);
EnQueue(Q, w);
}
}
}
}

4. 有哪些应用于移动机器人路径规划的算法

机器人家上了解到，在二维二值地图（FREE or OCCUPIED）场景下进行路径规划的方法。我看之前有同学在回答的时候配上了这幅图：

这幅图上的算法罗列的还是很全面的，体现了各个算法的出生顺序。但是并不能很好的对他们进行一个本质的分类。刚刚那位同学说的graph-based和sampling-based的分类方法我感觉有点概念重叠不能够对规划算法进行这样的分类，下面通过自己这一年多的研究和实践对规划算法进行一个简单的分类：

这幅图上的算法罗列的还是很全面的，体现了各个算法的出生顺序。但是并不能很好的对他们进行一个本质的分类。刚刚那位同学说的graph-based和sampling-based的分类方法我感觉有点概念重叠不能够对规划算法进行这样的分类，下面通过自己这一年多的研究和实践对规划算法进行一个简单的分类：

两大类：
1. 完备的（complete)
2. 基于采样的（sampling-based）又称为概率完备的

一 完备的规划算法

A*算法

所谓完备就是要达到一个systematic的标准，即：如果在起始点和目标点间有路径解存在那么一定可以得到解，如果得不到解那么一定说明没有解存在。
这一大类算法在移动机器人领域通常直接在occupancy grid网格地图上进行规划（可以简单理解成二值地图的像素矩阵）以深度优先寻路算法、广度优先寻路算法、Dijkstra(迪杰斯特拉)算法为始祖，以A*算法(Dijstra算法上以减少计算量为目的加上了一个启发式代价)最为常用，近期的Theta*算法是在A*算法的基础上增加了line-of-sight优化使得规划出来的路径不完全依赖于单步的栅格形状（答主以为这个算法意义不大，不就是规划了一条路径再简单平滑了一下么）。
完备的算法的优势在与它对于解的捕获能力是完全的，但是由此产生的缺点就是算法复杂度较大。这种缺点在二维小尺度栅格地图上并不明显，但是在大尺度，尤其是多维度规划问题上，比如机械臂、蛇形机器人的规划问题将带来巨大的计算代价。这样也直接促使了第二大类算法的产生。

二 基于采样的规划算法

RRT-connect算法
这种算法一般是不直接在grid地图进行最小栅格分辨率的规划，它们采用在地图上随机撒一定密度的粒子来抽象实际地图辅助规划。如PRM算法及其变种就是在原始地图上进行撒点，抽取roadmap在这样一个拓扑地图上进行规划；RRT以及其优秀的变种RRT-connect则是在地图上每步随机撒一个点，迭代生长树的方式，连接起止点为目的，最后在连接的图上进行规划。这些基于采样的算法速度较快，但是生成的路径代价（可理解为长度）较完备的算法高，而且会产生“有解求不出”的情况（PRM的逢Narrow space卒的情况）。这样的算法一般在高维度的规划问题中广泛运用。

三 其他规划算法
除了这两类之外还有间接的规划算法：Experience-based（Experience Graph经验图算法）算法：基于经验的规划算法，这是一种存储之前规划路径，建立知识库，依赖之进行规划的方法，题主有兴趣可以阅读相关文献。这种方法牺牲了一定的空间代价达到了速度与完备兼得的优势。此外还有基于广义Voronoi图的方法进行的Fast-marching规划，类似dijkstra规划和势场的融合，该方法能够完备地规划出位于道路中央，远离障碍物的路径。答主最近也在研究此类算法相关的工作。

APF（人工势场）算法

至于D* 、势场法、DWA(动态窗口法)、SR-PRM属于在动态环境下为躲避动态障碍物、考虑机器人动力学模型设计的规划算法。

5. c语言数据结构----学习graph遇到的问题，求教各位前辈~~

1、图在数据结构里面算最复杂的结构，重要性不言而喻，尤其是它与实际问题相关性比较高
2、图和树最大的区别在于，树是无环的，而图可能存在有环；在具体一点，任何一个树节点可以有多个或零个后继（孩子节点），但只能有一个前趋（父节点），而图都没有这些限制了；也直接导致了存储方式的不同：邻接表和邻接矩阵
3、我觉得图的算法虽然比线性表和数的算法抽象，但是还是可以从简单的图例中自己分析，而弧、边和点这些概念看懂就行
图的定义说的是G={V,E}就是点和边的集合，而边有可能有有向的(弧)和无向的，这个有什么不明白的可以再详细问
遍历的话也是深度、广度，跟树类似，唯一的区别就是有了环的存在，从而要对已访问的节点进行标记
4、多写程序吧，就是抄抄代码也好，简单的算法，像最小生成树之类的，画一次就理解了，而像网络流或者二分图最佳匹配之类的，就更要画图了，因为光靠记忆是很难的，至于Floyd，采用DP，直接记程序好了，三重循环很短，而Dijkstra用的贪心，画图很好理解。总而言之，好理解的画图就能记住，不好理解的算法通常都很简洁~
5、其实这两部分关系并不大，但是总之不要逃避问题，会有心理障碍的，不知道的可以问我啊~O(∩_∩)O

6. GraphX和Graphscope哪个算法更厉害

GraphScope的性能更优， GraphLab将数据抽象成Graph结构，非常的厉害

7. c++实现的图（graph）的算法，怎么能可视化演

#pragma comment(lib,"user32")#pragma comment(lib,"gdi32")#include <stdio.h>#include <stdlib.h>#include <windows.h>HWND WINAPI GetConsoleWindow();void HideTheCursor() { CONSOLE_CURSOR_INFO cciCursor; HANDLE hStdOut = GetStdHandle(STD_OUTPUT_HANDLE); if(GetConsoleCursorInfo(hStdOut, &cciCursor)) { cciCursor.bVisible = FALSE; SetConsoleCursorInfo(hStdOut, &cciCursor); }}void ShowTheCursor() { CONSOLE_CURSOR_INFO cciCursor; HANDLE hStdOut = GetStdHandle(STD_OUTPUT_HANDLE); if(GetConsoleCursorInfo(hStdOut, &cciCursor)) { cciCursor.bVisible = TRUE; SetConsoleCursorInfo(hStdOut, &cciCursor); }}int main() { HWND hwnd; HDC hdc; HFONT hfont; system("color F0"); system("cls"); HideTheCursor(); hwnd = GetConsoleWindow(); hdc = GetDC(hwnd); hfont = CreateFont(48, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, "华文楷体"); SelectObject(hdc,hfont); TextOut(hdc,10,10,"地球人都知道！",14); MoveToEx(hdc,5,5,NULL); LineTo(hdc,300, 5); LineTo(hdc,300, 60); LineTo(hdc, 5, 60); LineTo(hdc, 5, 5); DeleteObject(hfont); ReleaseDC(hwnd,hdc); getchar(); system("color 07"); system("cls"); ShowTheCursor(); return 0;}

8. 有向图和无向图的有关知识

有/无 向图如果给图的每条边规定一个方向，那么得到的图称为有向图，其边也称为有向边。在有向图中，与一个节点相关联的边有出边和入边之分，而与一个有向边关联的两个点也有始点和终点之分。相反，边没有方向的图称为无向图。[编辑]简单图一个图如果没有两条边，它们所关联的两个点都相同（在有向图中，没有两条边的起点终点都分别相同）；每条边所关联的是两个不同的顶点则称为简单图(simple graph)。简单的有向图和无向图都可以使用以上的“二元组的定义”，但形如(x,x)的序对不能属于E。而无向图的边集必须是对称的，即如果 ，那么 。[编辑]多重图若允许两结点间的边数多于一条，又允许顶点通过同一条边和自己关联，则为多重图的概念。它只能用“三元组的定义”。[编辑]基本术语在顶点1有一个环阶（Order）：图G中顶集V的大小称作图G的阶。子图（Sub-Graph）：图G'称作图G的子图如果以及 。生成子图（Spanning Sub-Graph）：指满足条件V(G') =V(G)的G的子图G。度（Degree）是一个顶点的度是指与该顶点相关联的总边数，顶点v的度记作d(v)。度和边有如下关系：。出度(out-degree) 和入度 (in-degree)：对有向图而言，顶点的度还可分为出度和入度。一个顶点的出度为 do ，是指有 do 条边以该顶点为起点，或说与该点关联的出边共有do条。入度的概念也类似。邻接矩阵环(loop)：若一条边的两个顶点相同，则此边称作环。路径（path）：从顶点 u 到顶点 v 的一条路径是指一个序列v0,e1,v1,e2,v2,...ek,vk， ei的起点终点为vi及vi - 1； k 称作路径的长度； v_0=u，称为路径的起点； v_k=v，称为路径的终点。如果 u=v，称该路径是闭的，反之则称为开的；如果 v_1 , ... , v_k 两两不等，则称之为简单路径(simple path)（注意，u=v 是允许的）。行迹（trace）：如果路径P(u,v)中边各不相同，则该路径称为u到v的一条行迹。轨道（track）：即简单路径。闭的行迹称作回路（circuit），闭的轨道称作圈（Cycle）。（现存文献中的命名法并无统一标准。比如在另一种定义中，walk 对应上述的 path，path 对应上述的 track ， trail 对应上述的 trace。）距离（distance）： 从顶点 u 出发到顶点 v 的最短路径若存在，则此路径的长度称作从 u 到 v 的距离。若从 u 到 v 根本不存在路径，则记该距离为无穷（∞）。距离矩阵桥（bridge）：若去掉一条边，便会使得整个图不连通，该边称为桥。[编辑]图的存储表示数组（邻接矩阵）存储表示（有向或无向）邻接表存储表示前向星存储表示有向图的十字链表存储表示无向图的邻接多重表存储表示一个不带权图中若两点不相邻，邻接矩阵相应位置为0，对带权图(网)，相应位置为∞。一个图的邻接矩阵表示是唯一的，但其邻接表表示不唯一。在邻接表中，对图中每个顶点建立一个单链表（并按建立的次序编号），第i个单链表中的结点表示依附于顶点vi的边（对于有向图是以顶点vi为尾的弧）。每个结点由两个域组成：邻接点域(adjvex)，用以指示与vi邻接的点在图中的位置，链域(nextarc)用以指向依附于顶点vi的下一条边所对应的结点。如果用邻接表存放网（带权图）的信息，则还需要在结点中增加一个存放权值的域（info）。每个顶点的单链表中结点的个数即为该顶点的出度(与该顶点连接的边的总数)。无论是存储图或网，都需要在每个单链表前设一表头结点，这些表头结点的第一个域data用于存放结点vi的编号i，第二个域firstarc用于指向链表中第一个结点。[编辑]图的遍历图的遍历方法有深度优先搜索法和广度(宽度)优先搜索法。深度优先搜索法是树的先根遍历的推广，它的基本思想是：从图G的某个顶点v0出发，访问v0，然后选择一个与v0相邻且没被访问过的顶点vi访问，再从vi出发选择一个与vi相邻且未被访问的顶点vj进行访问，依次继续。如果当前被访问过的顶点的所有邻接顶点都已被访问，则退回到已被访问的顶点序列中最后一个拥有未被访问的相邻顶点的顶点w，从w出发按同样的方法向前遍历，直到图中所有顶点都被访问。其递归算法如下：Boolean visited[MAX_VERTEX_NUM]; //访问标志数组Status (*VisitFunc)(int v); //VisitFunc是访问函数，对图的每个顶点调用该函数void DFSTraverse (Graph G, Status(*Visit)(int v)){ VisitFunc = Visit; for(v=0; v<G.vexnum; ++v) visited[v] = FALSE; //访问标志数组初始化 for(v=0; v<G.vexnum; ++v) if(!visited[v]) DFS(G, v); //对尚未访问的顶点调用DFS}void DFS(Graph G, int v){ //从第v个顶点出发递归地深度优先遍历图Gvisited[v]=TRUE; VisitFunc(v); //访问第v个顶点for(w=FirstAdjVex(G,v); w>=0; w=NextAdjVex(G,v,w))//FirstAdjVex返回v的第一个邻接顶点，若顶点在G中没有邻接顶点，则返回空(0)，//若w是v的邻接顶点，NextAdjVex返回v的（相对于w的）下一个邻接顶点。//若w是v的最后一个邻接点，则返回空(0)。 if(!visited[w]) DFS(G, w); //对v的尚未访问的邻接顶点w调用DFS}图的广度优先搜索是树的按层次遍历的推广，它的基本思想是：首先访问初始点vi，并将其标记为已访问过，接着访问vi的所有未被访问过的邻接点vi1,vi2, …, vi t，并均标记已访问过，然后再按照vi1,vi2, …, vi t的次序，访问每一个顶点的所有未被访问过的邻接点，并均标记为已访问过，依次类推，直到图中所有和初始点vi有路径相通的顶点都被访问过为止。其非递归算法如下：Boolean visited[MAX_VERTEX_NUM]; //访问标志数组Status (*VisitFunc)(int v); //VisitFunc是访问函数，对图的每个顶点调用该函数void BFSTraverse (Graph G, Status(*Visit)(int v)){ VisitFunc = Visit;for(v=0; v<G.vexnum, ++v) visited[v] = FALSE; initQueue(Q); //置空辅助队列Q for(v=0; v<G.vexnum; ++v) if(!visited[v]){ visited[v]=TRUE; VisitFunc(v); EnQueue(Q, v); //v入队列 while(!QueueEmpty(Q)){ DeQueue(Q, u); //队头元素出队并置为u for(w=FirstAdjVex(G,u); w>=0; w=NextAdjVex(G,u,w)) if(!Visited[w]){ //w为u的尚未访问的邻接顶点 Visited[w]=TRUE; VisitFunc(w); EnQueue(Q, w); } } }}
[编辑]图的重要类型树平面图连通图强连通图有向无环图AOV网AOE网完全图：每一对不同顶点间都有边相连的的图，记作Kn。二分图：顶集，且每一条边都有一个顶点在X中，而另一个顶点在Y中。完全二分图：二分图G中若任意两个X和Y中的顶点都有边相连。若，则图G记作Km,n。正则图：如果图中所有顶点的度皆相等，则此图称为正则图欧拉图:存在经过所有边一次(可以多次经过点)的路径的图哈密顿图:存在经过所有点一次的路径的图

9. 图计算框架有哪些Graphscope怎么样

1.一切的起源:Pregel 虽然图计算本身的历史比计算机的还要长,但如果说要找一个现代图计算框架的起源的话,由 Google 在 10 年的 SIGMOD 上公开的 Pregel 系统应该是众望所归的。 ...

10. 图计算软件GraphX和Graphscope有什么区别

一个是图数据库，一个是图数据分析，可以理解为GeaBase是存储数据的柜子，GraphScope就是在这个柜子里找东西的整个过程。但是GraphScope号称是一站式的平台，所以它里面应该也有些图数据库基础的功能。