数据结构图应用实验报告 - C语言实现邻接矩阵、邻接表及遍历算法 - 常规

数据结构图应用实验报告 - C语言实现

实验目的

掌握数据结构图的基本概念和应用。
了解图的存储方式：邻接矩阵和邻接表。
掌握图的遍历算法：深度优先搜索和广度优先搜索。

实验原理

图是一种非线性结构，由顶点和边组成。图的存储方式主要有两种：

邻接矩阵：用二维数组表示图中的顶点和边，数组元素的值表示两个顶点之间是否存在边。
邻接表：用链表来表示图中的顶点和边，每个顶点对应一个链表，链表中的结点存储与该顶点相连的边信息。

图的遍历算法有两种：

深度优先搜索 (DFS)：从一个顶点开始，沿着一条路径一直走到不能再走为止，然后回溯到上一个顶点，再沿着另一条路径继续搜索，直到所有顶点都被访问过。
广度优先搜索 (BFS)：从一个顶点开始，先访问该顶点的所有邻居，然后再访问这些邻居的邻居，以此类推，直到所有顶点都被访问过。

实验内容

用邻接矩阵实现图的存储方式。
用邻接表实现图的存储方式。
实现深度优先搜索算法。
实现广度优先搜索算法。

实验步骤

1. 邻接矩阵实现图的存储方式

#define MAXSIZE 100

typedef struct graph {
    int vertex[MAXSIZE]; //顶点集合
    int edge[MAXSIZE][MAXSIZE]; //邻接矩阵
    int vertexNum, edgeNum; //顶点数和边数
} Graph;

void initGraph(Graph *g) {
    int i, j;
    for(i = 0; i < MAXSIZE; i++) {
        g->vertex[i] = i;
        for(j = 0; j < MAXSIZE; j++) {
            g->edge[i][j] = 0;
        }
    }
    g->vertexNum = 0;
    g->edgeNum = 0;
}

void addEdge(Graph *g, int u, int v) {
    g->edge[u][v] = 1;
    g->edge[v][u] = 1;
    g->edgeNum++;
}

2. 邻接表实现图的存储方式

#define MAXSIZE 100

typedef struct graph {
    int vertex; //顶点
    struct edge *head; //边链表头指针
} Graph;

typedef struct edge {
    int vertex; //边的终点
    struct edge *next; //下一条边的指针
} Edge;

void initGraph(Graph *g) {
    int i;
    for(i = 0; i < MAXSIZE; i++) {
        g[i].vertex = i;
        g[i].head = NULL;
    }
}

void addEdge(Graph *g, int u, int v) {
    Edge *e1, *e2;
    e1 = (Edge *)malloc(sizeof(Edge));
    e1->vertex = v;
    e1->next = g[u].head;
    g[u].head = e1;
    e2 = (Edge *)malloc(sizeof(Edge));
    e2->vertex = u;
    e2->next = g[v].head;
    g[v].head = e2;
}

3. 深度优先搜索算法

void DFS(Graph g, int v, int visited[]) {
    int i;
    visited[v] = 1;
    printf("%d ", v);
    for(i = 0; i < MAXSIZE; i++) {
        if(g.edge[v][i] == 1 && visited[i] == 0) {
            DFS(g, i, visited);
        }
    }
}

4. 广度优先搜索算法

void BFS(Graph g, int v, int visited[]) {
    int queue[MAXSIZE];
    int front = 0, rear = 0;
    int i, u;
    visited[v] = 1;
    printf("%d ", v);
    queue[rear++] = v;
    while(front != rear) {
        u = queue[front++];
        for(i = 0; i < MAXSIZE; i++) {
            if(g.edge[u][i] == 1 && visited[i] == 0) {
                visited[i] = 1;
                printf("%d ", i);
                queue[rear++] = i;
            }
        }
    }
}

实验结果

输入图的顶点数和边数，以及每条边的起点和终点，程序将输出邻接矩阵和邻接表，并分别进行深度优先搜索和广度优先搜索。

实验结论

通过本次实验，我掌握了数据结构图的基本概念和应用，了解了图的存储方式和遍历算法。邻接矩阵和邻接表分别适用于不同的场景，深度优先搜索和广度优先搜索也有各自的优缺点。在实际应用中，应根据具体情况进行选择。