第五章 图论 邻接矩阵存图

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

邻接矩阵存图

存储结构定义

#define MaxSize 10 // 图中最多顶点个数
typedef char DataType;
typedef strcut{
    DataType vertex[MaxSize];
    int edge[MaxSize][MaxSize];
    int vertexNum, edgeNum;
} Mgraph;

建图

void CreateGraph(Mgraph *G, DataType a[], int n, int m){
    G->vertex=n, G->edgeNum=m;
    for(int i=0; i<n; i++) G->vertex[i]=a[i];
    for(int i=0; i<m; i++) for(int j=0; j<m; j++) G->edge[i][j]=0; // 初始化
    for(int i=0; i<m; i++){
        int x, y;
        scanf("%d%d", &x, &y);
        G->edge[x][y]=G->edge[y][x]=1; // 存边
    }
}

遍历

  • dfs
void dfs(Mgraph *G, int u){ // 全局变量数组 st[n] 初始化为 0
    printf("%c ", G->vertex[u]);
    st[u]=true;
    for(int v=0; v<G->vertexNum; v++){
        if(G->vertex[u][v]==1 && st[v]==0)
            dfs(G, v);
    }
}
  • bfs
void bfs(Mgraph *G, int root){ // 全局变量数组 st[n] 初始化为 0
    int Q[MaxSize];
    int front=-1, rear=-1;
    printf("%c ", G->vertex[root]);
    Q[++rear]=root, st[root]=1;
    while(front != rear){
        int u=Q[front++];
        for(int v=0; v<G->vertexNum; v++)
            if(G->edge[i][j]==1 && st[v]==0){
                printf("%c ", G->vertex[v]);
                Q[++rear]=v, st[v]=1;
            }
    }
}

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

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

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

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

相关文章

  • 图论之邻接矩阵

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

    2024年02月06日
    浏览(32)
  • 图论——邻接矩阵之无向网

    在此之前,我们需要先理清图和网的区别 1.图G:有两个集合,边集V和点集E【点集用来存放各个顶点,边集用来存放各条边来表示关联两点的联系】 2.权值:即即两顶点之间互相往来需要花费的代价或消耗 3.网:带权值的图 所谓邻接矩阵,即用矩阵排布的方式来构建两点之间

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

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

    2024年02月07日
    浏览(40)
  • C++ 图论之求图的连通块数量(邻接矩阵版)

    1. 连通块的定义 块内每个点之间都有一条路径。 2. 思路 我们可以用dfs深度优先搜索:从一个点出发遍历图将遍历过的点全部标记,标记过的点则不会再遍历到。 再写一个循环枚举所有的点(枚举起点),如果没标记就代表可以作为起点,数量加一,进行dfs标记点。 3. 代码

    2024年02月13日
    浏览(47)
  • 第五章 数据结构与算法——八大排序

    目录 一、排序的概念及其运用 二、八大排序的原理及其实现(升序为例) (一)、直接插入排序 (二)、希尔排序(也叫缩小增量排序)(重要) 1.原理: 2.该排序一般分为两个步骤: 3.预排序过程: 4.预排序的意义(升序为例): 5.希尔排序的特点: 6.希尔排序代码实现

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

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

    2024年02月09日
    浏览(52)
  • 【图论】Dijkstra 算法求最短路 - 构建邻接矩阵(带权无向图)

    题目链接:1976. 到达目的地的方案数

    2024年03月22日
    浏览(44)
  • 第五章 OpenGL ES 基础-透视投影矩阵与正交投影矩阵

    第一章 OpenGL ES 基础-屏幕、纹理、顶点坐标 第二章 OpenGL ES 基础-GLSL语法简单总结 第三章 OpenGL ES 基础-GLSL渲染纹理 第四章 OpenGL ES 基础-位移、缩放、旋转原理 第五章 OpenGL ES 基础-透视投影矩阵与正交投影矩阵 模型都是3D的,但屏幕是2D的。如何将3D空间投影到2D平面,还能保

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

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

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

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

    2024年02月02日
    浏览(37)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包