摘要：什么是图前面说完了树这种数据结构，接下来在看看一种更加复杂的非线性数据结构图。其实图这种数据结构比较适合用来存储我们常用的微信微博好友关系。
1. 什么是图？
前面说完了树这种数据结构，接下来在看看一种更加复杂的非线性数据结构——图。
先看看下面图这种数据结构的图片演示吧：
像上图这样的数据结构就叫做图了，图中的每个节点叫做 顶点 ，各个顶点之间的连接关系叫做 边 ，每个顶点有多少条边，叫做这个顶点的 度 。其实图这种数据结构比较适合用来存储我们常用的微信、微博好友关系。例如存储微信好友，例如两个人互加了微信，就相当于在两个顶点之间加上一条边，而顶点的度则表示一个人有多少微信好友。
而微博这样的存储关系，要稍微复杂一些，因为微博允许当方面关注，例如 A 关注了 B ，而 B 可以不关注 A，这样的关系，我们可以在图中引入方向的概念，先看下图：
例如 A 关注了 B，那么直接将 A 的边指向 B 即可。这样有方向关系的图，叫做 有向图 ，显然，没有方向关系的图，就叫做 无向图 。
无向图中有度的概念，表示一个顶点有多少条边，而有向图中的度，则还有 入度 和 出度 的区分，例如 A 指向 B，叫做 A 顶点的出度，E 指向了 A，叫做 A 的入度。不难理解，对应到微博的关系中，一个顶点的出度，就表示他关注了多少人，入度，则表示他有多少粉丝。
2. 图是如何存储的？
图有两种存储的方式，第一种叫做邻接矩阵，其底层是利用二维数组来存储的。对于无向图，如果顶点 i 和 j 之间有边，则在二维数组中 A[i] [j] 和 A[j] [i] 位置处标记为 1 ，对于有向图，如果 i 指向了 j，则将二维数组中 A[i] [j] 位置标记为 1，类似，如果 j 指向了 i，则将二维数组中 A[j] [i] 位置标记为 1。看下图的说明就很容易明白了：
这种存储方式虽然支持较为高效的查找操作，因为可以直接根据数组下标取出数据，但是存在的问题便是比较浪费存储空间，特别是对于数据量较大的情况。
另一种更加常用的图存储方式是邻接表，每个顶点对应一个链表，就像下图这样：
上面是使用的有向图，每个顶点对应的链表存储的是该顶点所指向的顶点，如果是无向图的话，那就更简单了，每个顶点链表存储的是与该顶点有边关系的顶点。
3. 简单实现一个图
接下来我是用代码简单使用了一个图，你可以看看，顺便理解一下：
public class Graph {
private int vertex;//图中的顶点个数
private LinkedList[] list;
public Graph(int vertex) {
this.vertex = vertex;
list = new LinkedList[vertex];
for (int i = 0; i < vertex; i++) {
list[i] = new LinkedList();
}
}
//两个顶点之间建立边关系
public void addSide(int v1, int v2){
if (v1 >= vertex || v2 >= vertex || v1 == v2) return;
if (!list[v1].contains(v2))
list[v1].add(v2);
if (!list[v2].contains(v1))
list[v2].add(v1);
}
//删除顶点之间的边
public void removeSide(int v1, int v2){
if (v1 >= vertex || v2 >= vertex || v1 == v2) return;
if (list[v1].contains(v2))
list[v1].remove(v2);
if (list[v2].contains(v1))
list[v2].remove(v1);
}
//列出与某顶点有边关系的所有顶点
public void listVertexes(int v){
if (v >= vertex) return;
System.out.println(list[v].toString());
}
}
文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。
转载请注明本文地址：https://www.ucloud.cn/yun/74071.html
摘要：在等机构新提出的论文中，其采用了大规模数据集与深度神经网络学习图像的自然结构，从而进一步分离图像的前景与背景。一张手动抠图的前景图拥有简单背景作为输入。对于每一张测试图像，按照降序从第列到第列显示了度量下的排名结果排名到。 抠图，一直是一件体力活，它需要大量的操作与时间。而传统抠图算法主要是以色彩为特征分离前景与背景，并在小数据集上完成，而这就造成了传统算法的局限性。在 Adobe 等机构新...
摘要：图关联矩阵在关联矩阵表示的图中，矩阵的行表示顶点，列表示边。如图，顶点数是，边的数量是，用邻接矩阵表示图需要的空间是，而使用关联矩阵表示图需要的空间是。广度优先搜索算法数据结构是队列。深度优先搜索算法数据结构是栈。 定义 图和散列表、二叉树一样，是一种非线性数据结构。如图1所示，图由一系列顶点以及连接顶点的边构成。由一条边连接在一起的顶点成为相邻顶点，比如A和B、A和D是相邻的，而A和...
摘要：近几年来，目标检测算法取得了很大的突破。本文主要讲述算法的原理，特别是算法的训练与预测中详细细节，最后将给出如何使用实现算法。但是结合卷积运算的特点，我们可以使用实现更高效的滑动窗口方法。这其实是算法的思路。下面将详细介绍算法的设计理念。 1、前言当我们谈起计算机视觉时，首先想到的就是图像分类，没错，图像分类是计算机视觉最基本的任务之一，但是在图像分类的基础上，还有更复杂和有意思的任务，如目...
摘要：在本次课程中，着重讲解的是传统的机器学习技术及各种算法。回归对连续型数据进行预测趋势预测等除了分类之外，数据挖掘技术和机器学习技术还有一个非常经典的场景回归。 摘要： 什么是数据挖掘？什么是机器学习？又如何进行Python数据预处理？本文将带领大家一同了解数据挖掘和机器学习技术，通过淘宝商品案例进行数据预处理实战，通过鸢尾花案例介绍各种分类算法。 课程主讲简介：韦玮，企业家，资深IT领...
阅读 2112·2019-08-30 15:53
阅读 2296·2019-08-30 12:54
阅读 1013·2019-08-29 16:09
阅读 620·2019-08-29 12:14
阅读 644·2019-08-26 10:33
阅读 2269·2019-08-23 18:36
阅读 2794·2019-08-23 18:30
阅读 1979·2019-08-22 17:09
