数据结构:图的存储结构之邻接矩阵

图的邻接矩阵(Adjacency Matrix)存储方式是用两个数组来表示图。一个一维的数组存储图中顶点信息,一个二维数组(称为邻接矩阵)存储图中的边或弧的信息。

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

我们来看一个实例,图7-4-2的左图就是一个无向图。

我们再来看一个有向图样例,如图7-4-3所示的左图。

图的术语中,我们提到了网的概念,也就是每条边上都带有权的图叫做网。那些这些权值就需要保存下来。

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

如图7-4-4左图就是一个有向网图。

下面示例无向网图的创建代码:(改编自《大话数据结构》)

#include<iostream>
using namespace std;

#define MAXVEX 100/* 最大顶点数,应由用户定义 */
#define INFINITY  65535 /* 表示权值的无穷*/

typedef int EdgeType;/* 边上的权值类型应由用户定义 */
typedef char VertexType;/* 顶点类型应由用户定义  */

typedef struct
{
    VertexType vexs[MAXVEX];/* 顶点表 */
    EdgeType arc[MAXVEX][MAXVEX];/* 邻接矩阵,可看作边表 */
    int numNodes, numEdges;/* 图中当前的顶点数和边数  */
} MGraph;
/* 建立无向网图的邻接矩阵表示 */
void CreateMGraph(MGraph *Gp)
{
    int i, j, k, w;
    cout << "请输入顶点数和边数(空格分隔):" << endl;
    cin >> Gp->numNodes >> Gp->numEdges;
    cout << "请输入顶点信息(空格分隔):" << endl;
    for (i = 0; i < Gp->numNodes; i++)
        cin >> Gp->vexs[i];
    for (i = 0; i < Gp->numNodes; i++)
    {
        for (j = 0; j < Gp->numNodes; j++)
        {
            if (i == j)
                Gp->arc[i][j] = 0;/* 顶点没有到自己的边*/
            else
                Gp->arc[i][j] = INFINITY;/* 邻接矩阵初始化 */
        }
    }

    for (k = 0; k < Gp->numEdges; k++)
    {
        cout << "请输入边(vi, vj)的上标i,下标j和权值w(空格分隔):" << endl;
        cin >> i >> j >> w;
        Gp->arc[i][j] = w;
        Gp->arc[j][i] = Gp->arc[i][j];/* 因为是无向图,矩阵对称 */
    }
}

int main(void)
{
    MGraph MG;
    CreateMGraph(&MG);

    return 0;
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏知识分享

关于stm32的正交解码

关于正交解码,我先解释何为正交解码,,,,其实名字挺高大上的,,,,还是先说编码器吧 看一下我用过的一种编码器 ? ? ? 编码器的 线 数 ,是说编码器转一圈...

3286
来自专栏云霄雨霁

加权有向图----加权有向图的实现

1230
来自专栏生信技能树

乳腺癌预后基因集

In addition to cell of origin and somatic mutation events, studies over the past...

933
来自专栏数据结构与算法

各种数论模板 不断更新 绝对精品

1.筛法求素数 1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #inclu...

3229
来自专栏ACM小冰成长之路

51Nod-1232-完美数

ACM模版 描述 ? 题解 这里要求数的值整除以所有位的值,除 0 以外,所以也就很容易想到,这个数一定是要整除这些位数的最小公倍数,而这些数范围是 1∼9 ,...

1788
来自专栏数据结构与算法

BZOJ1059: [ZJOI2007]矩阵游戏(二分图匹配)

  小Q是一个非常聪明的孩子,除了国际象棋,他还很喜欢玩一个电脑益智游戏——矩阵游戏。矩阵游戏在一个N

772
来自专栏量化投资与机器学习

【代码+论文】通过ML、Time Series模型学习股价行为

今天编辑部给大家带来的是来自Jeremy Jordan的论文,主要分析论文的建模步骤和方法,具体内容大家可以自行查看。 # Standard imports i...

3508
来自专栏大数据挖掘DT机器学习

使用R语言构造投资组合

原作者: 邓一硕 来自: 格物堂 构造投资组合是金融投资分析中历久弥新的问题。多年以来,学界、业界提出诸多对投资组合进行优化的方法。比如,最经典的基于收益率均...

3896
来自专栏owent

ECUST 09年 校赛个人赛第六,七场总结

732
来自专栏hightopo

纯Shading Language绘制飞机火焰效果

1736

扫码关注云+社区