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

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

相关文章

来自专栏赵俊的Java专栏

落单的数Ⅱ

1172
来自专栏cmazxiaoma的架构师之路

一个Java小白通向数据结构算法之旅(6) - 插入排序

1565
来自专栏ACM算法日常

10000的阶乘-HDU1042

Given an integer N(0 ≤ N ≤ 10000), your task is to calculate N!

801
来自专栏Java开发者杂谈

重读算法导论之算法基础

重读算法导论之算法基础 ---- 插入排序 ​ 对于少量数据的一种有效算法。原理: 整个过程中将数组中的元素分为两部分,已排序部分A和未排序部分B 插入过程中,...

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

Codeforces 550 D. Regular Bridge

\(>Codeforces \space 550 D. Regular Bridge<\)

361
来自专栏SeanCheney的专栏

《大话数据结构》总结第一章 绪论第二章 算法第三章 线性表第四章 栈和队列第五章 字符串第六章 树第七章 图第八章 查找第九章 排序

第一章 绪论 什么是数据结构? 数据结构的定义:数据结构是相互之间存在一种或多种特定关系的数据元素的集合。 第二章 算法 算法的特性:有穷性、确定性、可行性、输...

2815
来自专栏JackeyGao的博客

Leetcode 算法 -4. Median of Two Sorted Arrays

解题思路: 先把列表碾平 , 由于两个列表元素类型相同直接相加即可. 然后排序. 计算中间位置, 可以通过判断奇偶数来分别处理开始index和结束index....

593
来自专栏weixuqin 的专栏

数据结构学习笔记(图)

28310
来自专栏Bingo的深度学习杂货店

Q125 Valid Palindrome

Given a string, determine if it is a palindrome, considering only alphanumeric c...

3115
来自专栏文武兼修ing——机器学习与IC设计

表的应用——排序与描述多项式排序多项式ADTGO语言笔记

排序 朴素排序 在链表建立的过程中可以直接完成排序功能,即建立一个新链表并将源数据一个一个存进新链表中,每个元素存储的位置在小于这个元素的节点和大于这个元素的节...

3306

扫码关注云+社区