数据结构 图的邻接矩阵

数据结构 图的邻接矩阵图的邻接矩阵的存储方式是用两个数组来实现的,一个一维数组存储顶点信息,一个二维数组存储线(无向图)或弧(有向图)的信息。设图G有n个顶点,则邻接矩阵是一个n×n的方阵,定义为:无向图的邻接矩阵,两个顶点有边则为1,否则,为0;因为是无向图arc[i][j]=arc[j][i],所以矩阵为对称矩阵,对角线为自己到自己的边,邻接矩阵中,行之和或者列之和都为各顶点度的总数。设图G有是网图,有n个…

大家好,又见面了,我是你们的朋友全栈君。

图的邻接矩阵的存储方式是用两个数组来实现的,一个一维数组存储顶点信息,一个二维数组存储线(无向图)或弧(有向图)的信息。

设图G有n个顶点,则邻接矩阵是一个n × n的方阵,定义为:

数据结构 图的邻接矩阵

数据结构 图的邻接矩阵

无向图的邻接矩阵,两个顶点有边则为1,否则,为0;因为是无向图arc[i][j] = arc[j][i],所以矩阵为对称矩阵,对角线为自己到自己的边,邻接矩阵中,行之和或者列之和都为各顶点度的总数。

设图G有是网图,有n个顶点,则邻接矩阵是一个n × n的方阵,定义为:

数据结构 图的邻接矩阵

数据结构 图的邻接矩阵

无向网图和无向图差不多,就是加了权值,两个顶点之间无边的话距离是∞。

如果是有向图,邻接矩阵就不是对称矩阵了。

下面是邻接矩阵的存储结构:

#define MAXVERTEX 100   //图的最大顶点数
#define INFINITY 32767  //用有符号的int最大值表示无穷大
typedef char vertextype;    //定义定点的存储信息为字符型
typedef int arctype;    //定义边的权值为int型

//图的邻接矩阵的存储结构
typedef struct
{
    vertextype vertex[MAXVERTEX];   //顶点表
    arctype arc[MAXVERTEX][MAXVERTEX];  //邻接矩阵
    int vertexnum;  //图的当前顶点数
    int arcnum; //图的当前边数
}MGraph;

存储结构里面主要由四部分构成,

第一部分是一个一维数组存储的是顶点信息,

第二部分是邻接矩阵由二维数组组成,存储着各顶点彼此之间的关系,

第三部分和第四部分分别是当前图的顶点数和线数。

下面是具体的代码实现(注释的很详细了):

#include <iostream>
using namespace std;

#define MAXVERTEX 100   //图的最大顶点数
#define INFINITY 32767  //用有符号的int最大值表示无穷大
typedef char vertextype;    //定义定点的存储信息为字符型
typedef int arctype;    //定义边的权值为int型

//图的邻接矩阵的存储结构
typedef struct
{
    vertextype vertex[MAXVERTEX];   //顶点表
    arctype arc[MAXVERTEX][MAXVERTEX];  //邻接矩阵
    int vertexnum;  //图的当前顶点数
    int arcnum; //图的当前边数
}MGraph;

//创建无向网
void CreateMGraph(MGraph &G)
{
    cin >> G.vertexnum; //输入顶点数目
    cin >> G.arcnum;    //输入边数
    for(int i = 0; i < G.vertexnum; i++)    //输入顶点信息
        cin >> G.vertex[i];
    for(int i = 0; i < G.vertexnum; i++)    //将所有边初始化为无穷大
        for(int j = 0; j < G.vertexnum; j++)
            G.arc[i][j] = INFINITY;
    for(int k = 0; k < G.arcnum; k++)
    {
        int i, j, w;
        cin >> i >> j;  //输入构成边的两个顶点
        cin >> w;   //输入边所对应的权值
        G.arc[i][j] = w;
        G.arc[j][i] = G.arc[i][j];  //无向图的邻接矩阵为对称矩阵
    }
}

//打印邻接矩阵
void PrintfMGraph(MGraph G)
{
    for(int i = 0; i < G.vertexnum; i++)
    {
        for(int j = 0; j < G.vertexnum; j++)
            cout << G.arc[i][j] << '\t';
        cout << endl;
    }
}

//主函数
int main()
{
    MGraph G;
    CreateMGraph(G);
    PrintfMGraph(G);
    return 0;
} 

邻接矩阵的时间复杂度为O(n +  n^2 + e),其中n为顶点数,e为边数,去掉低阶和系数后,变为O(n^2)。

运行结果(根据上面第二个图输入的数据):

数据结构 图的邻接矩阵

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/153994.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)


相关推荐

  • plsqldev8.0下载和注册码

    plsqldev8.0下载和注册码[b]关键词:PL/SQL,下载,plsqldev,注册码,plsqldev711,汉化文件[/b]PL/SQLDeveloper是一种集成的开发环境,专门用于开发、测试、调试和优化OraclePL/SQL存储程序单元,比如触发器等。PL/SQLDeveloper功能十分全面,大大缩短了程序员的开发周期。[url]http://www.kutoku.info/software…

  • pki的应用包括哪些技术_新技术应用情况

    pki的应用包括哪些技术_新技术应用情况一、概述公钥基础设施(PublicKeyInfrastructure,简称PKI)是目前网络安全建设的基础与核心,是电子商务安全实施的基本保障,因此,对PKI技术的研究和开发成为目前信息安全领域的热点。本文对PKI技术进行了全面的分析和总结,其中包括PKI组成、PKI应用等,并对CA的开发做了简要分析。本文对PKI,特别是CA的开发、应用和普及具有一定的促进作用。二、PKI技术的信任服务…

    2022年10月26日
  • StoredProcedure “存储过程名” 的TextHeader 中存在语法错误

    StoredProcedure “存储过程名” 的TextHeader 中存在语法错误修改存储过程的时候出现StoredProcedure“存储过程名”的TextHeader中存在语法错误出现这样的问题的解决方法(本人修改已成功)在创建存储过程的时候加了注释,把注释删掉就没有问题了(或者把注释放到其他地方)错误代码如下:CREATEPROCEDURE[dbo].[tableToTxtExport]@dbTabNamenvarchar(4000),@dbBoo…

  • 约束条件(constraint)「建议收藏」

    约束条件(constraint)「建议收藏」1.为啥使用约束条件:约束条件也叫完整性约束条件,当对表中的数据做DML操作时会验证数据是否违反约束条件.如果违反了DML操作会失败.约束条件可以应用于表中的一列或几列,应用于整个表或几个表之间.约束条件分类:非空(NOTNULL),唯一(UNIQUE),主键(PRIMARYKEY),外键(FOREIGNKEY),检查(CHECK).其中NOTNULL只能应用于列.

    2022年10月13日
  • Fielddata is disabled on text fields by default. Set fielddata=true on [Tag] in order to load field

    Fielddata is disabled on text fields by default. Set fielddata=true on [Tag] in order to load field

  • c语言scanf函数用法详解_c语言输入scanf格式

    c语言scanf函数用法详解_c语言输入scanf格式本节介绍输入函数scanf的用法。scanf和printf一样,非常重要,而且用得非常多,所以一定要掌握。概述scanf的功能用一句话来概括就是“通过键盘给程序中的变量赋值”。该函数的原型为:#include<stdio.h>intscanf(constchar*format,…);它有两种用法,或者说有两种格式。1)scanf(“输…

    2022年10月25日

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号