数据结构——图(C语言)

这篇具有很好参考价值的文章主要介绍了数据结构——图(C语言)。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

目录

1.图的基本概念

 2.图的相关定义

 3.图的顶点与边之间的关系

 4.连通图

 5.图的存储结构

(1).邻接矩阵(无向图)

 (2).邻接矩阵(有向图)

(3).邻接矩阵(网)

 


1.图的基本概念

(Graph)是由顶点的有穷非空集合和顶点之间的集合组成,通常表示为:G(V,E),其中,G表示一个图,V是图G中顶点的集合,E是图G中边的集合。

c语言图,数据结构,图论

 注意:在图中数据元素叫做“顶点”;任意两个顶点之间都可能有关系,顶点之间的逻辑关系用“边”来表示,边集可以是空的(只有顶点),但是顶点集合一般要求有穷非空。


 

 2.图的相关定义

  • 无向边:若顶点Vi到Vj之间的边没有方向。则称这条边为无向边(Edge),用无序偶(Vi,Vj)来表示。

c语言图,数据结构,图论
G1

 如上图G1是一个无向图,G1={V1,E1},其中

—V1={A,B,C,D};

—E1={(A,B),(B,C),(C,D),(D,A),(A,C)}

  • 有向边:若从顶点Vi到Vj的边有方向,则称这条边为有向边,也称为弧(Arc),用有序偶<Vi,Vj>来表示,Vi称为弧尾,Vj称为弧头。
c语言图,数据结构,图论
G2

 上图G2是一个有向图,G2={V2,E2},其中

—V2={A,B,C,D},

—E2={<B,A>,<B,C>,<C,A>,<A,D>}

  • 简单图:在图结构中,若不存在顶点到其自身的边,且同一条边不重复出现,则称这样的图为简单图。以下两个则不属于简单图:

c语言图,数据结构,图论

  •  无向完全图:在无向图中,如果任意两个顶点之间都存在边,则称该图为无向完全图。含有n个顶点的无向完全图有n*(n-1)/2条边。如下图:

c语言图,数据结构,图论

  •  有向完全图:在有向图中,如果任意两个顶点之间都存在方向互为相反的两条弧,则称该图为有向完全图。含有n个顶点的有向完全图有n*(n-1)条边。如下图:

c语言图,数据结构,图论

  •  稀疏图和稠密图:这里的稀疏和稠密是有些模糊的概念,都是相对而言的,通常认为边或弧数小于n*logn(n是顶点个数)的图称为稀疏图,反之称为稠密图。
  • 带权的图:有些图的边或弧带有与它相关的数字,这种与图的边或弧相关的数叫做(Weight),带权的图通常称为网(Network)。 如下图:

c语言图,数据结构,图论

  •  子图:假设有两个图G1=(V1,E1)和G2=(V2,E2),如果V2⊆V1,E2⊆E1,则称G2为G1的子图(Subgraph)。

 

 3.图的顶点与边之间的关系

  • 邻接点:对于无向图G=(V,E),如果边(V1,V1)∈E,则称顶点V1和V2互为邻接点(Adjacent),即V1和V2相邻接。边(V1,V2)依附于顶点V1和V2,或者说(V1,V2)与顶点V1和V2相关联。对于有向图G=(V,E),如果有<V1,V2>∈E,则称顶点V1邻接到顶点V2,顶点V2邻接自顶点V1。
  • 度(Degree):顶点V的度是和V相关联的边的数目,记为TD(V),如下图,顶点A与B互为邻接点,边(A,B)依附于顶点A与B上,顶点A的度为3。

c语言图,数据结构,图论

  •  入度、出度:以顶点V为头的弧的数目称为V的入度(InDegree),记为ID(V),以V为尾的弧的数目称为V的出度(OutDegree),记为OD(V),因此顶点V的度为:TD(V)=ID(V)+OD(V)。如下图顶点A的入度是2,出度是1,所以顶点A的度是3。

    c语言图,数据结构,图论

     
  •  路径的长度是路径上的边或弧的数目。
  • 第一个顶点到最后一个顶点相同的路径称为回路或环(Cycle)。
  • 序列中顶点不重复出现的路径称为简单路径,除了第一个顶点和最后一个顶点之外,其余顶点不重复出现的回路,称为简单回路或简单环。如下图,左侧是简单环,右侧不是简单环。

 c语言图,数据结构,图论


 

 4.连通图

