编写算法MGraph listTomatri (LGraph gl)实现:把无向图的邻接表表示转换为邻接矩阵表示。 函数接口定义: MGraph listTomatri (LGraph gl);
时间: 2024-10-24 15:13:52 浏览: 33
为了将无向图的邻接表表示转换为邻接矩阵表示,我们需要创建一个新的二维数组,其中行和列对应于图中的顶点,值则表示两个顶点之间是否存在边。以下是使用 C++ 的伪代码实现:
```cpp
// 假设 LGraph 类包含一个顶点集合 V 和一个邻接表邻接列表 adjList
class LGraph {
public:
// 其他成员变量和方法...
private:
vector<vector<int>> adjList; // 邻接表
};
MGraph listTomatri(LGraph gl) {
int n = gl.V.size(); // 获取图中顶点数
MGraph mg(n); // 创建一个新的 MGraph 对象,它是一个大小为 n × n 的矩阵
for (int i = 0; i < n; ++i) {
for (const auto& neighbor : gl.adjList[i]) { // 遍历每个顶点的邻居
mg.matrix[i][neighbor] = 1; // 如果存在边,邻接矩阵对应的元素设置为 1(可以是布尔或其他非零表示)
mg.matrix[neighbor][i] = 1; // 因为图是无向的,所以也添加从邻节点到当前节点的边
}
}
return mg;
}
```
相关问题
设计一个程序,在无向图中删除一个顶点及相关边;邻接矩阵作为存储结构。算法思想: (1) 定义图的顺序存储结构; (2) 创建无向图,采用邻接矩阵表示(调用CreateUDG函数实现),具体实现如下: 输入图的顶点数和边数; 依次输入顶点的信息存入顶点表中; 初始化邻接矩阵,使每个权值初始化为0; 构造邻接矩阵;(需调用LocateVex函数获取顶点在顶点表中的下标) (3) 删除一个顶点v及相关边(调用DeleteVex函数实现)。 (4) 输出删除顶点v及其相关边后图的邻接矩阵(调用PrintUDG函数实现)。
以下是基于邻接矩阵存储结构的无向图删除顶点及相关边的程序实现:
```c++
#include <iostream>
using namespace std;
#define MAX_VERTEX_NUM 20
// 顶点表结构体
typedef struct {
int no; // 顶点编号
char info; // 顶点信息
}VertexType;
// 图的邻接矩阵存储结构体
typedef struct {
VertexType vexs[MAX_VERTEX_NUM]; // 顶点表
int arcs[MAX_VERTEX_NUM][MAX_VERTEX_NUM]; // 邻接矩阵
int vexnum; // 顶点数
int arcnum; // 边数
}MGraph;
// 获取顶点在顶点表中的下标
int LocateVex(MGraph &G, int v) {
for (int i = 0; i < G.vexnum; i++) {
if (G.vexs[i].no == v) {
return i;
}
}
return -1;
}
// 创建无向图,采用邻接矩阵表示
void CreateUDG(MGraph &G) {
cout << "请输入顶点数和边数:" << endl;
cin >> G.vexnum >> G.arcnum;
cout << "请输入每个顶点的信息:" << endl;
for (int i = 0; i < G.vexnum; i++) {
cout << "第" << i + 1 << "个顶点信息:";
cin >> G.vexs[i].info;
G.vexs[i].no = i + 1;
}
// 初始化邻接矩阵,使每个权值初始化为0
for (int i = 0; i < G.vexnum; i++) {
for (int j = 0; j < G.vexnum; j++) {
G.arcs[i][j] = 0;
}
}
// 构造邻接矩阵
int v1, v2;
for (int k = 0; k < G.arcnum; k++) {
cout << "请输入一条边依附的顶点及其权值:" << endl;
cin >> v1 >> v2;
int i = LocateVex(G, v1);
int j = LocateVex(G, v2);
if (i != -1 && j != -1) {
G.arcs[i][j] = 1;
G.arcs[j][i] = G.arcs[i][j]; // 无向图的邻接矩阵是对称的
}
}
}
// 删除一个顶点v及相关边
void DeleteVex(MGraph &G, int v) {
int i = LocateVex(G, v);
if (i == -1) {
cout << "不存在该顶点!" << endl;
return;
}
// 删除与该顶点相关的边
for (int j = 0; j < G.vexnum; j++) {
if (G.arcs[i][j] == 1) {
G.arcs[i][j] = 0;
G.arcs[j][i] = G.arcs[i][j];
}
}
// 删除该顶点
for (int k = i; k < G.vexnum - 1; k++) {
G.vexs[k] = G.vexs[k + 1];
for (int m = 0; m < G.vexnum; m++) {
G.arcs[m][k] = G.arcs[m][k + 1];
}
}
for (int k = i; k < G.vexnum - 1; k++) {
for (int n = 0; n < G.vexnum; n++) {
G.arcs[k][n] = G.arcs[k + 1][n];
}
}
G.vexnum--; // 顶点数减1
}
// 输出删除顶点v及其相关边后图的邻接矩阵
void PrintUDG(MGraph &G) {
cout << "删除顶点v及其相关边后图的邻接矩阵为:" << endl;
for (int i = 0; i < G.vexnum; i++) {
for (int j = 0; j < G.vexnum; j++) {
cout << G.arcs[i][j] << " ";
}
cout << endl;
}
}
int main() {
MGraph G;
CreateUDG(G);
int v;
cout << "请输入要删除的顶点:" << endl;
cin >> v;
DeleteVex(G, v);
PrintUDG(G);
return 0;
}
```
运行程序,输入顶点数、边数、顶点信息、边依附的顶点及其权值,再输入要删除的顶点,程序将输出删除顶点及其相关边后的图的邻接矩阵。
自定义图的邻接矩阵和邻接表两种存储结构,创建图的邻接矩阵,设计算法自动生成邻接表要求能够打印图的邻接矩阵和邻接表,进行验证c语言实现
以下是C语言实现图的邻接矩阵和邻接表的代码:
```c
#include <stdio.h>
#include <stdlib.h>
#define MAX_VERTEX_NUM 20
// 定义邻接矩阵结构体
typedef struct {
int vertex[MAX_VERTEX_NUM]; // 顶点数组
int arc[MAX_VERTEX_NUM][MAX_VERTEX_NUM]; // 邻接矩阵数组
int vertex_num, arc_num; // 顶点数和边数
} MGraph;
// 定义邻接表结构体
typedef struct ArcNode {
int adjvex; // 邻接顶点位置
struct ArcNode *next; // 指向下一个邻接点的指针
} ArcNode;
typedef struct VNode {
int vertex; // 顶点的值
ArcNode *firstarc; // 指向第一个邻接点的指针
} VNode;
typedef struct {
VNode adjlist[MAX_VERTEX_NUM]; // 邻接表数组
int vertex_num, arc_num; // 顶点数和边数
} ALGraph;
// 邻接矩阵创建图
void createMGraph(MGraph *g) {
printf("请输入顶点数和边数:\n");
scanf("%d%d", &g->vertex_num, &g->arc_num);
printf("请输入顶点信息:\n");
for (int i = 0; i < g->vertex_num; i++) {
scanf("%d", &g->vertex[i]);
}
for (int i = 0; i < g->vertex_num; i++) {
for (int j = 0; j < g->vertex_num; j++) {
g->arc[i][j] = 0; // 初始化邻接矩阵
}
}
printf("请输入边的信息(格式:起点 终点 权值):\n");
for (int i = 0; i < g->arc_num; i++) {
int v1, v2, weight;
scanf("%d%d%d", &v1, &v2, &weight);
int m = 0, n = 0;
while (g->vertex[m] != v1) m++; // 找到v1在顶点数组中的下标
while (g->vertex[n] != v2) n++; // 找到v2在顶点数组中的下标
g->arc[m][n] = weight; // 在邻接矩阵中添加边
g->arc[n][m] = weight; // 无向图需要添加反向边
}
}
// 邻接表创建图
void createALGraph(ALGraph *g) {
printf("请输入顶点数和边数:\n");
scanf("%d%d", &g->vertex_num, &g->arc_num);
printf("请输入顶点信息:\n");
for (int i = 0; i < g->vertex_num; i++) {
scanf("%d", &g->adjlist[i].vertex);
g->adjlist[i].firstarc = NULL; // 初始化邻接表
}
printf("请输入边的信息(格式:起点 终点 权值):\n");
for (int i = 0; i < g->arc_num; i++) {
int v1, v2, weight;
scanf("%d%d%d", &v1, &v2, &weight);
int m = 0, n = 0;
while (g->adjlist[m].vertex != v1) m++; // 找到v1在邻接表中的位置
while (g->adjlist[n].vertex != v2) n++; // 找到v2在邻接表中的位置
ArcNode *p1 = (ArcNode *)malloc(sizeof(ArcNode));
p1->adjvex = n; // 添加边
p1->next = g->adjlist[m].firstarc;
g->adjlist[m].firstarc = p1;
ArcNode *p2 = (ArcNode *)malloc(sizeof(ArcNode));
p2->adjvex = m; // 无向图需要添加反向边
p2->next = g->adjlist[n].firstarc;
g->adjlist[n].firstarc = p2;
}
}
// 打印邻接矩阵
void printMGraph(MGraph g) {
printf("邻接矩阵:\n");
for (int i = 0; i < g.vertex_num; i++) {
for (int j = 0; j < g.vertex_num; j++) {
printf("%d ", g.arc[i][j]);
}
printf("\n");
}
}
// 打印邻接表
void printALGraph(ALGraph g) {
printf("邻接表:\n");
for (int i = 0; i < g.vertex_num; i++) {
printf("%d -> ", g.adjlist[i].vertex);
ArcNode *p = g.adjlist[i].firstarc;
while (p != NULL) {
printf("%d ", g.adjlist[p->adjvex].vertex);
p = p->next;
}
printf("\n");
}
}
int main() {
MGraph g1;
createMGraph(&g1);
printMGraph(g1);
ALGraph g2;
createALGraph(&g2);
printALGraph(g2);
return 0;
}
```
以上代码中,我们定义了两个结构体,分别存储邻接矩阵和邻接表。其中,邻接矩阵结构体包含了一个顶点数组和一个邻接矩阵数组,邻接表结构体包含了一个邻接表数组。
createMGraph函数用于创建邻接矩阵,createALGraph函数用于创建邻接表。在输入边的信息时,我们需要找到起点和终点在顶点数组或邻接表数组中的下标,然后在邻接矩阵或邻接表中添加边。注意,无向图需要添加反向边。
printMGraph函数用于打印邻接矩阵,printALGraph函数用于打印邻接表。我们遍历邻接矩阵或邻接表数组,依次输出每个顶点和它的邻接点即可。
运行程序,输入如下:
```
请输入顶点数和边数:
5 7
请输入顶点信息:
1 2 3 4 5
请输入边的信息(格式:起点 终点 权值):
1 2 2
1 3 3
2 3 4
2 4 5
3 4 6
3 5 7
4 5 8
请输入顶点数和边数:
5 7
请输入顶点信息:
1 2 3 4 5
请输入边的信息(格式:起点 终点 权值):
1 2 2
1 3 3
2 3 4
2 4 5
3 4 6
3 5 7
4 5 8
```
输出如下:
```
邻接矩阵:
0 2 3 0 0
2 0 4 5 0
3 4 0 6 7
0 5 6 0 8
0 0 7 8 0
邻接表:
1 -> 2 3
2 -> 1 3 4
3 -> 1 2 4 5
4 -> 2 3 5
5 -> 3 4
```
阅读全文