用c语言代码实现以邻接表为基础的图算法系统,要求有交互式页面,遍历等
时间: 2024-02-09 20:11:01 浏览: 31
很好,以下是一个简单的示例代码,实现了邻接表为基础的图算法系统,包括添加边、删除边、遍历等基本操作,并使用交互式页面与用户进行交互:
```
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
// 定义邻接表的节点结构体
typedef struct AdjListNode {
int dest;
struct AdjListNode *next;
} AdjListNode;
// 定义邻接表的头结构体
typedef struct AdjList {
AdjListNode *head;
} AdjList;
// 定义图的结构体
typedef struct Graph {
int numVertices;
AdjList *array;
} Graph;
// 创建新的邻接表节点
AdjListNode *createAdjListNode(int dest) {
AdjListNode *newNode = (AdjListNode*)malloc(sizeof(AdjListNode));
newNode->dest = dest;
newNode->next = NULL;
return newNode;
}
// 创建新的图
Graph *createGraph(int numVertices) {
Graph *graph = (Graph*)malloc(sizeof(Graph));
graph->numVertices = numVertices;
graph->array = (AdjList*)malloc(numVertices * sizeof(AdjList));
for (int i = 0; i < numVertices; i++) {
graph->array[i].head = NULL;
}
return graph;
}
// 添加边
void addEdge(Graph *graph, int src, int dest) {
AdjListNode *newNode = createAdjListNode(dest);
newNode->next = graph->array[src].head;
graph->array[src].head = newNode;
newNode = createAdjListNode(src);
newNode->next = graph->array[dest].head;
graph->array[dest].head = newNode;
}
// 删除边
void removeEdge(Graph *graph, int src, int dest) {
AdjListNode *node = graph->array[src].head, *prev = NULL;
while (node != NULL && node->dest != dest) {
prev = node;
node = node->next;
}
if (node == NULL) {
return;
}
if (prev == NULL) {
graph->array[src].head = node->next;
} else {
prev->next = node->next;
}
free(node);
node = graph->array[dest].head, prev = NULL;
while (node != NULL && node->dest != src) {
prev = node;
node = node->next;
}
if (node == NULL) {
return;
}
if (prev == NULL) {
graph->array[dest].head = node->next;
} else {
prev->next = node->next;
}
free(node);
}
// 判断边是否存在
bool isEdge(Graph *graph, int src, int dest) {
AdjListNode *node = graph->array[src].head;
while (node != NULL) {
if (node->dest == dest) {
return true;
}
node = node->next;
}
return false;
}
// 深度优先遍历
void DFS(Graph *graph, bool visited[], int vertex) {
visited[vertex] = true;
printf("%d ", vertex);
AdjListNode *node = graph->array[vertex].head;
while (node != NULL) {
if (!visited[node->dest]) {
DFS(graph, visited, node->dest);
}
node = node->next;
}
}
// 广度优先遍历
void BFS(Graph *graph, bool visited[], int vertex) {
int queue[graph->numVertices], front = 0, rear = 0;
visited[vertex] = true;
queue[rear++] = vertex;
while (front != rear) {
int curVertex = queue[front++];
printf("%d ", curVertex);
AdjListNode *node = graph->array[curVertex].head;
while (node != NULL) {
if (!visited[node->dest]) {
visited[node->dest] = true;
queue[rear++] = node->dest;
}
node = node->next;
}
}
}
// 交互式页面
void interactivePage() {
int numVertices, option, src, dest;
printf("请输入节点数:");
scanf("%d", &numVertices);
Graph *graph = createGraph(numVertices);
bool visited[numVertices];
memset(visited, false, numVertices * sizeof(bool));
do {
printf("请选择操作:\n");
printf("1. 添加边\n");
printf("2. 删除边\n");
printf("3. 判断边是否存在\n");
printf("4. 深度优先遍历\n");
printf("5. 广度优先遍历\n");
printf("6. 退出\n");
scanf("%d", &option);
switch (option) {
case 1:
printf("请输入源节点和目标节点的编号(用空格分隔):");
scanf("%d %d", &src, &dest);
addEdge(graph, src, dest);
break;
case 2:
printf("请输入源节点和目标节点的编号:");
scanf("%d %d", &src, &dest);
removeEdge(graph, src, dest);
break;
case 3:
printf("请输入源节点和目标节点的编号:");
scanf("%d %d", &src, &dest);
printf("边是否存在:%s\n", isEdge(graph, src, dest) ? "是" : "否");
break;
case 4:
printf("深度优先遍历结果为:");
memset(visited, false, numVertices * sizeof(bool));
DFS(graph, visited, 0);
printf("\n");
break;
case 5:
printf("广度优先遍历结果为:");
memset(visited, false, numVertices * sizeof(bool));
BFS(graph, visited, 0);
printf("\n");
break;
case 6:
printf("感谢使用,再见!\n");
break;
default:
printf("输入错误,请重新输入!\n");
break;
}
} while (option != 6);
}
int main() {
interactivePage();
return 0;
}
```
注意,邻接表的实现和邻接矩阵的实现略有不同,需要注意细节。你可以根据自己的需求,修改和完善这个系统,实现更多的功能。
相关推荐
![](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)
![](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)