数据结构:图的存储结构之邻接矩阵「建议收藏」图的邻接矩阵(AdjacencyMatrix)存储方式是用两个数组来表示图。一个一维的数组存储图中顶点信息,一个二维数组(称为邻接矩阵)存储图中的边或弧的信息。设图G有n个顶点,则邻接矩阵是一个n*n的方阵,定义为:我们来看一个实例,图7-4-2的左图就是一个无向图。我们再来看一个有向图样例,如图7-4-3所示的左图。在图的术语中,我们提到了网的概念,也就
大家好,又见面了,我是你们的朋友全栈君。如果您正在找激活码,请点击查看最新教程,关注关注公众号 “全栈程序员社区” 获取激活教程,可能之前旧版本教程已经失效.最新Idea2022.1教程亲测有效,一键激活。
Jetbrains全家桶1年46,售后保障稳定
图的邻接矩阵(Adjacency Matrix)存储方式是用两个数组来表示图。一个一维的数组存储图中顶点信息,一个二维数组(称为邻接矩阵)存储图中的边或弧的信息。
设图G有n个顶点,则邻接矩阵是一个n*n的方阵,定义为:
我们来看一个实例,图7-4-2的左图就是一个无向图。
我们再来看一个有向图样例,如图7-4-3所示的左图。
在图的术语中,我们提到了网的概念,也就是每条边上都带有权的图叫做网。那些这些权值就需要保存下来。
设图G是网图,有n个顶点,则邻接矩阵是一个n*n的方阵,定义为:
如图7-4-4左图就是一个有向网图。
下面示例无向网图的创建代码:(改编自《大话数据结构》)
C++ Code
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51
|
|
#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; } |
版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。
发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/210017.html原文链接:https://javaforall.cn
【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛
【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...