实现邻接矩阵和邻接表存储结构
时间: 2023-10-21 10:30:31 浏览: 54
这个问题是关于数据结构与算法的,可以回答。邻接矩阵和邻接表是两种常用的图的存储结构。邻接矩阵是通过一个二维数组来表示各个顶点之间的连接情况,如果两个顶点之间有连线则为1,否则为0。邻接表则是通过链表来表示顶点之间的相邻关系,每个顶点对应一个链表,保存与其相邻的顶点。对于稠密图,邻接矩阵更适合存储,而对于稀疏图,邻接表更适合存储。
相关问题
实现邻接矩阵和邻接表存储结构下的createUDG()和createDG()算法。
邻接矩阵和邻接表是两种图的常用存储结构。下面是createUDG()和createDG()算法的实现:
邻接矩阵存储结构:
```
// 无向图的邻接矩阵存储结构
#define MAXV 100 // 最大顶点数
typedef struct {
int vertex[MAXV]; // 存储顶点信息
int edge[MAXV][MAXV]; // 存储边信息
int numVertex, numEdge; // 存储顶点数和边数
} MGraph;
// 创建无向图的邻接矩阵存储结构
void createUDG(MGraph *G) {
int i, j, k;
printf("请输入顶点数和边数:");
scanf("%d %d", &G->numVertex, &G->numEdge);
// 初始化邻接矩阵,全部边权值为0
for (i = 0; i < G->numVertex; i++) {
for (j = 0; j < G->numVertex; j++) {
G->edge[i][j] = 0;
}
}
// 读入顶点信息
printf("请输入顶点信息:");
for (i = 0; i < G->numVertex; i++) {
scanf("%d", &G->vertex[i]);
}
// 读入边信息
printf("请输入边信息:");
for (k = 0; k < G->numEdge; k++) {
scanf("%d %d", &i, &j);
G->edge[i][j] = 1;
G->edge[j][i] = 1; // 无向图的邻接矩阵是对称的
}
}
```
```
// 有向图的邻接矩阵存储结构
#define MAXV 100 // 最大顶点数
typedef struct {
int vertex[MAXV]; // 存储顶点信息
int edge[MAXV][MAXV]; // 存储边信息
int numVertex, numEdge; // 存储顶点数和边数
} MGraph;
// 创建有向图的邻接矩阵存储结构
void createDG(MGraph *G) {
int i, j, k;
printf("请输入顶点数和边数:");
scanf("%d %d", &G->numVertex, &G->numEdge);
// 初始化邻接矩阵,全部边权值为0
for (i = 0; i < G->numVertex; i++) {
for (j = 0; j < G->numVertex; j++) {
G->edge[i][j] = 0;
}
}
// 读入顶点信息
printf("请输入顶点信息:");
for (i = 0; i < G->numVertex; i++) {
scanf("%d", &G->vertex[i]);
}
// 读入边信息
printf("请输入边信息:");
for (k = 0; k < G->numEdge; k++) {
scanf("%d %d", &i, &j);
G->edge[i][j] = 1;
}
}
```
邻接表存储结构:
```
// 无向图的邻接表存储结构
#define MAXV 100 // 最大顶点数
typedef struct ArcNode {
int adjvex; // 邻接顶点编号
struct ArcNode *next; // 指向下一个邻接点的指针
} ArcNode;
typedef struct {
int vertex; // 存储顶点信息
ArcNode *firstarc; // 指向第一个邻接点的指针
} VNode;
typedef struct {
VNode adjList[MAXV]; // 存储顶点和边信息
int numVertex, numEdge; // 存储顶点数和边数
} ALGraph;
// 创建无向图的邻接表存储结构
void createUDG(ALGraph *G) {
int i, j, k;
ArcNode *p;
printf("请输入顶点数和边数:");
scanf("%d %d", &G->numVertex, &G->numEdge);
// 初始化邻接表为空表
for (i = 0; i < G->numVertex; i++) {
G->adjList[i].firstarc = NULL;
}
// 读入顶点信息
printf("请输入顶点信息:");
for (i = 0; i < G->numVertex; i++) {
scanf("%d", &G->adjList[i].vertex);
}
// 读入边信息,建立邻接表
printf("请输入边信息:");
for (k = 0; k < G->numEdge; k++) {
scanf("%d %d", &i, &j);
// 头插法插入边信息
p = (ArcNode *)malloc(sizeof(ArcNode));
p->adjvex = j;
p->next = G->adjList[i].firstarc;
G->adjList[i].firstarc = p;
p = (ArcNode *)malloc(sizeof(ArcNode));
p->adjvex = i;
p->next = G->adjList[j].firstarc;
G->adjList[j].firstarc = p; // 无向图的邻接表是对称的
}
}
```
```
// 有向图的邻接表存储结构
#define MAXV 100 // 最大顶点数
typedef struct ArcNode {
int adjvex; // 邻接顶点编号
struct ArcNode *next; // 指向下一个邻接点的指针
} ArcNode;
typedef struct {
int vertex; // 存储顶点信息
ArcNode *firstarc; // 指向第一个邻接点的指针
} VNode;
typedef struct {
VNode adjList[MAXV]; // 存储顶点和边信息
int numVertex, numEdge; // 存储顶点数和边数
} ALGraph;
// 创建有向图的邻接表存储结构
void createDG(ALGraph *G) {
int i, j, k;
ArcNode *p;
printf("请输入顶点数和边数:");
scanf("%d %d", &G->numVertex, &G->numEdge);
// 初始化邻接表为空表
for (i = 0; i < G->numVertex; i++) {
G->adjList[i].firstarc = NULL;
}
// 读入顶点信息
printf("请输入顶点信息:");
for (i = 0; i < G->numVertex; i++) {
scanf("%d", &G->adjList[i].vertex);
}
// 读入边信息,建立邻接表
printf("请输入边信息:");
for (k = 0; k < G->numEdge; k++) {
scanf("%d %d", &i, &j);
// 头插法插入边信息
p = (ArcNode *)malloc(sizeof(ArcNode));
p->adjvex = j;
p->next = G->adjList[i].firstarc;
G->adjList[i].firstarc = p;
}
}
```
实现图的邻接矩阵和邻接表存储
好的,我可以回答你的问题。
邻接矩阵和邻接表是两种常用的图的存储方式。
邻接矩阵是用一个二维数组来表示图的结构,其中数组的每个元素代表了两个顶点之间是否有边相连。如果两个顶点之间有边相连,则数组对应元素的值为1,否则为0。如果图是有向图,则数组可能不对称;如果图是无向图,则数组是对称的。
下面是一个无向图的邻接矩阵示例:
```
0 1 2 3 4
0 0 1 0 1 0
1 1 0 1 0 0
2 0 1 0 1 1
3 1 0 1 0 1
4 0 0 1 1 0
```
邻接表是用链表来表示图的结构,其中每个顶点都对应一条链表,链表中存储了该顶点所连接的所有顶点的信息。如果图是有向图,则链表可能有向;如果图是无向图,则链表是双向的。
下面是一个无向图的邻接表示例:
```
0 -> 1 -> 3
1 -> 0 -> 2
2 -> 1 -> 3 -> 4
3 -> 0 -> 2 -> 4
4 -> 2 -> 3
```
以上是邻接矩阵和邻接表的简单介绍,如果需要实现的话可以根据自己的需求选择其中一种存储方式,并按照相应的方法进行实现。
相关推荐
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)