数据结构--图

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

推广---  图

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

一、图的基本概念

二、图的分类

三、图的相关术语

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);
        
    }

}

测试样例：

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

#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、邻接表存储方法

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

头插法：

五、图的遍历

六、最小生成树

      

七、最短路径问题

八、AOV网与拓扑排序

九、AOE网与关键路径

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

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

相关文章

Shell编程基础 – C语言风格的Bash for循环

Shell编程基础 – C语言风格的Bash for循环

Shell编程基础 – C语言风格的Bash for循环 Shell Programming Essentials - C Style For Loop in Bash By JacksonML 循环是编程语言的基本概念之一&#xff0c;同样也是Bash编程的核心。当用户需要一遍又一遍地运行一系列命令直到达到特定条件时&#xff0c;例如&#xff1…
阅读更多...
输电线路定位：精确导航，确保电力传输安全

输电线路定位：精确导航，确保电力传输安全

在现代社会中&#xff0c;电力作为生活的基石&#xff0c;其安全稳定运行至关重要。而输电线路作为电力传输的重要通道&#xff0c;其故障定位和修复显得尤为重要。恒峰智慧科技将为您介绍一种采用分布式行波测量技术的输电线路定位方法&#xff0c;以提高故障定位精度&#xf…
阅读更多...
06-部署knative-eventing

06-部署knative-eventing

环境要求 For prototyping purposes 单节点的Kubernetes集群&#xff0c;有2个可用的CPU核心&#xff0c;以及4g内存&#xff1b; For production purposes 单节点的Kubernetes集群&#xff0c;需要至少有6个CPU核心、6G内存和30G磁盘空间多节点的Kubernetes集群中&#xff0c;…
阅读更多...
电影小镇智慧旅游项目技术方案：PPT全文111页，附下载

电影小镇智慧旅游项目技术方案：PPT全文111页，附下载

关键词&#xff1a;智慧旅游项目平台&#xff0c;智慧文旅建设&#xff0c;智慧城市建设&#xff0c;智慧文旅解决方案&#xff0c;智慧旅游技术应用&#xff0c;智慧旅游典型方案&#xff0c;智慧旅游景区方案&#xff0c;智慧旅游发展规划 一、智慧旅游的起源 智慧地球是IB…
阅读更多...
windows 安装jenkins

windows 安装jenkins

下载jenkins 官方下载地址&#xff1a;Jenkins 的安装和设置 清华源下载地址&#xff1a;https://mirrors.tuna.tsinghua.edu.cn/jenkins/windows-stable/ 最新支持java8的版本时2.346.1版本&#xff0c;在清华源中找不到&#xff0c;在官网中没找到windows的下载历史&#xff…
阅读更多...
MySQL数据库 约束

MySQL数据库 约束

目录 约束概述 外键约束 添加外键 删除外键 删除/更新行为 约束概述 概念&#xff1a;约束是作用于表中字段上的规则&#xff0c;用于限制存储在表中的数据。 目的&#xff1a;保证数据库中数据的正确、有效性和完整性。 分类: 注意&#xff1a;约束是作用于表中字段上…
阅读更多...
java继承

java继承

1.为什么需要继承 我们编写了两个类,一个是Puppil类(小学生),一个是Graduate(大学生),问题:两个类的属性和方法有很多是相同的,怎么办&#xff1f; 把共有的属性和方法抽离出来: 父类&#xff1a; package com.hspedu.extends01;//父类,是Pupil和Graduate的父类 public cla…
阅读更多...
50ms时延工业相机

50ms时延工业相机

华睿工业相机A3504CG000 参数配置&#xff1a; 相机端到端理论时延&#xff1a;80ms 厂家同步信息&#xff0c;此款设备帧率上线23fps&#xff0c;单帧时延&#xff1a;43.48ms&#xff0c;按照一图缓存加上传输显示的话&#xff0c;厂家预估时延在&#xff1a;80ms 厂家还有…
阅读更多...
AXure的情景交互

AXure的情景交互

目录 导语&#xff1a; 1.erp多样性登录界面 2.主页跳转 3.省级联动​编辑 4. 下拉加载 导语&#xff1a; Axure是一种流行的原型设计工具&#xff0c;可以用来创建网站和应用程序的交互原型。通过Axure&#xff0c;设计师可以创建情景交互&#xff0c;以展示用户与系统的交…
阅读更多...
机器学习之线性回归（Linear Regression）

机器学习之线性回归（Linear Regression）

概念 线性回归（Linear Regression）是机器学习中的一种基本的监督学习算法，用于建立输入变量（特征）与输出变量（目标）之间的线性关系。它假设输入变量与输出变量之间存在线性关系，并试图找到最佳拟合线来描述这种关系。 在简单线性回归中，只涉及两个变量：一个是自变量…
阅读更多...
Spark编程实验二：RDD编程初级实践

Spark编程实验二：RDD编程初级实践

