图的邻接矩阵表示及其基本操作

文章目录

• 图的邻接矩阵表示及其基本操作
• • 1.邻接矩阵
  • 2.图的邻接矩阵存储结构类型声明
  • 3.基于邻接矩阵表示的无向图的创建
  • 4.基于邻接矩阵的无向图的其它操作

1.邻接矩阵

表示图的一种简单方式是使用二维数组，称为邻接矩阵表示法。图中的每条边(v, w)，设置A[v][w]=1；若不存在边(v, w)，则A[v][w] = 0；如果边上带权值，那么可以设置A[v][w]等于该权值，同时使用一个很大或者很小的权值来表示不存在的边。如图，展示了无向图、有向图、有向网和它们的邻接矩阵。

邻接矩阵是一种顺序结构，从邻接矩阵的行数或者列数可知图的顶点数。无向图的邻接矩阵总是对称的，但有向图的邻接矩阵不一定对称。

2.图的邻接矩阵存储结构类型声明

#define MAX_V 20 //最大顶点数 #define OK 1 #define ERROR 0 typedef int ElemType, Status; typedef int GraphKind; //图的种类标志，无向图0，有向图1，无向网2，有向网3class MGraph { private:int arcs[MAX_V][MAX_V]; //邻接矩阵，存放的是边的信息int vexnum, arcnum; //图包含的顶点数与边的个数ElemType vexs[MAX_V]; //存储顶点的值GraphKind type; //图的种类标志，分为无向图0，有向图1，无向网2，有向网3 public:Status CreateGraph(); //基于邻接矩阵的无向图的创建Status DestroyGraph(); //基于邻接矩阵的无向图的销毁ElemType GetVex(int v); //返回编号为v的顶点信息Status InsertVex(); //插入顶点Status InsertArc(int v, int w); //插入边Status DeleteVex(int v); //删除顶点Status DeleteArc(int v, int w); //删除边Status Print(); //打印邻接矩阵 };

3.基于邻接矩阵表示的无向图的创建

//基于邻接矩阵的无向图的创建 Status MGraph::CreateGraph() {int v, e, i, j;int v1, v2;cin >> v >> e;vexnum = v;arcnum = e;for (i = 0; i < vexnum; i++)cin >> vexs[i];for (i = 0; i < vexnum; i++) //邻接矩阵初始化for (j = 0; j < vexnum; j++)arcs[i][j] = 0;//输入邻接矩阵for (i = 0; i < arcnum; i++) {cin >> v1 >> v2;arcs[v1][v2] = 1;arcs[v2][v1] = 1;}return OK; }

4.基于邻接矩阵的无向图的其它操作

//基于邻接矩阵的无向图的销毁 Status MGraph::DestroyGraph() {for (int i = 0; i < vexnum; i++)for (int j = 0; j < vexnum; j++)arcs[i][j] = 0;vexnum = 0;arcnum = 0;return OK; }//返回编号为v的顶点的值 ElemType MGraph::GetVex(int v) {if (v >= 0 && v < vexnum)return vexs[v];elsereturn ERROR; }//插入一个顶点 Status MGraph::InsertVex() {cin >> vexs[vexnum];vexnum++;int i, j;for (int n = 0; n < vexnum; n++) {arcs[vexnum-1][n] = 0;arcs[n][vexnum-1] = 0;}while (true) {cin >> i >> j;if (i == -1)break;arcs[i][j] = 1;arcs[j][i] = 1;}return OK; }//插入一条边 Status MGraph::InsertArc(int v, int w) {arcs[v][w] = 1;arcs[w][v] = 1;return OK; }//删除一个顶点 Status MGraph::DeleteVex(int v) {int i, j; for (i = v; i < vexnum - 1; i++) {for (j = 0; j < vexnum; j++) {arcs[i][j] = arcs[i + 1][j];arcs[j][i] = arcs[i][j];}}for (i = v; i < vexnum - 1; i++)vexs[i] = vexs[i + 1];vexnum--;return OK; }//删除一条边 Status MGraph::DeleteArc(int v, int w) {arcs[v][w] = 0;arcs[w][v] = 0;return OK; }//打印邻接矩阵 Status MGraph::Print() {int i, j;for (i = 0; i < vexnum; i++) {for (j = 0; j < vexnum; j++) {cout << arcs[i][j] << " ";}cout << endl;}cout << endl;return OK; }

总结

以上是生活随笔为你收集整理的图的邻接矩阵表示及其基本操作的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。