编辑代码

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define V 9

// 邻接表节点
typedef struct AdjNode {
    int vertex;
    struct AdjNode* next;
} AdjNode;

// 邻接表头
typedef struct AdjList {
    AdjNode* head;
} AdjList;

// 图结构
typedef struct Graph {
    int numVertices;
    AdjList adjLists[V];
} Graph;

// 创建新节点
AdjNode* newAdjNode(int vertex) {
    AdjNode* node = (AdjNode*)malloc(sizeof(AdjNode));
    node->vertex = vertex;
    node->next = NULL;
    return node;
}

// 创建图
Graph* createGraph() {
    Graph* graph = (Graph*)malloc(sizeof(Graph));
    graph->numVertices = V;
    for (int i = 0; i < V; i++) {
        graph->adjLists[i].head = NULL;
    }
    return graph;
}

// 添加边
void addEdge(Graph* graph, int src, int dest) {
    AdjNode* node = newAdjNode(dest);
    node->next = graph->adjLists[src].head;
    graph->adjLists[src].head = node;

    node = newAdjNode(src);
    node->next = graph->adjLists[dest].head;
    graph->adjLists[dest].head = node;
}

// 邻接表深度优先遍历辅助函数
void DFSUtilAdjList(Graph* graph, int vertex, int* visited) {
    visited[vertex] = 1;
    printf("%c ", vertex + 'A');
    AdjNode* temp = graph->adjLists[vertex].head;
    while (temp) {
        if (!visited[temp->vertex])
            DFSUtilAdjList(graph, temp->vertex, visited);
        temp = temp->next;
    }
}

// 邻接表深度优先遍历
void DFSAdjList(Graph* graph) {
    int visited[V] = {0};
    for (int i = 0; i < V; i++) {
        if (!visited[i])
            DFSUtilAdjList(graph, i, visited);
    }
    printf("\n");
}

// 构建邻接矩阵
void buildAdjMatrix(Graph* graph, int adjMatrix[V][V]) {
    for (int i = 0; i < V; i++) {
        AdjNode* temp = graph->adjLists[i].head;
        while (temp) {
            adjMatrix[i][temp->vertex] = 1;
            temp = temp->next;
        }
    }
}

// 邻接矩阵深度优先遍历辅助函数
void DFSUtilAdjMatrix(int adjMatrix[V][V], int vertex, int* visited) {
    visited[vertex] = 1;
    printf("%c ", vertex + 'A');
    for (int i = 0; i < V; i++) {
        if (adjMatrix[vertex][i] &&!visited[i])
            DFSUtilAdjMatrix(adjMatrix, i, visited);
    }
}

// 邻接矩阵深度优先遍历
void DFSAdjMatrix(int adjMatrix[V][V]) {
    int visited[V] = {0};
    for (int i = 0; i < V; i++) {
        if (!visited[i])
            DFSUtilAdjMatrix(adjMatrix, i, visited);
    }
    printf("\n");
}

// 打印菜单
void printMenu() {
    printf("1. 显示邻接表存储\n");
    printf("2. 显示邻接矩阵存储\n");
    printf("3. 邻接表深度优先遍历\n");
    printf("4. 邻接矩阵深度优先遍历\n");
    printf("5. 退出\n");
}

int main() {
    Graph* graph = createGraph();
    addEdge(graph, 0, 1);
    addEdge(graph, 0, 2);
    addEdge(graph, 1, 2);
    addEdge(graph, 1, 3);
    addEdge(graph, 1, 4);
    addEdge(graph, 2, 5);
    addEdge(graph, 3, 4);
    addEdge(graph, 3, 6);
    addEdge(graph, 4, 6);
    addEdge(graph, 5, 6);
    addEdge(graph, 7, 8);
    addEdge(graph, 8, 7);

    int choice;
    int adjMatrix[V][V] = {0};
    buildAdjMatrix(graph, adjMatrix);

    while (1) {
        printMenu();
        printf("请输入你的选择: ");
        scanf("%d", &choice);
        while (getchar() != '\n');

        switch (choice) {
            case 1:
                for (int i = 0; i < V; i++) {
                    printf("%c: ", i + 'A');
                    AdjNode* temp = graph->adjLists[i].head;
                    while (temp) {
                        printf("%c ", temp->vertex + 'A');
                        temp = temp->next;
                    }
                    printf("\n");
                }
                break;
            case 2:
                for (int i = 0; i < V; i++) {
                    for (int j = 0; j < V; j++) {
                        printf("%d ", adjMatrix[i][j]);
                    }
                    printf("\n");
                }
                break;
            case 3:
                DFSAdjList(graph);
                break;
            case 4:
                DFSAdjMatrix(adjMatrix);
                break;
            case 5:
                for (int i = 0; i < V; i++) {
                    AdjNode* temp = graph->adjLists[i].head;
                    AdjNode* next;
                    while (temp) {
                        next = temp->next;
                        free(temp);
                        temp = next;
                    }
                }
                free(graph);
                exit(0);
            default:
                printf("无效的选择，请重新输入。\n");
        }
    }

    return 0;
}