您现在的位置是:首页 >技术交流 >【数据结构与算法】图的概述(内含源码)网站首页技术交流

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

许思王 2024-06-08 00:00:02
简介【数据结构与算法】图的概述(内含源码)

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


在这里插入图片描述


系列文章目录

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



前言

与线性表中的元素是“一对一”的关系和树中的元素是“一对多”的关系不同的是,数据结构中图的元素则是“多对多”的关系。图(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("
 邻接列表%d: ", v);
        while (pCrawl) {
            printf("-> %d", pCrawl->dest);
            pCrawl = pCrawl->next;
        }
        printf("
");
    }
}

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("邻接矩阵:
");
    for (int i = 0; i < MAX_NODES; i++) {
        for (int j = 0; j < MAX_NODES; j++) {
            printf("%d ", adj_matrix[i][j]);
        }
        printf("
");
    }

    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:表示边或弧的数目

在这里插入图片描述

风语者!平时喜欢研究各种技术,目前在从事后端开发工作,热爱生活、热爱工作。