数据结构--图（更新ing~）

  树具有灵活性，并且存在许多不同的树的应用，但是就树本身而言有一定的局限性，树只能表示层次关系，比如父子关系。而其他的比如兄弟关系只能够间接表示。

推广---  图

图形结构中，数据元素之间的关系是任意的。

一、图的基本概念

二、图的分类

三、图的相关术语

1、顶点的度

无向图：n个顶点找两条，没有方向，

2、路径和路径长度

3.子图

4.图的连通

1）无向图的连通

2）有向图的连通

5.生成树

#不讨论的图：

四、图的存储方法

1、邻接矩阵存储方法

对称矩阵：

一个对称矩阵是指矩阵的主对角线两侧的元素相等。在这个矩阵中，通过观察可以发现对称性质：矩阵的第i行第j列的元素等于第j行第i列的元素。

**无向图的邻接矩阵建图和度数输出（完整代码）

#define _CRT_SECURE_NO_WARNINGS 1
#include <stdio.h>
#include <string.h>
#define N (100 + 5)
#define INF 0x3f3f3f3f//定义INF为一个十六进制无穷大常量

typedef char VexType; //顶点为字符类型
typedef int EdgeType;//邻接矩阵类型为整型

typedef struct {
    int n, m; //n个顶点，m条边
    VexType vex[N];//一维数组存放所有顶点的数据信息
    EdgeType edge[N][N];//邻接矩阵(二维数组存放图中所有顶点之间关系的信息)
} adjGraph;

//1.邻接矩阵建图
adjGraph createGraph();
//2.输出图的信息（顶点、邻接矩阵）
void print(adjGraph g);
//3.输出图中每个顶点的度数
void printDegree(adjGraph g);

int main()
{
    //1.建图
    adjGraph g = createGraph();
    //2.输出图的信息
    print(g);
    printDegree(g);
    return 0;
}

adjGraph createGraph()//建图
{
    adjGraph g;
    memset(g.edge, 0, sizeof(g.edge));//内存设置函数--创建图的过程中，所有元素初始化为0
    // g.edge 邻接矩阵
    //sizeof(g.edge) 数组占用的总字节数
    scanf("%d%d", &g.n, &g.m);//输入顶点数和边数
    getchar();//吸收换行符
    //1.输入n个顶点
    for (int i = 0; i < g.n; i++) {
        scanf("%c ", &g.vex[i]);
    }
    //2.输入m条边，按照邻接矩阵存图
    for (int i = 0; i < g.m; i++) {
        char v1, v2;
        scanf("\n%c %c", &v1, &v2);//读入当前边的2个顶点
        int n1 = v1 - 'A', n2 = v2 - 'A';
         //将顶点字符转换为对应的数组索引。
        // 假设顶点标签是大写字母'A'、'B'、'C'等，通过将其减去字符'A'的ASCII码值
        // 可以得到对应的数组索引（0、1、2等）。   
        g.edge[n1][n2] = g.edge[n2][n1] = 1;
        //无向图，邻接矩阵对应的n1行n2列和n2n1列都赋值为1(邻接矩阵的对称性）
        //将对应的邻接矩阵元素设置为1，表示图中对应的顶点之间存在一条边。
    }

    return g;
}

void print(adjGraph g)
{
    printf("图有%d个顶点，%d条边\n", g.n, g.m);
    printf("图的顶点是：");
    for (int i = 0; i < g.n; i++) {
        printf("%c ", g.vex[i]);
    }
    printf("\n图的邻接矩阵是：\n");
    for (int i = 0; i < g.n; i++) {
        for (int j = 0; j < g.n; j++) {
            printf("%4d", g.edge[i][j]);
        }
        printf("\n");
    }
}

void printDegree(adjGraph g)
{
    printf("图中每个顶点的度数是：");
    for (int i = 0; i < g.n; i++) {
        int degree = 0;
        for (int j = 0; j < g.n; j++) {
            if (g.edge[i][j] == 1) {
                degree++;
            }
        }
        printf("%c: %d ", g.vex[i], degree);
    }
    printf("\n");
}

输入样例：

**有向图邻接矩阵建图和度数输出（附完整代码）

修改的部分：

  • 将g.edge[n1][n2] = g.edge[n2][n1] = 1; 修改为 g.edge[n1][n2] = 1; 表示从顶点n1指向顶点n2的有向边。
  • 把无向图中的度数输出改成入度和出度输出
