【数据结构与算法】图的概述(内含源码)

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

个人主页:【😊个人主页】
系列专栏:【❤️数据结构与算法】
学习名言:天子重英豪,文章教儿曹。万般皆下品,惟有读书高——《神童诗劝学》


【数据结构与算法】图的概述(内含源码)


系列文章目录

第一章 ❤️ 学前知识
第二章 ❤️ 单向链表
第三章 ❤️ 递归



前言

与线性表中的元素是“一对一”的关系和树中的元素是“一对多”的关系不同的是,数据结构中图的元素则是“多对多”的关系。图(Graph)是一种复杂的非线性结构,在图结构中,每个元素都可以有零个或多个前驱,也可以有零个或多个后继,也就是说,元素之间的关系是任意的,今天就让我来带大家了解数据结构中图结构吧。


什么是图?

在计算机科学中,一个图就是一些顶点的集合,这些顶点通过一系列边结对(连接)。顶点用圆圈表示,边就是这些圆圈之间的连线。顶点之间通过边连接。
顶点有时也称为节点或者交点,边有时也称为链接
图有各种形状和大小。边可以有权重(weight),即每一条边会被分配一个正数或者负数值。

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

【数据结构与算法】图的概述(内含源码)


图的分类

图按照无方向和有方向分为:无向图和有向图。

【数据结构与算法】图的概述(内含源码)

不带有箭头指向的图只由顶点和边构成称为无向图,有向图是由顶点和弧(有向边构成)。弧有弧头和弧尾区别。

图按照边分为:稀疏图和稠密图

这是个模糊的概念,同样是相对的概念。

完全图

如果任意两个顶点之间都存在边叫完全图,有向的边叫有向完全图。如果无重复的边或者顶点到自身的边叫简单图。在用数学方式表示时,无向边用()表示,有向边用<>表示。我们目前接触到的图全是简单图。

【数据结构与算法】图的概述(内含源码)没有重复的边或者到自身的边(简单图),右图则有

【数据结构与算法】图的概述(内含源码)这种边带权值的图叫网


顶点与边

顶点与边的关系

  • 顶点的度:顶点关联边的数目。有向图图中有,入度:方向指向顶点的边;出度:方向背向顶点的边。在有向图中顶点的度就是两者之和。
  • 路径长度:路径上边或者弧的数目。

图的存储结构

理论上,图就是一堆顶点和边对象而已,那我们又如何用代码来实现它呢?

通常我们有两种选择:邻接列表和邻接矩阵。

邻接列表

邻接表,存储方法跟树的孩子链表示法相类似,是一种顺序分配和链式分配相结合的存储结构。如这个表头结点所对应的顶点存在相邻顶点,则把相邻顶点依次存放于表头结点所指向的单向链表中。
对于无向图来说,使用邻接表进行存储也会出现数据冗余,表头结点A所指链表中存在一个指向C的表结点的同时,表头结点C所指链表也会存在一个指向A的表结点。

【数据结构与算法】图的概述(内含源码)
顶点表的各个结点由data(数据域)和Firstedge(指针域)两个域表示,data是数据域,指针域指向边表的第一个结点,即顶点的第一个邻接点。边表结点由adjvex(邻接点域)和next两个域组成。
邻接点域存储某顶点的邻接点在顶点表中坐标,next存储边表中下一个结点指针。
如图中v1顶点与v2、v0互为邻接点,则在v1边表中,adjvex分别为0和2。
有向图也可以用邻接表,出度表叫邻接表,入度表尾逆邻接表

#include <stdio.h>
#include <stdlib.h>

// 邻接表中每个节点的结构体
struct AdjListNode {
    int dest;
    struct AdjListNode* next;
};

// 邻接表的结构体
struct AdjList {
    struct AdjListNode *head;
};

// 图的结构体
struct Graph {
    int V;
    struct AdjList* array;
};

// 创建一个新的邻接表节点
struct AdjListNode* newAdjListNode(int dest) {
    struct AdjListNode* newNode = (struct AdjListNode*)malloc(sizeof(struct AdjListNode));
    newNode->dest = dest;
    newNode->next = NULL;
    return newNode;
}

// 创建一个具有V个顶点的新图
struct Graph* createGraph(int V) {
    struct Graph* graph = (struct Graph*)malloc(sizeof(struct Graph));
    graph->V = V;

    // 创建邻接表数组
    graph->array = (struct AdjList*)malloc(V * sizeof(struct AdjList));

    // 初始化链表头为空
    for (int i = 0; i < V; ++i)
        graph->array[i].head = NULL;

    return graph;
}

