IT数码 购物 网址 头条 软件 日历 阅读 图书馆
TxT小说阅读器
↓语音阅读,小说下载,古典文学↓
图片批量下载器
↓批量下载图片,美女图库↓
图片自动播放器
↓图片自动播放器↓
一键清除垃圾
↓轻轻一点,清除系统垃圾↓
开发: C++知识库 Java知识库 JavaScript Python PHP知识库 人工智能 区块链 大数据 移动开发 嵌入式 开发工具 数据结构与算法 开发测试 游戏开发 网络协议 系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑 笔记本 显卡 显示器 固态硬盘 硬盘 耳机 手机 iphone vivo oppo 小米 华为 单反 装机 图拉丁
 
   -> 数据结构与算法 -> 图的存储结构 -> 正文阅读

[数据结构与算法]图的存储结构

图的存储结构

G = ( V , E ) G=(V,E) G=VE) V V V表示顶点集合, E E E表示边集合

邻接矩阵

是顺序存储结构

邻接矩阵是表示顶点之间相邻关系的矩阵。

设G=(V,E)是具有n(n>0)个顶点的图,顶点的编号依次为0~n-1。

特点

一个图的邻接矩阵表示是唯一的。

特别适合于稠密图的存储。

邻接矩阵的存储空间为O(n2)

不带权图

(1)如果G是无向图,则:

图片来自扬老师课件

  $A[i][j]=1$:若$(i,j)∈E(G)$   0:其他

解释:

矩阵中,0-1-2-3-4分别代表图中各个点,横纵坐标都是代表各个顶点。

对于 A i A_i Ai?这个矩阵,如果第 A [ i ] [ j ] = = 1 A[i][j]==1 A[i][j]==1,那么在无向图中 ( i , j ) (i,j) (i,j)这条边一定存在。

(2)如果G是有向图,则:

请添加图片描述

? A [ i ] [ j ] = 1 A[i][j]=1 A[i][j]=1:若 < i , j > ∈ E ( G ) <i,j>∈E(G) <ij>E(G) 0:其他

对于 A i A_i Ai?这个矩阵,如果第 A [ i ] [ j ] = = 1 A[i][j]==1 A[i][j]==1,那么在无向图中 < i , j > <i,j> <i,j>这条边一定存在。

(3)如果G是带权无向图,则:

用每个点存储权重

? A [ i ] [ j ] = w i j A[i][j]= w_{ij} A[i][j]=wij? :若 i ≠ j i≠j i?=j且(i,j)∈E(G) $ 0:i=j$ ∞ ∞ :其他

(4)如果G是带权有向图,则:

用每个点存储权重

? $ A[i][j]= w_{ij}$ :若{i≠j}且 < i , j > ∈ E ( G ) <i,j>∈E(G) <ij>E(G) 0 : i = j 0:i=j 0i=j   ∞ ∞ :其他

代码

#define  MAXV  <最大顶点个数>	//#define 是宏定义
typedef struct      //这个结构体定义,每个顶点的信息。
{  int no;			//顶点编号
   InfoType info;		//顶点其他信息,* InfoType 这个不是类型,需要自己定义,你可以存一个字符串,数组,一个数字都可以,都表示这个顶点的信息。
} VertexType;

typedef struct  		//图的定义
{  int edges[MAXV][MAXV]; 	//邻接矩阵
   int n,e;  			//顶点数,边数
   VertexType vexs[MAXV];	//存放顶点信息
}  MatGraph;

邻接表存储方法

特别适合于稀疏图存储。

邻接表表示不唯一。

邻接表的存储空间为O(n+e)

定义

step1:

对图中每个顶点i建立一个单链表,将顶点 i i i的所有直接相邻接点链起来。
请添加图片描述

step2:

每个单链表上添加一个表头结点(表示顶点信息)。并将所有表头结点构成一个数组,下标为 i i i的元素表示顶点 i i i的表头结点。

请添加图片描述

图的邻接表是 顺序分配?链式分配

我们从头节点找对应的顶点,在边节找到点中存储信息。

实例

请添加图片描述

对于2、3顶点他们没有后续节点,所以不是指向的为空,而是这个头节点存储为空

代码

typedef struct ANode//链节点
{  int adjvex;			//该边的终点编号
   struct ANode *nextarc;	//指向下一条边的指针
   InfoType weight;		//该边的权值等信息
}  ArcNode;

typedef struct Vnode//头节点
{  Vertex data;		//顶点信息
   ArcNode *firstarc;		//指向第一条边
}  VNode;

typedef struct 
{  VNode adjlist[MAXV];	//邻接表
   int n,e;			//图中顶点数n和边数e
} AdjGraph;

### 空间资源对比

当图是稠密图时,边非常多,每个点对应的边也非常多。 O ( n + e ) O(n+e) O(n+e)中 e甚至会到达 e = n ? ( n ? 1 ) e=n*(n-1) e=n?n?1的空间,而邻接表始终是 O ( n 2 ) O(n^2) O(n2)

当图是稀疏图时,边很少,邻接表对应 O ( n 2 ) O(n^2) O(n2)中存在很多0,造成空间浪费,而稠密图 O ( n + e ) O(n+e) O(n+e)中 e很小,甚至最小可以到达0

  • 如有疑问:请前往http://www.i5201314.top留言咨询
  • 请收藏,避免迷路。
  数据结构与算法 最新文章
【力扣106】 从中序与后续遍历序列构造二叉
leetcode 322 零钱兑换
哈希的应用:海量数据处理
动态规划|最短Hamilton路径
华为机试_HJ41 称砝码【中等】【menset】【
【C与数据结构】——寒假提高每日练习Day1
基础算法——堆排序
2023王道数据结构线性表--单链表课后习题部
LeetCode 之 反转链表的一部分
【题解】lintcode必刷50题<有效的括号序列
上一篇文章      下一篇文章      查看所有文章
加:2021-11-19 17:52:03  更:2021-11-19 17:52:37 
 
开发: C++知识库 Java知识库 JavaScript Python PHP知识库 人工智能 区块链 大数据 移动开发 嵌入式 开发工具 数据结构与算法 开发测试 游戏开发 网络协议 系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑 笔记本 显卡 显示器 固态硬盘 硬盘 耳机 手机 iphone vivo oppo 小米 华为 单反 装机 图拉丁

360图书馆 购物 三丰科技 阅读网 日历 万年历 2025年1日历 -2025/1/9 1:51:50-

图片自动播放器
↓图片自动播放器↓
TxT小说阅读器
↓语音阅读,小说下载,古典文学↓
一键清除垃圾
↓轻轻一点,清除系统垃圾↓
图片批量下载器
↓批量下载图片,美女图库↓
  网站联系: qq:121756557 email:121756557@qq.com  IT数码