#define _CRT_SECURE_NO_WARNINGS 1
#include <stdio.h>
#include <string.h>
#define N (100 + 5)
#define INF 0x3f3f3f3f//定义INF为一个十六进制无穷大常量

typedef char VexType; //顶点为字符类型
typedef int EdgeType;//邻接矩阵类型为整型

typedef struct {
    int n, m; //n个顶点，m条边
    VexType vex[N];//一维数组存放所有顶点的数据信息
    EdgeType edge[N][N];//邻接矩阵(二维数组存放图中所有顶点之间关系的信息)
} adjGraph;

//1.邻接矩阵建图
adjGraph createGraph();
//2.输出图的信息（顶点、邻接矩阵）
void print(adjGraph g);
//3.输出图中每个顶点的度数
void printDegree(adjGraph g);

int main()
{
    //1.建图
    adjGraph g = createGraph();
    //2.输出图的信息
    print(g);
    printDegree(g);
    return 0;
}

adjGraph createGraph()//建图
{
    adjGraph g;
    memset(g.edge, 0, sizeof(g.edge));//内存设置函数--创建图的过程中，所有元素初始化为0
    // g.edge 邻接矩阵
    //sizeof(g.edge) 数组占用的总字节数
    scanf("%d%d", &g.n, &g.m);//输入顶点数和边数
    getchar();//吸收换行符
    //1.输入n个顶点
    for (int i = 0; i < g.n; i++) {
        scanf("%c ", &g.vex[i]);
    }
    //2.输入m条边，按照邻接矩阵存图
    for (int i = 0; i < g.m; i++) {
        char v1, v2;
        scanf("\n%c %c", &v1, &v2);//读入当前边的2个顶点
        int n1 = v1 - 'A', n2 = v2 - 'A';
        //将顶点字符转换为对应的数组索引。
       // 假设顶点标签是大写字母'A'、'B'、'C'等，通过将其减去字符'A'的ASCII码值
       // 可以得到对应的数组索引（0、1、2等）。   
        g.edge[n1][n2] = 1;
        //有向图，邻接矩阵对应的n1行n2列赋值为1
        //将对应的邻接矩阵元素设置为1，表示图中对应的顶点之间存在一条边。
    }

    return g;
}

void print(adjGraph g)
{
    printf("图有%d个顶点，%d条边\n", g.n, g.m);
    printf("图的顶点是：");
    for (int i = 0; i < g.n; i++) {
        printf("%c ", g.vex[i]);
    }
    printf("\n图的邻接矩阵是：\n");
    for (int i = 0; i < g.n; i++) {
        for (int j = 0; j < g.n; j++) {
            printf("%4d", g.edge[i][j]);
        }
        printf("\n");
    }
}

void printDegree(adjGraph g)
{
    printf("图中每个顶点的入度是：\n");
    for (int i = 0; i < g.n; i++) {
        int indegree = 0;
            for (int j = 0; j < g.n; j++) {
                if (g.edge[j][i] == 1) {
                    indegree++;
                 }
            }
            printf("%c: %d \n", g.vex[i], indegree);
       }
       
  


    printf("图中每个顶点的出度是：\n");
    for (int i = 0; i < g.n; i++) {
        int outdegree = 0;
        for (int j = 0; j < g.n; j++) {
            if (g.edge[i][j] == 1) {
                outdegree++;
            }
        }
        printf("%c: %d \n", g.vex[i], outdegree);
        
    }

}

测试样例：

**有向带权图邻接矩阵建图和度数输出（含完整代码）

要注意有向图带权图中，含有权值的线路如 A 20 B ，反过来B到A就是 INF，不相连的两个顶点之间也是INF

#define _CRT_SECURE_NO_WARNINGS 1
#include <stdio.h>
#include <string.h>
#define N (100 + 5)
#define INF 0x3f3f3f3f//定义INF为一个十六进制无穷大常量

typedef char VexType; //顶点为字符类型
typedef int EdgeType;//邻接矩阵类型为整型

typedef struct {
    int n, m; //n个顶点，m条边
    VexType vex[N];//一维数组存放所有顶点的数据信息
    EdgeType edge[N][N];//邻接矩阵(二维数组存放图中所有顶点之间关系的信息)
} adjGraph;

//1.邻接矩阵建图
adjGraph createGraph();
//2.输出图的信息（顶点、邻接矩阵）
void print(adjGraph g);
//3.输出图中每个顶点的度数
void printDegree(adjGraph g);

int main()
{
    //1.建图
    adjGraph g = createGraph();
    //2.输出图的信息
    print(g);
    printDegree(g);
    return 0;
}


