数据结构实验有关邻接矩阵和邻接表的实验总结

好的，我会为您总结有关邻接矩阵和邻接表的数据结构实验。

一、实验目的

本次实验主要目的是掌握图的邻接矩阵和邻接表两种存储方式，以及对图的深度优先搜索和广度优先搜索算法的理解和应用。

二、实验原理

1. 邻接矩阵

邻接矩阵是一种利用矩阵来表示图的方法。设有n个顶点，则用一个n×n的矩阵来表示。其中，若i和j之间有边，则A[i][j]=1；否则A[i][j]=0。

2. 邻接表

邻接表是一种链式存储方式，每个节点存储了与该节点相邻的节点信息。对于每个节点，用一个指针指向一个链表，链表中存储着与该节点相邻的节点。

3. 深度优先搜索

深度优先搜索是一种遍历图的算法，其主要思想是从一个顶点开始，尽可能深地搜索每个分支，直到无法继续为止，然后回溯到前一个节点，继续搜索其他分支。

4. 广度优先搜索

广度优先搜索是一种遍历图的算法，其主要思想是从一个顶点开始，先访问该顶点的所有邻接点，再依次访问这些邻接点的邻接点，直到所有顶点都被访问为止。

三、实验过程

1. 邻接矩阵实现

（1）定义一个结构体来存储图。

#define MAX_VERTEX_NUM 20    //最大顶点数
typedef struct {
    int vexs[MAX_VERTEX_NUM];    //顶点表
    int edges[MAX_VERTEX_NUM][MAX_VERTEX_NUM];    //邻接矩阵
    int n, e;    //顶点数和边数
} MGraph;

（2）初始化图。

void InitMGraph(MGraph* G) {
    int i, j;
    G->n = 0;
    G->e = 0;
    for (i = 0; i < MAX_VERTEX_NUM; i++) {
        for (j = 0; j < MAX_VERTEX_NUM; j++) {
            G->edges[i][j] = 0;
        }
    }
}

（3）创建图。

void CreateMGraph(MGraph* G) {
    int i, j, k, w;
    printf("请输入图的顶点数和边数：\n");
    scanf_s("%d%d", &G->n, &G->e);
    printf("请输入图的顶点信息：\n");
    for (i = 0; i < G->n; i++) {
        scanf_s("%d", &G->vexs[i]);
    }
    for (i = 0; i < G->n; i++) {
        for (j = 0; j < G->n; j++) {
            G->edges[i][j] = 0;
        }
    }
    for (k = 0; k < G->e; k++) {
        printf("请输入边(vi, vj)的下标i，下标j和权值w：\n");
        scanf_s("%d%d%d", &i, &j, &w);
        G->edges[i][j] = w;
        G->edges[j][i] = w;
    }
}

（4）深度优先搜索。

void DFS(MGraph* G, int v, int* visited) {
    int i;
    visited[v] = 1;
    printf("%d ", G->vexs[v]);
    for (i = 0; i < G->n; i++) {
        if (G->edges[v][i] == 1 && visited[i] == 0) {
            DFS(G, i, visited);
        }
    }
}

（5）广度优先搜索。

void BFS(MGraph* G, int v, int* visited) {
    int i, j;
    int queue[MAX_VERTEX_NUM];
    int front = 0, rear = 0;
    printf("%d ", G->vexs[v]);
    visited[v] = 1;
    queue[rear++] = v;
    while (front != rear) {
        i = queue[front++];
        for (j = 0; j < G->n; j++) {
            if (G->edges[i][j] == 1 && visited[j] == 0) {
                printf("%d ", G->vexs[j]);
                visited[j] = 1;
                queue[rear++] = j;
            }
        }
    }
}

2. 邻接表实现

（1）定义一个结构体来存储图。

#define MAX_VERTEX_NUM 20    //最大顶点数
typedef struct EdgeNode {
    int adjvex;    //邻接点在顶点表中的下标
    int weight;    //边的权值
    struct EdgeNode* next;    //下一个邻接点指针
} EdgeNode;

typedef struct VertexNode {
    int data;    //顶点信息
    EdgeNode* first;    //第一个邻接点指针
} VertexNode;

typedef struct {
    VertexNode vexs[MAX_VERTEX_NUM];    //顶点表
    int n, e;    //顶点数和边数
} AdjList;

（2）初始化图。

void InitAdjList(AdjList* G) {
    int i;
    G->n = 0;
    G->e = 0;
    for (i = 0; i < MAX_VERTEX_NUM; i++) {
        G->vexs[i].first = NULL;
    }
}

（3）创建图。

void CreateAdjList(AdjList* G) {
    int i, j, k, w;
    EdgeNode* e;
    printf("请输入图的顶点数和边数：\n");
    scanf_s("%d%d", &G->n, &G->e);
    printf("请输入图的顶点信息：\n");
    for (i = 0; i < G->n; i++) {
        scanf_s("%d", &G->vexs[i].data);
        G->vexs[i].first = NULL;
    }
    for (k = 0; k < G->e; k++) {
        printf("请输入边(vi, vj)的下标i，下标j和权值w：\n");
        scanf_s("%d%d%d", &i, &j, &w);
        e = (EdgeNode*)malloc(sizeof(EdgeNode));
        e->adjvex = j;
        e->weight = w;
        e->next = G->vexs[i].first;
        G->vexs[i].first = e;
        e = (EdgeNode*)malloc(sizeof(EdgeNode));
        e->adjvex = i;
        e->weight = w;
        e->next = G->vexs[j].first;
        G->vexs[j].first = e;
    }
}

（4）深度优先搜索。

void DFS(AdjList* G, int i, int* visited) {
    EdgeNode* e;
    visited[i] = 1;
    printf("%d ", G->vexs[i].data);
    e = G->vexs[i].first;
    while (e) {
        if (visited[e->adjvex] == 0) {
            DFS(G, e->adjvex, visited);
        }
        e = e->next;
    }
}

（5）广度优先搜索。

void BFS(AdjList* G, int v, int* visited) {
    int i, j;
    int queue[MAX_VERTEX_NUM];
    int front = 0, rear = 0;
    EdgeNode* e;
    printf("%d ", G->vexs[v].data);
    visited[v] = 1;
    queue[rear++] = v;
    while (front != rear) {
        i = queue[front++];
        e = G->vexs[i].first;
        while (e) {
            j = e->adjvex;
            if (visited[j] == 0) {
                printf("%d ", G->vexs[j].data);
                visited[j] = 1;
                queue[rear++] = j;
            }
            e = e->next;
        }
    }
}

四、实验结论

通过本次实验，我们可以得出以下结论：

1. 邻接矩阵和邻接表都是常用的图的存储方式，各有优缺点。

2. 深度优先搜索和广度优先搜索是两种常用的遍历图的算法。

3. 邻接矩阵适用于稠密图，邻接表适用于稀疏图。

4. 深度优先搜索和广度优先搜索的时间复杂度都是O(n+e)，其中n为顶点数，e为边数。

5. 深度优先搜索和广度优先搜索的主要区别在于遍历顺序的不同。深度优先搜索是尽可能深地搜索每个分支，而广度优先搜索是先访问该顶点的所有邻接点。