数据结构与算法——图

简介: 前面说完了树这种数据结构,接下来在看看一种更加复杂的非线性数据结构——图。

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<Integer>[] 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);
相关文章
|
7月前
|
算法
研究生考试.数据结构与算法之十一 图
研究生考试.数据结构与算法之十一 图
34 0
|
9月前
|
存储 算法
第七章 图【数据结构与算法】3
第七章 图【数据结构与算法】3
46 0
|
9月前
|
算法 vr&ar
第七章 图【数据结构与算法】2
第七章 图【数据结构与算法】2
37 0
|
5月前
|
存储 人工智能 算法
第七章 图【数据结构与算法】【精致版】
第七章 图【数据结构与算法】【精致版】
46 0
|
9月前
|
算法 Java
图【数据结构与算法java】
图【数据结构与算法java】
39 0
|
9月前
|
存储 人工智能 算法
第七章 图【数据结构与算法】1
第七章 图【数据结构与算法】1
63 0
|
12月前
|
存储 算法
【数据结构与算法】图的概述(内含源码)
【数据结构与算法】图的概述(内含源码)
76 0
|
存储 算法
数据结构/数据结构与算法实验三 图的相关算法实现
数据结构/数据结构与算法实验三 图的相关算法实现
97 0
数据结构/数据结构与算法实验三 图的相关算法实现
|
移动开发 算法 C++
数据结构与算法之图的应用
一.树之习题选讲-Tree Traversals Again 树习题-TTA.1 题意理解 非递归中序遍历的过程 ● 1. Push的顺序为先序遍历(pre) ● 2. Pop的顺序给出中序遍历(in) ● 树习题-TTA.2 核心算法 上图分别是先序、中序、后序遍历通过规律我们可以看到他们之间的位置分配 //伪代码 void solve(int preL,int inL,int n) { if(n == 0) return;//n等于0的时候什么都不做(n真的会右等于0的时候吗?为什么写他?)调用完了 之后右边没有元素,此时n等于0,进行判断正常结束进程 if(n == 1){p
62 0
|
存储 机器学习/深度学习 算法
【数据结构与算法】图的基本概念 | 邻接矩阵和邻接表 | 广度优先遍历和深度优先遍历
【数据结构与算法】图的基本概念 | 邻接矩阵和邻接表 | 广度优先遍历和深度优先遍历
【数据结构与算法】图的基本概念 | 邻接矩阵和邻接表 | 广度优先遍历和深度优先遍历