adjGraph createGraph()//建图
{
    adjGraph g;
    memset(g.edge, 0, sizeof(g.edge));//内存设置函数--创建图的过程中，所有元素初始化为0
    // g.edge 邻接矩阵
    //sizeof(g.edge) 数组占用的总字节数
    scanf("%d%d", &g.n, &g.m);//输入顶点数和边数
    getchar();//吸收换行符
    //1.输入n个顶点
    for (int i = 0; i < g.n; i++) {
        scanf("%c ", &g.vex[i]);
    }
    //2.输入m条边，按照邻接矩阵存图 
    // 将邻接矩阵初始化为INF
    for (int i = 0; i < g.m; i++) {
        for (int j = 0; j < g.m; j++) {
            g.edge[i][j] = INF;
        }
    }
    for (int i = 0; i < g.m; i++) {
        char v1, v2;
        int weight;
        scanf("\n%c %d %c", &v1, &weight, &v2);//读入当前边的2个顶点
        int n1 = v1 - 'A', n2 = v2 - 'A';
        //将顶点字符转换为对应的数组索引。
        // 假设顶点标签是大写字母'A'、'B'、'C'等，通过将其减去字符'A'的ASCII码值
        // 可以得到对应的数组索引（0、1、2等）。
       
        if (n1 == n2) {
            g.edge[n1][n2] = 0;
        }
        else {
            g.edge[n1][n2] = weight;
            g.edge[n2][n1] = INF; // 反方向的边权值设置为INF
        }
    }


    return g;
}

void print(adjGraph g)
{
    printf("图有%d个顶点，%d条边\n", g.n, g.m);
    printf("图的顶点是：");
    for (int i = 0; i < g.n; i++) {
        printf("%c ", g.vex[i]);
    }
    printf("\n图的邻接矩阵是：\n");
    for (int i = 0; i < g.n; i++) {
        for (int j = 0; j < g.n; j++) {
            if (i == j) printf("0 ");
            else if (g.edge[i][j] == INF)
            {
                printf("INF ");
           }
            else  {
                   printf("%-4d", g.edge[i][j]);
            }
                  
        
            
        }
        printf("\n");
    }
}

void printDegree(adjGraph g)
{
    printf("图中每个顶点的入度是：\n");
    for (int i = 0; i < g.n; i++) {
        int indegree = 0;
        for (int j = 0; j < g.n; j++) {
     
                  if (g.edge[j][i] != 0 && g.edge[j][i] != INF) {
                     indegree++;
                 }
    
            
        }
        printf("%c: %d \n", g.vex[i], indegree);
    }




    printf("图中每个顶点的出度是：\n");
    for (int i = 0; i < g.n; i++) {
        int outdegree = 0;
        for (int j = 0; j < g.n; j++) {
                if (g.edge[i][j] != 0&& g.edge[i][j] != INF) {
                    outdegree++;
                }
            }

        
        printf("%c: %d \n", g.vex[i], outdegree);

    }

}

样例：

2、邻接表存储方法

  对每一个顶点建立一个单链表，将同一个顶点发出的边链接在一个称为边链表的单链表中。

头插法：

无向图中相连即放在链表里作为边结点（包含与该点相连的所有顶点）。

有向图按照方向选择结点作为边结点。‘’

五、图的遍历

1.深度优先遍历

2.广度优先遍历

六、最小生成树

      

1.克鲁斯卡尔方法

2.普里姆算法

七、最短路径问题

Q:对于对于给定的带权连通无向图，从某源点到图中各顶点的最短路径构成的生成树是否是该图的最小生成树？？

不一定相同。

八、AOV网与拓扑排序

九、AOE网与关键路径

1、AOE网的定义

2、AOE网的特点

3、AOE网的存储方法

4、关键路径

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：/a/258581.html

如若内容造成侵权/违法违规/事实不符，请联系我们进行投诉反馈qq邮箱809451989@qq.com，一经查实，立即删除！

相关文章

Java：语法速通

Java：语法速通

参考 菜鸟教程 java 继承 class 父类 { }class 子类 extends 父类 { }继承的特性&#xff1a; 子类拥有父类非private的属性和方法子类可以对父类进行扩展子类可以重写父类的方法使用extends只能单继承&#xff0c;使用implements可以变相的多继承&#xff0c;即一个类继承…
阅读更多...
24_28-Golang函数详解

24_28-Golang函数详解

