博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
非线性数据结构——图的相关概念
阅读量:4113 次
发布时间:2019-05-25

本文共 789 字,大约阅读时间需要 2 分钟。

1.图的相关概念

用于深度和广度搜索算法一般就是用来做图的遍历,或者说图是搜索算法的最常用数据结构,因此需要先储备一些图的概念。

图是由一个非空的顶点集合和一个边的集合组成。 G=( V, E )
1.无向图:任意两顶点构成的偶对(vi , vj )是无序的。一个顶点的连接边数叫作结点的。一个完全无向图有n(n-1)/2 条边。
2.有向图:顶点之间的关系(边)有方向,因此把度也分成了出度和入度。表示微博中的用户关注度可用
3.带权图:边加了权重的图。表示网络中,QQ好友亲密度度可用
带权图
4.完全图:(1)若 n 个顶点的无向图有 n(n-1)/2 条边, 称为无向完全图
(2)若 n 个顶点的有向图有n(n-1) 条边, 称为有向完全图
5.邻接矩阵:优点是容易实现图的操作,如:求某顶点的度、判断顶点之间是否有边(弧)、找顶点的邻接点等等。缺点是n个顶点需要n*n个单元存储边(弧);空间效率为O(n2)。
在这里插入图片描述
6.邻接表:对每个顶点vi 建立一个单链表,把与vi有关联的边的信息(度)链接起来。优点是空间效率高且容易寻找顶点的邻接点;
以下是无向图及其邻接表:
在这里插入图片描述
先给出用邻接表实现的无向图代码:

public class Graph{
private int v; private LinkedList
adj[]; public Graph(int v){
this.v=v; adj = new LinkedList[v]; for(int i=0;i
(); } } public void addEdge(int s, int t){
adj[s].add(t); adj[t].add(s); }}

转载地址:http://jfrsi.baihongyu.com/

你可能感兴趣的文章
gcc 常用选项详解
查看>>
c++输出文件流ofstream用法详解
查看>>
firewalld的基本使用
查看>>
Linux下SVN客户端使用教程
查看>>
Linux分区方案
查看>>
nc 命令详解
查看>>
如何使用 systemd 中的定时器
查看>>
git命令速查表
查看>>
linux进程监控和自动重启的简单实现
查看>>
OpenFeign学习(三):OpenFeign配置生成代理对象
查看>>
OpenFeign学习(四):OpenFeign的方法同步请求执行
查看>>
OpenFeign学习(五):OpenFeign请求结果处理及重试控制
查看>>
OpenFeign学习(六):OpenFign进行表单提交参数或传输文件
查看>>
OpenFeign学习(七):Spring Cloud OpenFeign的使用
查看>>
Ribbon 学习(二):Spring Cloud Ribbon 加载配置原理
查看>>
Ribbon 学习(三):RestTemplate 请求负载流程解析
查看>>
深入理解HashMap
查看>>
XML生成(一):DOM生成XML
查看>>
XML生成(三):JDOM生成
查看>>
Ubuntu Could not open lock file /var/lib/dpkg/lock - open (13:Permission denied)
查看>>