// 添加一个边到无向图
void addEdge(struct Graph* graph, int src, int dest) {
    // 添加一条从src到dest的边
    struct AdjListNode* newNode = newAdjListNode(dest);
    newNode->next = graph->array[src].head;
    graph->array[src].head = newNode;

    // 添加一条从dest到src的边,因为是无向图
    newNode = newAdjListNode(src);
    newNode->next = graph->array[dest].head;
    graph->array[dest].head = newNode;
}

// 打印邻接列表表示的图
void printGraph(struct Graph* graph) {
    for (int v = 0; v < graph->V; ++v) {
        struct AdjListNode* pCrawl = graph->array[v].head;
        printf("\n 邻接列表%d: ", v);
        while (pCrawl) {
            printf("-> %d", pCrawl->dest);
            pCrawl = pCrawl->next;
        }
        printf("\n");
    }
}

int main() {
    // 创建一个具有5个顶点的新图
    struct Graph* graph = createGraph(5);

    // 添加边
    addEdge(graph, 0, 1);
    addEdge(graph, 0, 2);
    addEdge(graph, 1, 2);
    addEdge(graph, 1, 3);
    addEdge(graph, 2, 3);
    addEdge(graph, 2, 4);
    addEdge(graph, 3, 4);

    // 打印邻接列表表示的图
    printGraph(graph);

    return 0;
}

邻接矩阵

邻接矩阵(Adjacency Matrix):是表示顶点之间相邻关系的矩阵。设G=(V,E)是一个图,其中V={v1,v2,…,vn}。G的邻接矩阵是一个具有下列性质的n阶方阵:
【数据结构与算法】图的概述(内含源码)

  • 对无向图而言,邻接矩阵一定是对称的,而且主对角线一定为零(在此仅讨论无向简单图),副对角线不一定为0,有向图则不一定如此。
  • 在无向图中,任一顶点i的度为第i列(或第i行)所有非零元素的个数,在有向图中顶点i的出度为第i行所有非零元素的个数,而入度为第i列所有非零元素的个数。
  • 用邻接矩阵法表示图共需要n^2个空间,由于无向图的邻接矩阵一定具有对称关系,所以扣除对角线为零外,仅需要存储上三角形或下三角形的数据即可,因此仅需要n(n-1)/2个空间
#include <stdio.h>

#define MAX_NODES 100

int adj_matrix[MAX_NODES][MAX_NODES];

void add_edge(int start, int end) {
    adj_matrix[start][end] = 1;
    adj_matrix[end][start] = 1; // 无向图需要将两个方向都标记为已连接
}

int main() {

    // 添加边
    add_edge(0, 1);
    add_edge(0, 2);
    add_edge(1, 2);
    add_edge(2, 3);

    // 输出邻接矩阵
    printf("邻接矩阵:\n");
    for (int i = 0; i < MAX_NODES; i++) {
        for (int j = 0; j < MAX_NODES; j++) {
            printf("%d ", adj_matrix[i][j]);
        }
        printf("\n");
    }

    return 0;
}

图的定义和术语总结

顶点(Vertex):图中的数据元素通常称为顶点
弧(Arc):若< v,w >∈VR,则< v,w >表示从v到w的一条弧
弧尾(Tail):v为弧尾或初始点(Initial node)
弧头(Head):w为弧头或终端点(Terminal node)
有向图(Digraph):图中每条边都有方向
无向图(Undigraph):图中每条边都没有方向
连通图(Connected Graph):对于图中任意两个顶点v,j∈V,v和j都是连通的,则称G是连通图
连通分量(Connected Compenent):无向图中的极大连通子图
完全图(Completed graph):有1/2*n(n-1)条边的无向图称为完全图
有向完全图:具有n(n-1)条弧的有向图称为有向完全图
稀疏图(Sparse graph):有很少条边或弧(如e < nlogn)的图称为稀疏图
稠密图(Dense graph):有很多条边或弧
权(Weight):有时图的边或弧具有与它相关的数,这种与图的边或弧相关的数叫做权
度(Degree):定点v的度是和v相关联的边的数目,记为TD(V)
入度(InDegree):以顶点v为头的弧的数目称为v的入度,记为ID(v)
出度(Outdegree):以v为尾的弧的数目成为v的出度,记为OD(v)
V: 是顶点的有穷非空集合
VR:是两个顶点之间的关系的集合
n:表示图中顶点数目
e:表示边或弧的数目

【数据结构与算法】图的概述(内含源码)文章来源地址https://www.toymoban.com/news/detail-439515.html

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

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

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