定义:在无向图G中,如果从顶点V1到顶点V2有路径,则称V1和V2是连通的,如果对于图中任意两个顶点Vi和Vj都是连通的,则称G是连通图。如下图,左侧不是连通图,右侧是连通图:

c语言图,数据结构,图论

连通分量:无向图中的极大连通子图称为连通分量。

注意:首先要是子图,并且子图是要连通的;连通子图含有极大顶点数;具有极大顶点数的连通子图包含依附于这些顶点的所有边。

 强连通图:在有向图中,如果对于每一对Vi到Vj都存在路径,则称G是强连通图。

强连通分量:有向图中的极大强连通子图称为有向图的强连通分量。下图中右侧是强连通图,左侧不是。并且右侧是左侧的极大强连通子图,也是左侧的强连通分量。

c语言图,数据结构,图论


 

 5.图的存储结构

(1).邻接矩阵(无向图)

图的邻接矩阵存储方式是用两个数组来表示图。一个一维数组存储图中顶点信息,一个二维数组(称为邻接矩阵)存储图中的边或弧的信息。

c语言图,数据结构,图论

顶点数组: V0 V1 V2 V3
V0 V1 V2 V3
V0 0 1 1 1
V1 1 0 1 0
V2 1 1 0 1
V3 1 0 1 0

 如上,我们设置了两个数组,顶点数组为vertex[4]={V0,V1,V2,V3},边数组arc[4][4]为对称矩阵(0表示不存在顶点间的边,1表示顶点间存在边)。

上面第二个表是以对角线为对称轴的对称表,由此我们引入了对称矩阵的概念:所谓对称矩阵就是n阶矩阵的元满足a[i][j]=a[j][i](0<=i,j<=n)。即从矩阵的左上角到右下角的主对角线为轴,右上角的元与左下角对应的元全都是相等的。

从这个二维数组组成的对称矩阵我们可以很容易的知道图中的信息:根据0或1来判定任意两个顶点之间是否有边;某个顶点的就是这个顶点Vi在邻接矩阵中第i行(或第i列)的元素之和;求顶点Vi的所有邻接点就是将矩阵中第i行元素扫描一遍,arc[i][j]为1的就是邻接点。

 (2).邻接矩阵(有向图)

无向图的边构成了一个对称矩阵,看起来浪费了一半的空间,那如果我们是存放有向图会怎样呢?

c语言图,数据结构,图论

顶点数组: V0 V1 V2 V3
V0 V1 V2 V3
V0 0 0 0 1
V1 1 0 1 0
V2 1 1 0 0
V3 0 0 0 0

 可见顶点数组vertex[4]={V0,V1,V2,V3},弧数组arc[4][4]也是一个矩阵,但因为是有向图,所以这个矩阵并不对称,例如由V1到V0有弧,的到arc[1][0]=1,而V0到V1没有弧,因此arc[0][1]=0。

 有向图要考虑入度和出度,顶点V1的入度为1,正好是第V1列的各数之和,顶点V1的出度为2,正好是第V2行的各数之和

(3).邻接矩阵(网)

 在图的定义中我们提到了网这个概念,事实上也就是每条边上都带有权的图叫做网。

c语言图,数据结构,图论

顶点数组: V0 V1 V2 V3
V0 V1 V2 V3
V0 0 18
V1 8 0 2
V2 4 0
V3 0

 这里的“∞”表示一个计算机允许的,大于所有边上权值的值。

 

 征战尚未结束,你我仍需努力!

后续更精彩~~文章来源地址https://www.toymoban.com/news/detail-753405.html

