数据结构之图（1）【邻接矩阵、邻接表】 |
您所在的位置：网站首页 › 数据结构用邻接矩阵创建无向图 › 数据结构之图（1）【邻接矩阵、邻接表】 |
数据结构之图（1）【邻接矩阵、邻接表】
|
邻接矩阵创建无向网： 图的邻接矩阵（Adjacency Matrix)存储方式是用两个数组来表示图。一个一维的数组存储图中顶点信息，一个二维数组（称为邻接矩阵）存储图中的边或弧的信息。 设图G有n个顶点，则邻接矩阵是一个n*n的方阵，定义为：
我们来看一个实例，图7-4-2的左图就是一个无向图。
我们再来看一个有向图样例，如图7-4-3所示的左图。
在图的术语中，我们提到了网的概念，也就是每条边上都带有权的图叫做网。那些这些权值就需要保存下来。 设图G是网图，有n个顶点，则邻接矩阵是一个n*n的方阵，定义为：
如图7-4-4左图就是一个有向网图。
下面示例无向网图的创建代码： 1 #include "stdafx.h" 2 #include 3 #define MaxInt 10000 //表示权值的无穷 4 #define MVNum 100 //最大顶点数，应由用户定义 5 typedef char VerTexType; //假设顶点数据类型为字符型 6 typedef int ArcType; //假设边的权值类型为整形 7 using namespace std; 8 typedef struct 9 { 10 VerTexType vexs[MVNum]; //顶点表 11 ArcType arcs[MVNum][MVNum]; //邻接矩阵 12 int vexnum, arcnum; //图的当前点数和边数 13 }AMGraph; 14 15 void CreateUDN(AMGraph &G) //采用邻接矩阵表示法，创建无向网&G 16 { 17 int i, j, w; 18 cout > G.arcnum; //输入总顶点数、总边数 20 cout > j >> w; //输入一条边依附的顶点及权值 33 G.arcs[i - 1][j - 1] = w; 34 G.arcs[j - 1][i - 1] = G.arcs[i - 1][j - 1]; 35 } 36 } 37 38 void coutAMGraph(AMGraph &G) //无向网的输出 39 { 40 int i, j; 41 cout = G.vexnum) 34 return ERROR; 35 else 36 return 0; 37 } 38 void CreateUDG(ALGraph &G) //创建无向图 39 { 40 ArcNode *p1, *p2; 41 int i, j, k; 42 char v1, v2; 43 cout > G.arcnum; //输入总顶点数，总边数 45 cout > v1 >> v2; //输入各边，构造邻接表 55 i = LocateVex(G, v1); 56 j = LocateVex(G, v2); 57 p1 = new ArcNode; //生成一个新结点*p1 58 p1->adjvex = j; //邻接点序号为j 59 p1->nextarc = G.vertices[i].firstarc; 60 G.vertices[i].firstarc = p1; 61 p2 = new ArcNode; 62 p2->adjvex = i; 63 p2->nextarc = G.vertices[j].firstarc; 64 G.vertices[j].firstarc = p2; 65 } 66 cout |
【本文地址】
今日新闻 |
推荐新闻 |