第五章 图论 邻接表存图

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

邻接表存图

存储结构

#define MaxSize 10
typedef char DataType;
typedef struct EdgeNode{ // 定义边表节点 
    int adjvex;
    struct EdgeNode *next; 
} EdgeNode;

typedef struct{ // 定义顶点表结点
    DataType vertex;
    EdgeNode *first;
} vertexNode;

typedef struct{
    vertexNode adjlist[MaxSize]; // 存放顶点表的数组
    int vertexNum, edgeNum; // 图的顶点数和边数
} ALGraph;

有向图邻接表的建立

void CreateGraph(ALGraph *G, DataType a[], int n, int m){
    G->vertexNum=n, G->edgeNum=m;
    for(int i=0; i<n; i++){
        G->adjlist[i].vertex=a[i];
        G->adjlist[i].first=NULL;
    }
    for(int i=0; i<m; i++){
        int x, y;
        scanf("%d%d", &x, &y);
        EdgeNode *s=(EdgeNode*)malloc(sizeof(EdgeNode));
        s->adjvex=y;
        s->next=G->adjlist[x].first;
        G->adjlist[x].first=s;
    }
}

图的销毁

void DestroyGraph(ALGraph *G){
    for(int i=0; i<G->vertexNum; i++){
        EdgeNode *p, *q;
        p=q=G->adjlist[i].first;
        while(p != NULL){
            p=p->next;
            free(q);
            q=p;
        }
    }
}

深度优先遍历

void dfs(ALGraph *G, int r){
    printf("%c ", G->adjlist[r].vertex);
    st[r]=1;

    EdgeNode *p=G->adjlist[r].first;
    while(p != NULL){
        int u=p->adjvex;
        if(st[u]==0) dfs(G, u);
        p=p->next;
    }
}

广度优先遍历

void bfs(ALGraph *G, int r){
    int Q[MaxSize];
    int front=-1, rear=-1;
    printf("%c ", G->adjlist[r].vertex);
    st[r]=1; Q[++rear]=r;

    while(front != rear){
        int u=Q[front ++];
        EdgeNode *p=G->adjlist[u].first;
        while(p != NULL){
            int v=p->adjvex;
            if(st[v]==0){
                printf("%c ", G->adjlist[v].vertex);
                st[v]=1; Q[++rear]=v;
            }
            p=p->next;
        }
    }
}

文章来源地址https://www.toymoban.com/news/detail-775317.html

到了这里,关于第五章 图论 邻接表存图的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

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

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

相关文章

  • 一张图带你看完图论第五章(包含全部考点,含定义、定理、公式、推导证明和所有例题)

    付费大佬可以联系我把你们加入思维导图协作,看更加具体清楚地思维导图/敬礼 5.1 匹配 匹配(边独立集)M是G的不相邻边组成的边子集(无环) 饱和点 v是匹配M中某边的端点,则称v为M饱和点 完美匹配 G中每个顶点均为M饱和点,则M为G的完美匹配 最优匹配 在赋权完全偶图

    2024年02月09日
    浏览(52)
  • 王道考研数据结构第五章知识点

    5.1.1 树的定义和基本术语   祖先节点:(对于你来说),父亲和爷爷都是祖先节点 子孙节点:对于父亲来说,父亲下面所有的节点都叫子孙节点 双亲节点(父节点):一个节点的直接前驱就是它的父节点  兄弟节点:例如二叔,三叔都是父亲的兄弟节点 堂兄弟节点:对于你来说,

    2024年02月15日
    浏览(51)
  • 数据结构与算法分析 第五章 树和二叉树 作业讲解

     参考教材: 《数据结构(C语言版 第2版)》 严蔚敏,李冬梅,吴伟民编著,人民邮电出版社,2022年版。 截图未标明出处均为原创或取自《数据结构(C语言版 第2版)》~   本文对应的作业题讲解视频:   数据结构与算法分析作业讲解视频合集 https://www.bilibili.com/video/BV1N

    2024年02月02日
    浏览(37)
  • 数据结构(c++语言版) 邓俊辉 第五章:二叉树学习笔记

    5.1二叉树及其表示         树是由节点和边组成的。 1.有根树         树是由顶点(vertex)和边(edge)组成。树的每个顶点也叫节点(node)。 2.深度与层次         由树的连通性,每一节点与根都有一条路径相连:根据树的无环性,由根通往每个节点的路径必然唯一。  

    2024年02月13日
    浏览(44)
  • 【Rust】Rust学习 第五章使用结构体组织相关联的数据

    定义结构体,需要使用  struct  并为整个结构体提供一个名字。结构体的名字需要描述它所组合的数据的意义。接着,在大括号中,定义每一部分数据的名字和类型,我们称为  字段 ( field )。 实例化(不可变变量) 可变变量 字段初始化简写语法 通过已经存着的变

    2024年02月13日
    浏览(46)
  • 数据结构英文习题解析-第五章 二叉搜索树Binary Search Tree

    前言:最近快到FDS考试了,po重刷了一下学校的题目,自己整理了一些解析orz 因为po在自己找解析和学习的过程中非常痛苦,所以在此共享一下我的题目和自己写的解题思路,欢迎各位指出错误~全章节预计会陆续更新,可在专栏查看~ HW5 1.In a binary search tree, the keys on the same

    2024年04月09日
    浏览(48)
  • 图论基础: 邻接矩阵与邻接表(c++实现)

    邻接矩阵(Adjacency Matrix)是表示 顶点之间相邻关系 的矩阵。 设G=(顶点,边):G=(V,E)是一个图。其中V={v1,v2,…,vn} [1] 。G的邻接矩阵是一个具有下列性质的n阶方阵: 无向图的邻接矩阵一定是成对角线对称的,是一个 对称矩阵 ,有向图 不一定 是对称的。 有向图当把它的 行

    2024年02月05日
    浏览(40)
  • 图论01-【无权无向】-图的基本表示-邻接矩阵/邻接表

    https://github.com/Chufeng-Jiang/Graph-Theory/tree/main/src/Chapt01_Adjacency 代码有删减 代码有删减 只需要改动一行 adj = new TreeSet[V]; //构造邻接表, V行,V个LinkedList 代码有删减

    2024年02月07日
    浏览(40)
  • 图论之邻接表

    路径规划算法综述 图论基础介绍 图论之邻接矩阵 目录  路径规划系列文章目录 一、邻接表 二、邻接表实现 2.1 链式前向星实现 2.2 链表实现 三、总结         由于对于稀疏图来说,使用邻接矩阵进行存储显然会使得空间利用率较低,因此利用邻接表来存储图,可以克服

    2024年02月04日
    浏览(37)
  • 图论之邻接矩阵

    路径规划算法综述 图论基础介绍 目录 路径规划系列文章目录 一、图的存储方式介绍 二、邻接矩阵介绍 三、邻接矩阵实现 四、总结          图的结构比较复杂,是非线性结构,任意两点都可能存在联系,相对来说存储方法较多。目前主要有: 邻接矩阵表示法 邻接表表

    2024年02月06日
    浏览(32)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包