目录 一、目的与要求 二、实验内容 三、实验步骤 1、pyspark交互式编程 2、编写独立应用程序实现数据去重 3、编写独立应用程序实现求平均值问题 4、三个综合实例 四、结果分析与实验体会 一、目的与要求 1、熟悉Spark的RDD基本操作及键值对操作&#xff1b; 2、熟悉使…
阅读更多...
传统软件集成AI大模型——Function Calling

传统软件集成AI大模型——Function Calling

传统软件和AI大模型的胶水——Function Calling 浅谈GPT对传统软件的影响Function Calling做了什么&#xff0c;为什么选择Function CallingFunction Calling简单例子&#xff0c;如何使用使用场景 浅谈GPT对传统软件的影响 目前为止好多人对chatGPT的使用才停留在OpenAI自己提…
阅读更多...
详细教程 - 从零开发 Vue 鸿蒙harmonyOS应用 第六节（js版） ——模块化设计实现复杂页面

详细教程 - 从零开发 Vue 鸿蒙harmonyOS应用 第六节（js版） ——模块化设计实现复杂页面

随着HarmonyOS生态的日渐完善,越来越多的厂商加入鸿蒙系统应用开发的行列。然而从其他系统转到鸿蒙开发,很多开发者还是需要一个适应的过程,特别是面对比较复杂的页面,应该如何合理进行模块化拆分是一个难点。 本文将通过一个实例,来分析如果采用模块化的方式实现一个包含丰富内…
阅读更多...
“去 Android化”为何蔚然成风？

“去 Android化”为何蔚然成风？

早在2008年时&#xff0c;国内市场诞生了第一批自研手机OS&#xff0c;由于种种缘由铩羽而归&#xff0c;“优化Android ”貌似成为了本土特色。而从2023年下半年开始掀起了一股"去安卓化"的热潮&#xff0c;像华为、小米、vivo等都不约而同的站在了同一战线。 “去…
阅读更多...
【WinDbg】学习以及在CTF中解题

【WinDbg】学习以及在CTF中解题

1、Windbg介绍 Windbg是一款Window强大的调试器&#xff0c;可以调试0和3环的程序。 在实际开发中&#xff0c;可以调试我们的错误程序&#xff0c;从而定位关键代码&#xff0c;进行程序代码修复。 WinDbg 是一种调试器工具&#xff0c;由微软公司开发&#xff0c;用于分析…
阅读更多...
随笔记录-springboot_LoggingApplicationListener+LogbackLoggingSystem

随笔记录-springboot_LoggingApplicationListener+LogbackLoggingSystem

环境&#xff1a;springboot-2.3.1 加载日志监听器初始化日志框架 SpringApplication#prepareEnvironment SpringApplicationRunListeners#environmentPrepared EventPublishingRunListener#environmentPrepared SimpleApplicationEventMulticaster#multicastEvent(Applicati…
阅读更多...
自然语言处理阅读第一弹

自然语言处理阅读第一弹

Transformer架构 encoder和decoder区别 Embeddings from Language Model (ELMO) 一种基于上下文的预训练模型,用于生成具有语境的词向量。原理讲解ELMO中的几个问题 Bidirectional Encoder Representations from Transformers (BERT) BERT就是原生transformer中的Encoder两…
阅读更多...
YOLOv5改进 | 2023卷积篇 | DWRSeg扩张式残差助力小目标检测

YOLOv5改进 | 2023卷积篇 | DWRSeg扩张式残差助力小目标检测

一、本文介绍 本文内容给大家带来的DWRSeg中的DWR模块来改进YOLOv5中的C3和Bottleneck模块&#xff0c;主要针对的是小目标检测&#xff0c;主要创新点可以总结如下&#xff1a;多尺度特征提取机制的深入研究和创新的DWR模块和SIR模块的提出&#xff0c;这种方法使得网络能够更…
阅读更多...
P2P网络下分布式文件共享场景的测试

P2P网络下分布式文件共享场景的测试

P2P网络介绍 P2P是Peer-to-Peer的缩写&#xff0c;“Peer”在英语里有“对等者、伙伴、对端”的意义。因此&#xff0c;从字面意思来看&#xff0c;P2P可以理解为对等网络。国内一些媒体将P2P翻译成“点对点”或者“端对端”&#xff0c;学术界则统一称为对等网络(Peer-to-Pee…
阅读更多...
AR室内导航如何实现？技术与原理分析

AR室内导航如何实现？技术与原理分析

随着科技的进步&#xff0c;我们生活中许多方面正在被重新定义。其中之一就是导航&#xff0c;尤其是室内导航。增强现实&#xff08;AR&#xff09;技术的出现为室内导航带来了革命性的变革。本文将深入探讨AR室内导航的技术与原理&#xff0c;以及它如何改变我们的生活方式。…
阅读更多...
最新文章

Copyright @ 2022~2023