圖的鄰接矩陣表示及其基本操作

文章目錄

• 圖的鄰接矩陣表示及其基本操作
• • 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; }

總結

以上是生活随笔為你收集整理的图的邻接矩阵表示及其基本操作的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。