图的基本操作c语言代码
时间: 2023-09-11 19:07:27 浏览: 38
以下是图的基本操作C语言代码示例:
1. 定义图结构体
```
#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;
```
2. 创建图
```
void CreateGraph(ALGraph *G) {
printf("请输入顶点数和边数:");
scanf("%d %d", &G->vexnum, &G->arcnum);
for (int i = 0; i < G->vexnum; i++) {
printf("请输入第%d个顶点的值:", i+1);
scanf("%d", &G->vertices[i].data);
G->vertices[i].firstarc = NULL;
}
for (int i = 0; i < G->arcnum; i++) {
int v1, v2;
printf("请输入第%d条边的两个顶点编号:", i+1);
scanf("%d %d", &v1, &v2);
ArcNode *arc1 = (ArcNode*)malloc(sizeof(ArcNode));
arc1->adjvex = v2 - 1;
arc1->next = G->vertices[v1 - 1].firstarc;
G->vertices[v1 - 1].firstarc = arc1;
ArcNode *arc2 = (ArcNode*)malloc(sizeof(ArcNode));
arc2->adjvex = v1 - 1;
arc2->next = G->vertices[v2 - 1].firstarc;
G->vertices[v2 - 1].firstarc = arc2;
}
}
```
3. 遍历图
```
void DFS(ALGraph G, int v, int visited[]) {
visited[v] = 1;
printf("%d ", G.vertices[v].data);
ArcNode *p = G.vertices[v].firstarc;
while (p != NULL) {
int w = p->adjvex;
if (!visited[w]) {
DFS(G, w, visited);
}
p = p->next;
}
}
void BFS(ALGraph G, int v, int visited[]) {
int queue[MAX_VERTEX_NUM], front = 0, rear = 0;
visited[v] = 1;
printf("%d ", G.vertices[v].data);
queue[rear++] = v;
while (front < rear) {
int w = queue[front++];
ArcNode *p = G.vertices[w].firstarc;
while (p != NULL) {
int k = p->adjvex;
if (!visited[k]) {
visited[k] = 1;
printf("%d ", G.vertices[k].data);
queue[rear++] = k;
}
p = p->next;
}
}
}
```
4. 销毁图
```
void DestroyGraph(ALGraph *G) {
for (int i = 0; i < G->vexnum; i++) {
ArcNode *p = G->vertices[i].firstarc;
while (p != NULL) {
ArcNode *q = p->next;
free(p);
p = q;
}
}
G->vexnum = 0;
G->arcnum = 0;
}
```