相关文章

  • 【数据结构与算法】图的遍历与拓扑排序

    再上一篇中我们讲了树的两种存储方式:【数据结构与算法】图——邻接表与邻接矩阵 这一篇我们可以用数组来模拟邻接表。 假设现在我们要进行n次操作,实现无向图。 首先需要一个 保存是哪个节点 的数组 e 然后就是类似指针数组的 表 h ,每个表都会连一串单链表 e,ne

    2024年02月04日
    浏览(46)
  • 【数据结构与算法】图的深度优先和广度优先遍历

    😊😊作者简介😊😊 : 大家好,我是南瓜籽,一个在校大二学生,我将会持续分享Java相关知识。 🎉🎉个人主页🎉🎉 : 南瓜籽的主页 ✨✨座右铭✨✨ : 坚持到底,决不放弃,是成功的保证,只要你不放弃,你就有机会,只要放弃的人,他肯定是不会成功的人。 图是一

    2024年02月02日
    浏览(58)
  • 学习高级数据结构:探索平衡树与图的高级算法

    🎉欢迎来到数据结构学习专栏~学习高级数据结构:探索平衡树与图的高级算法 ☆* o(≧▽≦)o *☆嗨~我是IT·陈寒🍹 ✨博客主页:IT·陈寒的博客 🎈该系列文章专栏:数据结构学习 📜其他专栏:Java学习路线 Java面试技巧 Java实战项目 AIGC人工智能 数据结构学习 🍹文章作者技

    2024年02月09日
    浏览(46)
  • 【数据结构与算法】图的搜索——广度优先遍历、最小生成树

    邻接链表: 用字典实现.有向图的邻接链表的总长度等于图的边个数;无向图的邻接链表的总长度等于图的边个数的2倍. 邻接矩阵:用于最短路径算法. 该数据结构维护一个不相交动态集的集合,每个集合有一个代表,不关心谁做代表。 支持三种操作: MAKE_SET(x) FIND_SET(x) UNION(x,y

    2024年02月19日
    浏览(50)
  • 算法数据结构——图的遍历之深度优先搜索算法(Depth First Search)

    深度优先搜索算法 (Depth First Search):英文缩写为 DFS。是一种用于搜索树或图的算法。所谓深度优先,就是说每次都尝试向更深的节点走。 深度优先搜索采用了回溯思想,该算法沿着树的深度遍历树的节点,会尽可能深的搜索树的分支。当节点 v 的所在边都己被探寻过,搜

    2024年02月09日
    浏览(50)
  • C语言数据结构——图的最短路径算法解决实例问题

    一、问题描述 W公司在某个地区有6个产品销售点,现根据业务需要打算在其中某个销售点上建立一个中心仓库,负责向其他销售点提供产品。由于运输线路不同,运输费用也不同。假定每天需要向每个销售点运输一次产品,那么应将中心仓库建在哪个销售点上,才能使运输费

    2024年02月08日
    浏览(48)
  • 【数据结构】无向图的最小生成树(Prime,Kruskal算法)

    连通图 :在 无向图 中,若从顶点v1到顶点v2有路径,则称顶点v1与顶点v2是连通的。如果图中 任意一对顶点都是连通的 ,则称此图为连通图 强连通图 :在 有向图 中,若在每一对顶点vi和vj之间都存在一条从vi到vj的路径,也存在一条从vj到vi的路径,则称此图是强连通图 生成

    2024年01月24日
    浏览(48)
  • 数据结构与算法:概述

    目录 算法 评价标准 时间的复杂度 概念 推导原则 举例 空间的复杂度 定义 情形 运用场景 数据结构 组成方式 在数学领域,算法是解决某一类问题的公式和思想; 计算机科学领域,是指一系列程序指令,用于解决特定的运算和逻辑问题; 衡量算法好坏的重要标准是:时间复

    2024年02月09日
    浏览(44)
  • 数据结构和算法概述

    官方解释: 数据结构是一门研究非数值计算的程序设计问题中的操作对象,以及他们之间的关系和操作等相关问题的学科。 大白话: 数据结构就是把数据元素按照一定的关系组织起来的集合,用来组织和存储数据 传统上,我们可以把数据结构分为逻辑结构和物理结构两大类

    2024年02月08日
    浏览(36)
  • 数据结构学习笔记——图的遍历算法(深度优先搜索和广度优先搜索)

    图的遍历指从图中某一顶点出发(任意一个顶点都可以作为访问的起始顶点),按照某种遍历方法,对图中所有的顶点访问一次且只访问一次。图与树不一样,其中一个顶点可能与多个顶点相连,所以需记录已访问过的顶点,当访问一个顶点后,考虑如何选取下一个要访问的

    2024年02月05日
    浏览(53)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包