**Golang **函数详解 主讲教师&#xff1a;&#xff08;大地&#xff09; 合作网站&#xff1a;www.itying.com** **&#xff08;IT 营&#xff09; 我的专栏&#xff1a;https://www.itying.com/category-79-b0.html 1、函数定义 :::info 函数是组织好的、可重复使用的、用…
阅读更多...
雪花算法（几种常见的雪花算法生成ID方案简单介绍：Hutool、百度Uid-Generator、美团Leaf、Yitter）

雪花算法（几种常见的雪花算法生成ID方案简单介绍：Hutool、百度Uid-Generator、美团Leaf、Yitter）

文章目录 1.生成id的几种方式2. 雪花算法2.1 雪花算法介绍2.2 市面上几种雪花算法的实现2.2.1 hutool版2.2.1.1 hutool版本雪花算法 关于时钟回拨的处理&#xff1a; ---------------百度UidGenerator 介绍开始--------------2.2.2 百度版&#xff1a;[UidGenerator](https://g…
阅读更多...
vue 流光边框矩形圆形容器

vue 流光边框矩形圆形容器

实现流光边框一般是用渐变背景加动画实现&#xff0c;然后使用内部盒子遮挡内部空间&#xff0c;达到边框流光的效果 思路&#xff1a;背景渐变旋转动画 功能&#xff1a; 自定义渐变&#xff08;是否渐变<不渐变没有流光效果>&#xff0c;渐变颜色&#xff0c;渐变角…
阅读更多...
鉴赏 tcp vegas

鉴赏 tcp vegas

优秀的 vegas 之后&#xff0c;再鉴赏一下迄今唯一像那么回事的拥塞控制算法 vegas。 从下图可看出所有的(对&#xff0c;所有的) aimd 都毫无伸缩性(z:吞吐&#xff0c;x:rtt&#xff0c;y:丢包率&#xff0c;由 buffer_size 直接决定)&#xff1a; 一下就可看出 rtt 和 bu…
阅读更多...
LeetCode day27

LeetCode day27

LeetCode day27 —今天做到树&#xff0c;&#xff0c;&#xff0c;对不起我的数据结构老师啊~~~ 7. 整数反转 给你一个 32 位的有符号整数 x &#xff0c;返回将 x 中的数字部分反转后的结果。 如果反转后整数超过 32 位的有符号整数的范围 [−231, 231 − 1] &#xff0c…
阅读更多...
springboot跨域问题，解决方法

springboot跨域问题，解决方法

前端访问出现CORS跨域问题 不多说&#xff0c;直接上代码~ import org.springframework.stereotype.Component;import javax.servlet.*; import javax.servlet.http.HttpServletRequest; import javax.servlet.http.HttpServletResponse; import java.io.IOException;Component…
阅读更多...
OpenAI 偷偷在训练 GPT-4.5！？

OpenAI 偷偷在训练 GPT-4.5！？

最近看到有人已经套路出 ChatGPT 当前的版本&#xff0c;回答居然是 gpt-4.5-turbo&#xff1a; 实际试验下&#xff0c;用 starflow.tech&#xff0c;切换到小星 4 全能版&#xff08;同等官网最新 GPT-4&#xff09;&#xff0c;复制下面这段话问它&#xff1a; What is the…
阅读更多...
winfrom大恒工业相机SDK二次开发、C#联合halcon开发

winfrom大恒工业相机SDK二次开发、C#联合halcon开发

一、开发环境 1.在大恒图像官网下载SDK安装包&#xff0c;安装SDK后&#xff0c;打开安装目录找到Samples文件夹&#xff0c;然后找到Samples\CSharp SDK\x64\DoNET\.NET4.0文件夹下找到GxIAPINET.dll&#xff0c;如图&#xff1a; 2.打开VS2019软件&#xff0c;建立winfrom项…
阅读更多...
JS中的异常处理：

JS中的异常处理：

throw: 抛出异常时我们哪个关键字&#xff1f;它会终止程序&#xff1f; throw关键字 会终止程序 抛出异常经常和谁配合使用&#xff1f; Error对象配合throw使用 代码演示&#xff1a; function fn(x,y){if(!x || !y){// console.log(11);// throw 用户没有参数传递进来;th…
阅读更多...
【BEV感知】BEVFormer 融合多视角图形的空间特征和时序特征 ECCV 2022

【BEV感知】BEVFormer 融合多视角图形的空间特征和时序特征 ECCV 2022

