鄰接矩陣資料結構程式c語言,C語言資料結構之圖的鄰接矩陣的應用執行個體

圖的存儲結構有 3 種形式：鄰接矩陣、鄰接表和鄰接多重表

對于一個有 n 個頂點的圖，其頂點資訊可以用一個一維數組表示，而頂點間是否有相鄰的關系，可以用鄰接矩陣(Adjacency Matrix)來表示。若 G 是一個有 n 個頂點的圖，則 G 的鄰接矩陣 A 是具有如下性質的 n 階方陣：

帶權的圖成為網，下面給出一個程式來建構一個網的鄰接矩陣：

#include

using namespace std;

#define INFINITY INT_MAX

#define MAX_VERTEX_NUM 20

typedef struct{

int vex[MAX_VERTEX_NUM];

int arcs[MAX_VERTEX_NUM][MAX_VERTEX_NUM];

int vexnum,arcnum;

}mgraph;

void creatmg(mgraph *g)

{

int m,n,w;

cin>>g->vexnum>>g->arcnum; // 輸入頂點的個數和邊數

for(int i=0;ivexnum;i++)

for(int j=0;jvexnum;j++)

g->arcs[i][j] = INFINITY; // 初始化鄰接矩陣各元素為無窮大

for(int i=0;ivexnum;i++)

cin>>g->vex[i]; // 輸入頂點

for(int j=0;jarcnum;j++)

{

cin>>m>>n>>w; // 輸入 arcnum 條邊所對應的頂點 m, n，以及這兩個頂點之間的權重 w

g->arcs[m][n] = g->arcs[n][m] = w; // 無向圖的鄰接矩陣的對稱的

}

int main()

{

mgraph g;

creatmg(&g);

cout<

system("pause");

return 0;

}