到了这里,关于数据结构——图(C语言)的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 【数据结构与算法】图论及其相关算法

    线性表局限于一个直接前驱和一个直接后继的关系,树也只能有一个直接前驱也就是父节点,当我们需要表示多对多的关系时, 这里我们就用到了图。 图是一种数据结构,其中结点可以具有零个或多个相邻元素。两个结点之间的连接称为边。 结点也可以称为顶点。如图:

    2024年02月09日
    浏览(40)
  • 数据结构的应用场景:如社交网络、路由算法、图论、网络协议等

    作者:禅与计算机程序设计艺术 数据结构(Data Structure)是计算机科学中存储、组织、管理数据的方式,主要用于解决信息检索、处理和运算时的效率及空间占用问题。它是指数据元素(elements)之间的关系、顺序和逻辑结构,以及相互作用的算法。数据结构通常采用抽象数据类

    2024年02月14日
    浏览(47)
  • 【C++数据结构 | 图速通】10分钟掌握邻接矩阵 & 邻接表 | 快速掌握图论基础 | 快速上手抽象数据类型图

    by.Qin3Yu 请注意:严格来说,图不是一种数据结构,而是一种抽象数据类型。但为了保证知识点之间的相关性,也将其列入数据结构专栏。 本文需要读者掌握顺序表和单链表的操作基础,若需学习,可参阅我的往期文章: 【C++数据结构 | 顺序表速通】使用顺序表完成简单的成

    2024年02月05日
    浏览(45)
  • 【数据结构】C语言结构体详解

    目录 前言 一、结构体的定义 二、定义结构体变量 三、结构体变量的初始化 四、使用typedef声明新数据类型名 五、指向结构体变量的指针 总结 🌈嗨!我是Filotimo__🌈。很高兴与大家相识,希望我的博客能对你有所帮助。 💡本文由Filotimo__✍️原创,首发于CSDN📚。 📣如需转

    2024年02月04日
    浏览(49)
  • 『初阶数据结构 • C语言』① - 数据结构为何重要

    本文内容借鉴一本我非常喜欢的书——《数据结构与算法图解》。学习之余,我决定把这本书精彩的部分摘录出来与大家分享。 数组是计算机科学中最基本的数据结构之一。如果你用过数组,那么应该知道它就是一个含有 数据的列表。它有多种用途,适用于各种场景,下面

    2024年02月16日
    浏览(47)
  • R语言数据结构(三)数据框

    数据结构是指在计算机中存储和组织数据的方式,不同的数据结构有不同的特点和适用场景。R语言中的常用数据结构,包括向量、矩阵、数组、列表和数据框。关于数据结构的使用,我们将分四篇文章分别介绍每种数据结构的操作方法和代码示例。 为方便大家理解记忆,对

    2024年01月15日
    浏览(39)
  • 【C语言】【数据结构】自定义类型:结构体

    这是一篇对结构体的详细介绍,这篇文章对结构体声明、结构体的自引用、结构体的初始化、结构体的内存分布和对齐规则、库函数offsetof、以及进行内存对齐的原因、如何修改默认对齐数、结构体传参进行介绍和说明。                  ✨  猪巴戒 :个人主页✨      

    2024年02月05日
    浏览(35)
  • 数据结构初阶(用C语言实现简单数据结构)--栈和队列

    ✨✨欢迎来到T_X_Parallel的博客!!       🛰️博客主页:T_X_Parallel       🛰️专栏 : 数据结构初阶       🛰️欢迎关注:👍点赞🙌收藏✍️留言 这小猫真好看 言归正传,通过上篇有关顺序表和链表的博客,可以了解到线性表的一些大致特征,这篇博

    2024年02月08日
    浏览(42)
  • 数据结构——二叉树基础结构篇(C语言)

    现在是北京时间2023年6月13日9点11分。从决定要开始减脂之后,饥饿总是伴随着我。一觉起来肚子咕咕叫,我还是想先把文章发了再吃第一餐。燕麦加蛋白粉几乎伴随了我大学的第一年早饭。昨天练了一个小时背,练背后还做了45分钟有氧。空腹训练没有影响我的训练状态。这

    2024年02月08日
    浏览(39)
  • 数据结构——队列(C语言)

    本篇文章将解决一下几个问题: 队列是什么? 如何实现一个队列? 什么场景下会用队列? 队列:一种只允许一端进行插入数据操作,在另一端进行删除操作的特殊线性表。队列具有先进先出(FIFO)入队列:进行插入操作的一端称为队尾,出队列的一端叫做队头。  队列也

    2024年02月11日
    浏览(44)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包