前言 本文分享BEV感知方案中&#xff0c;具有代表性的方法&#xff1a;BEVFormer。 它基于Deformable Attention&#xff0c;实现了一种融合多视角相机空间特征和时序特征的端到端框架&#xff0c;适用于多种自动驾驶感知任务。 主要由3个关键模块组成&#xff1a; BEV Que…
阅读更多...
EasyExcel合并相同内容单元格及动态标题功能的实现

EasyExcel合并相同内容单元格及动态标题功能的实现

一、最初版本 导出的结果&#xff1a; 对应实体类代码&#xff1a; import com.alibaba.excel.annotation.ExcelProperty; import com.alibaba.excel.annotation.write.style.ColumnWidth; import com.alibaba.excel.annotation.write.style.ContentLoopMerge; import com.al…
阅读更多...
markdown文档主题颜色修改

markdown文档主题颜色修改

目录 1、选择任意想选择的markdown文档主题css文件&#xff1a; 2、修改背景颜色 1、选择任意想选择的markdown文档主题css文件&#xff1a; 使用工具Typora文件主题路径&#xff1a; C:\Users\AppData\Roaming\Typora\themes&#xff0c;此处我这边就是copy了xydark的css文…
阅读更多...
Java 自定义注解

Java 自定义注解

Java 自定义注解&#xff0c; 以及interface Target Retention Around Before After ProceedingJoinPoint JoinPoint 等用法 注解应用非常广泛&#xff0c;我们自定义注解能简化开发各种各种业务 一、关键字解释 (1) 定义注解时&#xff0c;关键字 interface 来表示注解类的类…
阅读更多...
高级算法设计与分析（二） -- 递归与分治策略

高级算法设计与分析（二） -- 递归与分治策略

系列文章目录 高级算法设计与分析&#xff08;一&#xff09; -- 算法引论 高级算法设计与分析&#xff08;二&#xff09; -- 递归与分治策略 高级算法设计与分析&#xff08;三&#xff09; -- 动态规划 未完待续【 高级算法设计与分析&#xff08;四&#xff09; -- 贪…
阅读更多...
谷歌新款 Pixel 8 更小、更智能！

谷歌新款 Pixel 8 更小、更智能！

一、谷歌 Pixel 8 更小、更智能——比去年的 Pixel 7 贵了 100 美元——不是一点点——贵 与 Pixel 7 一样&#xff0c;Pixel同样在今天 8 比正式发布的更大的 Pixel 8 Pro 兄弟产品更小、更便宜。但今年价格有所上涨&#xff0c;128GB 存储型号的 Pixel 8 起售价为 699.99 美…
阅读更多...
腾讯云消息队列11月产品月报 | RocketMQ 5.x 国际站上线

腾讯云消息队列11月产品月报 | RocketMQ 5.x 国际站上线

2023年 11月动态 消息队列 RocketMQ 版 1、5.x 形态国际站上线 国际站上线 5.x 集群全系列&#xff0c;第一批先开放新加坡和硅谷地域。 控制台链接&#xff1a;https://console.tencentcloud.com/trocketmq 2、 无感迁移能力 支持用户白屏化操作&#xff0c;将自建的 Roc…
阅读更多...
夜莺项目发布 v6.5.0 版本，暗黑菜单来了

夜莺项目发布 v6.5.0 版本，暗黑菜单来了

大家好&#xff0c;夜莺项目发布 v6.5.0 版本&#xff0c;启用新 logo&#xff0c;菜单支持换肤&#xff0c;支持了暗黑版本的菜单&#xff0c;下一步会支持全站暗黑主题&#xff0c;敬请期待&#xff0c;下面是新 logo。 暗黑菜单 页面右上角点击用户名&#xff0c;在下拉框里…
阅读更多...
盘点ASO优化过去到现在的进步

盘点ASO优化过去到现在的进步

ASO优化行业十年老兵报道&#xff01;从以下几个方面总结了ASO优化的一些变化和进步&#xff0c;给大家分享。 一、优化手段&#xff1a; 过去&#xff0c;ASO优化主要依赖于机刷&#xff0c;通过破解苹果的算法&#xff0c;对苹果账号进行一系列的定向操作行为&#xff08;搜…
阅读更多...
React Jsx转换成真实DOM过程？

React Jsx转换成真实DOM过程？

面试官&#xff1a;说说React Jsx转换成真实DOM过程&#xff1f; 一、是什么 react通过将组件编写的JSX映射到屏幕&#xff0c;以及组件中的状态发生了变化之后 React会将这些「变化」更新到屏幕上 在前面文章了解中&#xff0c;JSX通过babel最终转化成React.createElement这…
阅读更多...
最新文章

Copyright @ 2022~2023