图的邻接多重表c语言
时间: 2024-02-25 16:55:29 浏览: 18
以下是邻接多重表的C语言实现:
```c
#define MAX_VERTEX_NUM 100 // 最大顶点数
typedef int VertexType; // 顶点类型
typedef struct ArcNode { // 边结点
int ivex, jvex; // 该边所依附的两个顶点的位置
struct ArcNode* ilink, * jlink; // 分别指向依附这两个顶点的下一条边
InfoType* info; // 边的相关信息
} ArcNode;
typedef struct VNode { // 顶点结点
VertexType data; // 顶点信息
ArcNode* firstin, * firstout; // 分别指向以该顶点为终点和起点的第一条边
} VNode, AdjMulList[MAX_VERTEX_NUM];
typedef struct { // 图
AdjMulList vertices; // 存放顶点的一维数组
int vexnum, arcnum; // 顶点数和边数
} AMLGraph;
```
其中 `ivex` 和 `jvex` 分别表示该边所依附的两个顶点在一维数组中的位置,`ilink` 和 `jlink` 分别指向依附这两个顶点的下一条边,`InfoType` 表示边的相关信息。`firstin` 和 `firstout` 分别指向以该顶点为终点和起点的第一条边。
相关问题
图的邻接表c语言实现
邻接表是一种表示图的数据结构,可以用于存储有向图或无向图。它采用链表的方式来存储每个顶点所对应的边集,因此比邻接矩阵更适用于表示稀疏图。以下是邻接表的C语言实现:
```c
#include <stdio.h>
#include <stdlib.h>
#define MAXVEX 100 // 最大顶点数
typedef char VertexType; // 顶点类型
typedef int EdgeType; // 边权值类型
// 边表结构体
typedef struct EdgeNode {
int adjvex; // 邻接点域,存储该顶点对应的下标
EdgeType weight; // 存储权值,对于非网图可以不需要
struct EdgeNode *next; // 链域,指向下一个邻接点
} EdgeNode;
// 顶点表结构体
typedef struct VertexNode {
VertexType data; // 顶点信息
EdgeNode *firstedge; // 边表头指针
} VertexNode, AdjList[MAXVEX];
// 图结构体
typedef struct {
AdjList adjList; // 邻接表
int numVertexes; // 顶点数
int numEdges; // 边数
} GraphAdjList;
// 建立图的邻接表结构
void CreateALGraph(GraphAdjList *G) {
int i, j, k;
EdgeNode *e;
printf("请输入顶点数和边数:\n");
scanf("%d %d", &G->numVertexes, &G->numEdges);
getchar(); // 把换行符取走
printf("请输入顶点信息:\n");
for (i = 0; i < G->numVertexes; i++) {
scanf("%c", &G->adjList[i].data);
G->adjList[i].firstedge = NULL;
getchar(); // 把换行符取走
}
printf("请输入边的信息:\n");
for (k = 0; k < G->numEdges; k++) {
printf("输入边(vi,vj)上的顶点序号:\n");
scanf("%d %d", &i, &j);
e = (EdgeNode *)malloc(sizeof(EdgeNode));
e->adjvex = j;
e->next = G->adjList[i].firstedge;
G->adjList[i].firstedge = e;
e = (EdgeNode *)malloc(sizeof(EdgeNode));
e->adjvex = i;
e->next = G->adjList[j].firstedge;
G->adjList[j].firstedge = e;
}
}
// 输出邻接表存储的图
void PrintALGraph(GraphAdjList G) {
int i;
EdgeNode *p;
printf("邻接表存储的图:\n");
for (i = 0; i < G.numVertexes; i++) {
printf("%d %c:", i, G.adjList[i].data);
p = G.adjList[i].firstedge;
while (p != NULL) {
printf("%d ", p->adjvex);
p = p->next;
}
printf("\n");
}
}
int main() {
GraphAdjList G;
CreateALGraph(&G);
PrintALGraph(G);
return 0;
}
```
无向图的邻接表c语言
邻接表是一种表示图的数据结构,对于无向图,我们可以使用C语言中的链表来实现邻接表。具体实现步骤如下:
1. 定义一个结构体来表示图中的每个顶点,包含顶点的编号和一个指向链表的指针。
```c
struct Vertex{
int id; // 顶点编号
struct Edge *edgeList; // 指向链表的指针
};
```
2. 定义一个结构体来表示图中的每条边,包含边的终点和下一条边的指针。
```c
struct Edge{
int dest; // 边的终点
struct Edge *next; // 指向下一条边的指针
};
```
3. 定义一个数组来存储图中的所有顶点。
```c
struct Vertex graph[MAX_VERTICES];
```
其中MAX_VERTICES表示顶点的最大数量。
4. 对于每个顶点,初始化其指向链表的指针为NULL。
```c
for(int i=0; i<MAX_VERTICES; i++){
graph[i].edgeList = NULL;
}
```
5. 添加边时,我们需要先找到边的起点,然后在起点的链表中添加一个新的边。具体实现可以参考下面的代码:
```c
void addEdge(int src, int dest){
struct Edge *newEdge = (struct Edge*)malloc(sizeof(struct Edge)); // 创建新的边节点
newEdge->dest = dest; // 设置边的终点为目标顶点
newEdge->next = graph[src].edgeList; // 将新的边节点插入到起点的链表头部
graph[src].edgeList = newEdge; // 更新起点的链表头指针
}
```
6. 遍历邻接表时,我们可以使用一个嵌套的循环来遍历每个顶点的链表。具体实现可以参考下面的代码:
```c
for(int i=0; i<MAX_VERTICES; i++){
printf("Vertex %d: ", graph[i].id);
struct Edge *curEdge = graph[i].edgeList;
while(curEdge != NULL){
printf("%d ", curEdge->dest);
curEdge = curEdge->next;
}
printf("\n");
}
```
以上就是无向图邻接表的C语言实现。
相关推荐
![](https://img-home.csdnimg.cn/images/20210720083646.png)
![docx](https://img-home.csdnimg.cn/images/20210720083331.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_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)