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

图的邻接矩阵(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 条评论
登录 后参与评论

相关文章

来自专栏生信技能树

使用ESTIMATE来对转录组表达数据根据stromal和immune细胞比例估算肿瘤纯度

ESTIMATE (Estimation of STromal and Immune cells in MAlignant Tumor tissues usin...

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

边双联通分量与割边

前言 在图论中,除了在有向图中的强连通分量,在无向图中还有一类双联通分量 双联通分量一般是指点双连通分量 当然,还有一种叫做边双连通分量 边双联通分量 对于一个...

3646
来自专栏IT派

开源|人脸检测的C / C ++源代

人脸检测的C/C++源代码,曾发表于 OPENCV 的 MAILING LIST,主要是对OPENCV 3.1 版本发布的代码做了一些速度上的优化,并且解决了内...

3455
来自专栏尾尾部落

[剑指offer] 变态跳台阶

一只青蛙一次可以跳上1级台阶,也可以跳上2级……它也可以跳上n级。求该青蛙跳上一个n级的台阶总共有多少种跳法。

692
来自专栏一棹烟波

OpenGL进行简单的通用计算实例

博主作为OpenGL新手,最近要用OpenGL进行并行的数据计算,突然发现这样的资料还是很少的,大部分资料和参考书都是讲用OpenGL进行渲染的。好不容易找到一...

2187
来自专栏xingoo, 一个梦想做发明家的程序员

剑指OFFER之变态跳台阶(九度OJ1389)

题目描述: 一只青蛙一次可以跳上1级台阶,也可以跳上2级……它也可以跳上n级。求该青蛙跳上一个n级的台阶总共有多少种跳法。 输入: 输入可能包含多个测试样例,对...

1768
来自专栏calmound

ZOJ 3631 Watashi's BG(01dp)

01dp不过由于数组过于大,开不开,学了搜索过了,先记录下 还有一种方法 #include<stdio.h> #include<algorithm> using...

3617
来自专栏TechBox

两个宏快速计算九宫格X、Y坐标

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

tarjan系列算法代码小结

个人使用,可能不是很详细 强联通分量 这里的dfn可以写成low 因为都是在栈中,只要保证该节点的low值不为本身即可 void tarjan(int now)...

3497
来自专栏Python小屋

Python两种方法求解登楼梯问题(京东2016笔试题)

问题:假设一段楼梯共15个台阶,小明一步最多能上3个台阶,那么小明上这段楼梯一共有多少种方法? 解析:从第15个台阶上往回看,有3种方法可以上来(从第14个台阶...

3709

扫码关注云+社区