写一个creatALGraph函数可以吗?
时间: 2023-08-31 07:42:57 浏览: 57
### 回答1:
当然可以,以下是一个基于邻接表表示图的创建函数 `creatALGraph` 的示例代码:
```c
#include <stdio.h>
#include <stdlib.h>
#define MAX_VERTEX_NUM 100 // 最大顶点数
// 边表节点
typedef struct ArcNode {
int adjvex; // 该弧所指向的顶点的位置
struct ArcNode *next; // 指向下一条弧的指针
} ArcNode;
// 顶点表节点
typedef struct VNode {
int data; // 顶点信息
ArcNode *firstarc; // 指向第一条依附该顶点的弧的指针
} VNode, AdjList[MAX_VERTEX_NUM];
// 图
typedef struct {
AdjList vertices; // 邻接表
int vexnum, arcnum; // 顶点数和边数
} ALGraph;
// 创建图
void creatALGraph(ALGraph *G) {
printf("请输入顶点数和边数:");
scanf("%d %d", &G->vexnum, &G->arcnum);
printf("请输入顶点信息:\n");
for (int i = 0; i < G->vexnum; ++i) {
scanf("%d", &G->vertices[i].data);
G->vertices[i].firstarc = NULL;
}
printf("请输入每条边的两个顶点的位置:\n");
int v1, v2;
for (int i = 0; i < G->arcnum; ++i) {
scanf("%d %d", &v1, &v2);
ArcNode *p = (ArcNode*)malloc(sizeof(ArcNode));
p->adjvex = v2;
p->next = G->vertices[v1].firstarc;
G->vertices[v1].firstarc = p;
p = (ArcNode*)malloc(sizeof(ArcNode));
p->adjvex = v1;
p->next = G->vertices[v2].firstarc;
G->vertices[v2].firstarc = p;
}
}
// 主函数
int main() {
ALGraph G;
creatALGraph(&G);
return 0;
}
```
该函数中,我们先通过 `scanf` 输入顶点数和边数,再通过循环输入每个顶点的信息。接着,我们使用循环输入每条边的两个顶点的位置,依次将这些边插入到邻接表中,最终得到一个完整的邻接表表示的图。
需要注意的是,由于邻接表是一种动态数据结构,因此在插入边的时候需要动态地申请内存空间,需要在程序结束时手动释放这些空间,以免造成内存泄漏。
### 回答2:
可以的,下面是一个创建有向图的creatALGraph函数的示例:
```cpp
#include <iostream>
#include <vector>
using namespace std;
const int MAX_VERTEX_NUM = 100; // 图中顶点的最大数量
// 边表节点
struct ArcNode {
int adjvex; // 邻接点下标
struct ArcNode* nextarc; // 指向下一个邻接点的指针
};
// 顶点表节点
struct VNode {
int data; // 顶点的数据
ArcNode* firstarc; // 指向第一个邻接点的指针
};
// 图的结构体
struct ALGraph {
VNode vertices[MAX_VERTEX_NUM]; // 顶点表
int vexnum; // 顶点数
int arcnum; // 弧数
};
// 创建有向图函数
void createALGraph(ALGraph& G, const vector<vector<int>>& edges) {
G.vexnum = edges.size();
G.arcnum = 0;
// 初始化顶点表
for (int i = 0; i < G.vexnum; i++) {
G.vertices[i].data = i;
G.vertices[i].firstarc = nullptr;
}
// 构建边表
for (int i = 0; i < G.vexnum; i++) {
for (int j = 0; j < G.vexnum; j++) {
if (edges[i][j] != 0) {
ArcNode* arc = new ArcNode();
arc->adjvex = j;
arc->nextarc = G.vertices[i].firstarc;
G.vertices[i].firstarc = arc;
G.arcnum++;
}
}
}
}
int main() {
vector<vector<int>> edges = {
{0, 1, 0},
{0, 0, 1},
{1, 0, 0}
};
ALGraph G;
createALGraph(G, edges);
cout << "顶点数:" << G.vexnum << endl;
cout << "弧数:" << G.arcnum << endl;
return 0;
}
```
这个函数接受一个二维数组`edges`作为参数,其中`edges[i][j]`表示顶点i到顶点j是否存在弧,如果存在,则值不为0。函数首先根据边的数量初始化顶点表,然后根据`edges`中的值构建边表,最后将构建好的有向图保存在结构体`ALGraph`中。
### 回答3:
可以的。创建一个有向图或无向图的函数称为creatALGraph函数。这个函数可以根据给定的输入参数来创建图,并返回一个表示该图的邻接表。
在这个函数中,我们首先初始化邻接表,然后根据输入参数,逐个添加边或顶点到邻接表中。
如果是有向图,我们可以通过为每条边添加一个入度和出度的信息来创建邻接表。每个顶点的出度信息存储在与该顶点对应的链表节点中,同时,对于每个顶点,我们还需要记录它的入度信息,使得可以通过邻接表进行反向遍历。
如果是无向图,我们可以将每条边的两个顶点都加到对方的邻接表中,表示它们之间相互连接。
在创建邻接表的过程中,可以使用循环和条件语句来判断边或顶点是否已经存在于邻接表中,从而避免重复添加。同时,我们还可以使用动态内存分配来动态创建邻接表节点和边节点,使其适应图的规模变化。
总的来说,通过实现creatALGraph函数,我们可以灵活地创建出任意类型的图,并使用邻接表来表示和存储图的结构。
相关推荐
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_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)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)