目錄
一、鄰接矩陣表示法
二、AMGraph.h
三、AMGraph.c
四、Test.c
【數據結構第 6 章 ① 】- 圖的定義和基本術語-CSDN博客
由于圖的結構比較復雜，任意兩個頂點之間都可能存在聯系，因此無法以數據元素在存儲區中的物理位置來表示元素之間的關系，即圖沒有順序存儲結構，但可以借助二維數組來表示元素之間的關系，即鄰接矩陣表示法。另一方面，由于圖的任意兩個頂點間都可能存在關系，因此，用鏈式存儲表示圖是很自然的事，圖的鏈式存儲有多種，有鄰接表、十字鏈表和鄰接多重表，應根據實際需要的不同，選擇不同的存儲結構。
一、鄰接矩陣表示法
鄰接矩陣（Adjacency Matrix）是表示頂點之間相鄰關系的矩陣。設 G(V, E) 是具有 n 個頂點的圖，則 G 的鄰接矩陣是具有如下性質的 n 階方陣：
例如，圖一中的 G1 和 G2 的鄰接矩陣如下所示：
若 G 是網，則鄰接矩陣可以定義為：
其中??表示邊上的權值；?
?表示計算機允許的，大于所有邊上權值的數。例如，下圖所示為一個有向網和它的鄰接矩陣。
二、AMGraph.h
用鄰接矩陣表示法表示圖，除了一個用于存儲鄰接矩陣的二維數組外，還需要用一個一維數組來存儲頂點信息。
注意：下面是以無向圖為例的。
#pragma once#define DEFAULT_CAPACITY 10typedef char VertexType; // 假定頂點的數據類型為 char
typedef int EdgeType; // 假定邊的權值的數據類型為 inttypedef struct AMGraph
{VertexType* vertices; // 頂點表（vertices 是 vertex 的復數）EdgeType** edges; // 鄰接矩陣int vSize; // 當前圖中的頂點數int eSize; // 當前圖中的邊數int capacity; // 容量
}AMGraph;// 基本操作
void AMGraphInit(AMGraph* pg); // 初始化void ShowAdjMatrix(AMGraph* pg); // 顯示鄰接矩陣int GetVetexPos(AMGraph* pg, VertexType v); // 獲取頂點的位置void InsertVertex(AMGraph* pg, VertexType v); // 插入頂點
void InsertEdge(AMGraph* pg, VertexType v1, VertexType v2); // 插入邊void EraseVertex(AMGraph* pg, VertexType v); // 刪除頂點
void EraseEdge(AMGraph* pg, VertexType v1, VertexType v2); // 刪除邊int GetFirstAdjVexPos(AMGraph* pg, VertexType v); // 獲取 v 的第一個鄰接頂點的位置
int GetNextAdjVexPos(AMGraph* pg, VertexType v, VertexType w);
// 獲取 v 的（相對于 w 的）下一個鄰接頂點的位置void AMGraphDestroy(AMGraph* pg); // 銷毀三、AMGraph.c
-
初始化：
void AMGraphInit(AMGraph* pg) {assert(pg);pg->vSize = pg->eSize = 0;pg->capacity = DEFAULT_CAPACITY;pg->vertices = (VertexType*)malloc(sizeof(VertexType) * pg->capacity);assert(pg->vertices);pg->edges = (EdgeType**)malloc(sizeof(EdgeType*) * pg->capacity);assert(pg->edges);for (int i = 0; i < pg->capacity; ++i){pg->edges[i] = (EdgeType*)malloc(sizeof(EdgeType) * pg->capacity);assert(pg->edges[i]);for (int j = 0; j < pg->capacity; ++j){pg->edges[i][j] = 0;}} } -
獲取頂點的位置：
int GetVetexPos(AMGraph* pg, VertexType v) {assert(pg);for (int i = 0; i < pg->vSize; ++i){if (pg->vertices[i] == v)return i;}return -1; } -
顯示鄰接矩陣：
void ShowAdjMatrix(AMGraph* pg) {assert(pg);printf(" "); // 輸出兩個空格for (int i = 0; i < pg->vSize; ++i){printf("%c ", pg->vertices[i]);}printf("\n");for (int i = 0; i < pg->vSize; ++i){printf("%c ", pg->vertices[i]);for (int j = 0; j < pg->vSize; ++j){printf("%d ", pg->edges[i][j]);}printf("\n");} } -
插入頂點：
void InsertVertex(AMGraph* pg, VertexType v) {assert(pg);// 考慮是否需要擴容if (pg->vSize == pg->capacity){VertexType* tmp1 = (VertexType*)realloc(pg->vertices, sizeof(VertexType) * 2 * pg->capacity);assert(tmp1);pg->vertices = tmp1;EdgeType** tmp2 = (EdgeType**)realloc(pg->edges, sizeof(EdgeType*) * 2 * pg->capacity);assert(tmp2);pg->edges = tmp2;for (int i = 0; i < pg->capacity; ++i){EdgeType* tmp3 = (EdgeType*)realloc(pg->edges[i], sizeof(EdgeType) * 2 * pg->capacity);assert(tmp3);pg->edges[i] = tmp3;for (int j = pg->capacity; j < 2 * pg->capacity; ++j){pg->edges[i][j] = 0;}}for (int i = pg->capacity; i < 2 * pg->capacity; ++i){pg->edges[i] = (EdgeType*)malloc(sizeof(EdgeType) * 2 * pg->capacity);assert(pg->edges[i]);for (int j = 0; j < 2 * pg->capacity; ++j){pg->edges[i][j] = 0;}}pg->capacity *= 2;}// 插入頂點pg->vertices[pg->vSize++] = v; } -
插入邊：
void InsertEdge(AMGraph* pg, VertexType v1, VertexType v2) {assert(pg);int pos1 = GetVetexPos(pg, v1);int pos2 = GetVetexPos(pg, v2);if (pos1 == -1 || pos2 == -1)return;if (pg->edges[pos1][pos2] != 0)return;pg->edges[pos1][pos2] = pg->edges[pos2][pos1] = 1;++pg->eSize; } -
刪除頂點：
void EraseVertex(AMGraph* pg, VertexType v) {assert(pg);int pos = GetVetexPos(pg, v);if (pos == -1)return;// cnt 為和 v 相關聯的邊的數目int cnt = 0;for (int j = 0; j < pg->vSize; ++j){if (pg->edges[pos][j] != 0)++cnt;}pg->vertices[pos] = pg->vertices[pg->vSize - 1];for (int j = 0; j < pg->vSize; ++j){pg->edges[pos][j] = pg->edges[pg->vSize - 1][j];}for (int i = 0; i < pg->vSize; ++i){pg->edges[i][pos] = pg->edges[i][pg->vSize - 1];}--pg->vSize;pg->eSize -= cnt; } -
刪除邊：
void EraseEdge(AMGraph* pg, VertexType v1, VertexType v2) {assert(pg);int pos1 = GetVetexPos(pg, v1);int pos2 = GetVetexPos(pg, v2);if (pos1 == -1 || pos2 == -1)return;if (pg->edges[pos1][pos2] == 0)return;pg->edges[pos1][pos2] = pg->edges[pos2][pos1] = 0;--pg->eSize; } -
獲取 v 的第一個鄰接頂點：
int GetFirstAdjVexPos(AMGraph* pg, VertexType v) {assert(pg);int pos = GetVetexPos(pg, v);if (pos == -1)return -1;for (int j = 0; j < pg->vSize; ++j){if (pg->edges[pos][j] != 0)return j;}return -1; } -
獲取 v 的（相對于 w 的）下一個鄰接頂點：
int GetNextAdjVexPos(AMGraph* pg, VertexType v, VertexType w) {assert(pg);int pos1 = GetVetexPos(pg, v);int pos2 = GetVetexPos(pg, w);if (pos1 == -1 || pos2 == -1)return -1;for (int j = pos2 + 1; j < pg->vSize; ++j){if (pg->edges[pos1][j] != 0)return j;}return -1; } -
銷毀：
void AMGraphDestroy(AMGraph* pg) {assert(pg);free(pg->vertices);pg->vertices = NULL;for (int i = 0; i < pg->capacity; ++i){free(pg->edges[i]);pg->edges[i] = NULL;}free(pg->edges);pg->edges = NULL;pg->vSize = pg->eSize = pg->capacity = 0; }
四、Test.c
#include "AMGraph.h"
#include <stdio.h>int main()
{AMGraph g;AMGraphInit(&g); InsertVertex(&g, 'A');InsertVertex(&g, 'B');InsertVertex(&g, 'C');InsertVertex(&g, 'D');InsertVertex(&g, 'E');InsertEdge(&g, 'A', 'B');InsertEdge(&g, 'A', 'D');InsertEdge(&g, 'B', 'C');InsertEdge(&g, 'B', 'E');InsertEdge(&g, 'C', 'D');InsertEdge(&g, 'C', 'E');ShowAdjMatrix(&g);printf("\n");EraseVertex(&g, 'C');ShowAdjMatrix(&g);printf("\n");EraseEdge(&g, 'A', 'B');ShowAdjMatrix(&g);printf("\n");printf("%d\n", GetFirstAdjVexPos(&g, 'A')); // 3printf("%d\n", GetNextAdjVexPos(&g, 'A', 'D')); // -1AMGraphDestroy(&g);return 0;
}
)
