目录😋
任务描述
本关任务：编写一个程序实现图的邻接矩阵和邻接表的存储。
相关知识
为了完成本关任务，你需要掌握：
- 带权有向图
- 图的邻接矩阵，
- 图的邻接表。
1. 带权有向图
针对有向图的邻接矩阵和邻接表的存储，如下列图形：
编辑
编辑
2. 图的邻接矩阵
若 G 为带权有向图，其邻接矩阵 A 中的元素 Aij 遵循以下规则进行赋值：
- 当 i≠j，并且存在从顶点 i 指向顶点 j 的有向边，即 <i, j>∈E (G) 时，此时 Aij 的值等于该有向边的权值 wij；
- 当 i = j 时，Aij 的取值为 0，这表示顶点到自身的权值为 0；
- 而在其他情况下，也就是不存在从顶点 i 指向顶点 j 的有向边时，Aij 的值设定为无穷大（通常用特定的极大数值来表示，例如在程序实现中可以采用类似 INT_MAX 这样能表示极大值的常量来表示无穷大的概念）。
示例代码如下：
if (g.edges[i][j]!=INF) printf("%d ",g.edges[i][j]); else printf("%s ","∞");
（INF表示无穷大，表示整数：32767)
3. 图的邻接表
邻接表结点由三个域组成：
- adjvex指示与顶点vi邻接的点在图中的位置,
- nextarc指示下一条边或弧的结点,
- info存储与边或弧的权值。
表头结点由两个域组成：
- data存储顶点vi的名称或其他信息,
- firstarc指向链表中第一个结点。
示例代码如下：
for (int i=0;i<G->n;i++) { p=G->adjlist[i].firstarc; printf("%3d: ",i); while (p!=NULL) { printf("%3d[%d]→",p->adjvex,p->weight); p=p->nextarc; } printf("∧\n"); }
测试说明
平台会对你编写的代码进行测试：
测试输入：（ 输入图的顶点数和边数，再输入图的邻接矩阵。）
6 10 0 5 32767 7 32767 32767 32767 0 4 32767 32767 32767 8 32767 0 32767 32767 9 32767 32767 5 0 32767 6 32767 32767 32767 5 0 32767 3 32767 32767 32767 1 0
预期输出：（Prim算法求解结果）
边(0,5)权为:3 边(5,4)权为:1 边(0,1)权为:5 边(1,2)权为:4 边(4,3)权为:5
开始你的任务吧，祝你成功！
通关代码
using namespace std; const int MAX_VERTICES = 6; // 最大顶点数 const int INF = 32767; // 表示无穷大 // 邻接矩阵表示的图 struct GraphMatrix { int n; // 顶点数 vector<vector<int>> edges; // 邻接矩阵 }; // 邻接表的边节点 struct ArcNode { int adjvex; // 邻接点在图中的位置 int weight; // 边的权重 ArcNode *nextarc; // 指向下一条边 }; // 邻接表 struct VNode { int data; // 顶点信息 ArcNode *firstarc; // 指向第一条边 }; struct GraphList { int n; // 顶点数 vector<VNode> adjlist; // 邻接表 }; // 输入邻接矩阵并构建图 void inputGraphMatrix(GraphMatrix &g) { cin >> g.n; // 读入顶点数 int e; // 边数 cin >> e; // 读入边数 g.edges.resize(g.n, vector<int>(g.n, INF)); for (int i = 0; i < g.n; ++i) { g.edges[i][i] = 0; // 对角线元素为0 } // 读入邻接矩阵 for (int i = 0; i < g.n; ++i) { for (int j = 0; j < g.n; ++j) { cin >> g.edges[i][j]; } } } // 输出邻接矩阵 void printGraphMatrix(const GraphMatrix &g) { cout << "(1)图G的邻接矩阵:" << endl; for (int i = 0; i < g.n; ++i) { for (int j = 0; j < g.n; ++j) { if (g.edges[i][j] == INF) { cout << "∞ "; } else { cout << g.edges[i][j] << " "; } } cout << endl; } } // 构建邻接表 void buildGraphList(const GraphMatrix &gm, GraphList &gl) { gl.n = gm.n; gl.adjlist.resize(gl.n); for (int i = 0; i < gm.n; ++i) { gl.adjlist[i].data = i; // 存储顶点 gl.adjlist[i].firstarc = nullptr; // 初始化第一条边 } // 从邻接矩阵构建邻接表 for (int i = 0; i < gm.n; ++i) { for (int j = 0; j < gm.n; ++j) { if (gm.edges[i][j] != INF && gm.edges[i][j] != 0) { ArcNode *arc = new ArcNode(); // 动态分配新边 arc->adjvex = j; // 指向邻接点 arc->weight = gm.edges[i][j]; // 边的权重 arc->nextarc = nullptr; // 初始化下一条边为nullptr // 将新节点插入已排序的链表中 if (gl.adjlist[i].firstarc == nullptr || gl.adjlist[i].firstarc->adjvex > j) { arc->nextarc = gl.adjlist[i].firstarc; // 插入到链表头 gl.adjlist[i].firstarc = arc; } else { ArcNode *p = gl.adjlist[i].firstarc; while (p->nextarc != nullptr && p->nextarc->adjvex < j) { p = p->nextarc; // 寻找插入位置 } arc->nextarc = p->nextarc; // 插入 p->nextarc = arc; } } } } } // 输出邻接表 void printGraphList(const GraphList &gl) { cout << "(2)图G的邻接表:" << endl; for (int i = 0; i < gl.n; ++i) { cout << " " << i << ": "; ArcNode *p = gl.adjlist[i].firstarc; while (p != nullptr) { cout << " " << p->adjvex << "[" << p->weight << "]→"; p = p->nextarc; } cout << "∧" << endl; } } int main() { GraphMatrix gm; inputGraphMatrix(gm); printGraphMatrix(gm); GraphList gl; buildGraphList(gm, gl); printGraphList(gl); return 0; }
测试结果
编辑
