实验九 图的创建与遍历

实验时间： 第11周

实验目的： 掌握图的邻接矩阵、邻接表两种存储结构，能够实现在任意一种存储结构上的创建和遍历两种基本操作

实验要求：

1、认真阅读和掌握教材上和本实验相关内容和算法（见P161~170）。

2、上机将图的任意一种存储表示的创建和遍历（DFS和BFS至少实现一种）算法实现。

3、实现下面实验内容要求的功能，并能够进行简单的输入输出验证。

实验内容：

1、 图的创建部分

编程实现图的任意一种存储表示的创建算法，要求能够进行简单的输入输出验证。

2、 图的遍历操作部分

编程实现图的遍历操作，至少实现图的深度优先搜索和广度优先搜索两种遍历算法中的一种，要求能够进行简单的输入输出验证。

图的创建与遍历（使用邻接矩阵）

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

#define MAX_VERTICES 100

// Representation of Graph using Adjacency Matrix
typedef struct {
    int V; // Number of vertices
    int **matrix; // Adjacency matrix
} GraphAdjMatrix;

GraphAdjMatrix* createGraphAdjMatrix(int vertices) {
    GraphAdjMatrix* graph = (GraphAdjMatrix*)malloc(sizeof(GraphAdjMatrix));
    graph->V = vertices;

    // Allocate memory for adjacency matrix
    graph->matrix = (int**)malloc(vertices * sizeof(int*));
    for (int i = 0; i < vertices; ++i) {
        graph->matrix[i] = (int*)calloc(vertices, sizeof(int));
    }

    return graph;
}

void addEdgeAdjMatrix(GraphAdjMatrix* graph, int src, int dest) {
    // Assuming it's an undirected graph, assigning 1 for both directions
    graph->matrix[src][dest] = 1;
    graph->matrix[dest][src] = 1;
}

void printGraphAdjMatrix(GraphAdjMatrix* graph) {
    printf("Adjacency Matrix:\n");
    for (int i = 0; i < graph->V; ++i) {
        for (int j = 0; j < graph->V; ++j) {
            printf("%d ", graph->matrix[i][j]);
        }
        printf("\n");
    }
}

void freeGraphAdjMatrix(GraphAdjMatrix* graph) {
    for (int i = 0; i < graph->V; ++i) {
        free(graph->matrix[i]);
    }
    free(graph->matrix);
    free(graph);
}

int main() {
    int V = 4; // Number of vertices
    GraphAdjMatrix* g = createGraphAdjMatrix(V);

    addEdgeAdjMatrix(g, 0, 1);
    addEdgeAdjMatrix(g, 0, 2);
    addEdgeAdjMatrix(g, 1, 2);
    addEdgeAdjMatrix(g, 2, 3);

    printGraphAdjMatrix(g);

    freeGraphAdjMatrix(g);

    return 0;
}

结果演示：

图的创建与遍历（使用邻接表）

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

// Node to store adjacent vertices in Adjacency List
typedef struct Node {
    int dest;
    struct Node* next;
} Node;

// Adjacency List representation of Graph
typedef struct {
    int V; // Number of vertices
    Node** array; // Array of adjacency lists
} GraphAdjList;

Node* createNode(int dest) {
    Node* newNode = (Node*)malloc(sizeof(Node));
    newNode->dest = dest;
    newNode->next = NULL;
    return newNode;
}

GraphAdjList* createGraphAdjList(int vertices) {
    GraphAdjList* graph = (GraphAdjList*)malloc(sizeof(GraphAdjList));
    graph->V = vertices;

    // Create an array of adjacency lists
    graph->array = (Node**)malloc(vertices * sizeof(Node*));
    for (int i = 0; i < vertices; ++i) {
        graph->array[i] = NULL;
    }

    return graph;
}

void addEdgeAdjList(GraphAdjList* graph, int src, int dest) {
    // Add edge from src to dest
    Node* newNode = createNode(dest);
    newNode->next = graph->array[src];
    graph->array[src] = newNode;

    // For undirected graph, uncomment the lines below
    /*
    newNode = createNode(src);
    newNode->next = graph->array[dest];
    graph->array[dest] = newNode;
    */
}

void printGraphAdjList(GraphAdjList* graph) {
    printf("Adjacency List:\n");
    for (int i = 0; i < graph->V; ++i) {
        Node* temp = graph->array[i];
        printf("Adjacency list of vertex %d: ", i);
        while (temp != NULL) {
            printf("%d -> ", temp->dest);
            temp = temp->next;
        }
        printf("NULL\n");
    }
}

void freeGraphAdjList(GraphAdjList* graph) {
    for (int i = 0; i < graph->V; ++i) {
        Node* current = graph->array[i];
        while (current != NULL) {
            Node* next = current->next;
            free(current);
            current = next;
        }
    }
    free(graph->array);
    free(graph);
}

int main() {
    int V = 4; // Number of vertices
    GraphAdjList* g = createGraphAdjList(V);

    addEdgeAdjList(g, 0, 1);
    addEdgeAdjList(g, 0, 2);
    addEdgeAdjList(g, 1, 2);
    addEdgeAdjList(g, 2, 3);

    printGraphAdjList(g);

    freeGraphAdjList(g);

    return 0;
}

结果演示：