• 数据结构实验6 ：图的存储与遍历（邻接矩阵的深度优先遍历DFS和邻接表的广度优先遍历BFS）

    文章目录

    题目一

    题目要求

    利用邻接矩阵存储无向图，并从0号顶点开始进行深度优先遍历。

    输入

    输入第一行是两个整数n1 n2，其中n1表示顶点数（则顶点编号为0至n1-1），n2表示图中的边数。
    之后有n2行输入，每行输入表示一条边，格式是“顶点1 顶点2”，把边插入图中。
    例如：

    4 4
    0 1
    1 3
    0 3
    0 2

    输出

    先输出存储图的邻接矩阵，同一行元素之间空1格，最后一个元素之后不要有空格。
    之后空一行后输出从0号顶点开始的深度优先遍历序列，顶点编号之间空1格。
    例如，对于上面的示例输入，输出为：

    0 1 1 1
    1 0 0 1
    1 0 0 0
    1 1 0 0
    0 1 3 2

    说明

    输入第1个4表示有4个顶点，第2个4表示有4条边。之后的4行输入代表4条边的顶点。输出的前4行为邻接矩阵，之后空一行，然后输出的“0 1 3 2”是深度优先遍历序列。

    代码实现

    邻接矩阵图相关定义：

    typedef int Vertex;
typedef int WeightType;
typedef struct EdgeNode {
    Vertex v1, v2;
}*Edge;
typedef struct MatrixGraphNode {
    int vertexNum; /* 顶点数 */
    int edgeNum; /* 边数 */
    WeightType** adjMatrix; /* 邻接矩阵 */
    int* visited; /* 标记数组，用来标记某一个点是否被访问过，DFS时要用到，也可以把它定义为全局变量，这里为了方便就写在结构体里 */
} *MatrixGraph;

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11

    邻接矩阵图的相关操作：

    这里选择动态创建二维数组，因为不知道测试样例最大顶点数是多少。读者当然可以直接在定义结构体把就把adjMatrix定义为一个足够大的二维数组，而不必如此麻烦的动态创建。

    MatrixGraph createMatrixGraph(int vertexNum) {
    MatrixGraph graph = (MatrixGraph)malloc(sizeof(struct MatrixGraphNode));
    graph->vertexNum = vertexNum;
    graph->edgeNum = 0;
    graph->visited = (int*)malloc(sizeof(int) * graph->vertexNum);
    /* 动态创建二维数组 */
    graph->adjMatrix = (WeightType**)malloc(sizeof(WeightType*) * graph->vertexNum);
    for (int i = 0;i < graph->vertexNum;i++)
        graph->adjMatrix[i] = (WeightType*)malloc(sizeof(WeightType) * graph->vertexNum);
    /* 初始化邻接矩阵adjMatrix和标记数组visited */
    for (int i = 0;i < graph->vertexNum;i++) {
        graph->visited[i] = 0;
        for (int j = 0;j < graph->vertexNum;j++)
            graph->adjMatrix[i][j] = 0;
    }
    return graph;
}
void insertEdge(MatrixGraph graph, Edge edge) {
    graph->adjMatrix[edge->v1][edge->v2] = 1;
    graph->adjMatrix[edge->v2][edge->v1] = 1;
}
MatrixGraph buildMatrixGraph() {
    Edge edge = (Edge)malloc(sizeof(struct EdgeNode));
    int vertexNum;
    scanf("%d", &vertexNum);
    MatrixGraph graph = createMatrixGraph(vertexNum);
    scanf("%d", &graph->edgeNum);
    for (int i = 0;i < graph->edgeNum;i++) {
        scanf("%d%d", &edge->v1, &edge->v2);
        insertEdge(graph, edge);
    }
    return graph;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33

    深度优先搜索DFS和打印邻接矩阵图

    void DFS(MatrixGraph graph, Vertex v) {
	/* 访问当前顶点 */
    printf("%d ", v);
    graph->visited[v] = 1;
    for (int i = 0;i < graph->vertexNum;i++)
    	/* 如果w没有被访问且和v相连，就递归地访问它 */
        if (!graph->visited[i] && isEdge(graph, v, i))
            DFS(graph, i);
}
void printGraph(MatrixGraph graph) {
    for (int i = 0;i < graph->vertexNum;i++)
        for (int j = 0;j < graph->vertexNum;j++)
            j == graph->vertexNum - 1 ? printf("%d\n", graph->adjMatrix[i][j]) : printf("%d ", graph->adjMatrix[i][j]);
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14

    主函数

    int main() {
    MatrixGraph graph = buildMatrixGraph();
    printGraph(graph);
    DFS(graph, 0);
    system("pause");
    return 0;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7

    运行结果

    在这里插入图片描述

    题目二

    题目要求

    利用邻接表存储无向图，并从0号顶点开始进行广度优先遍历。

    输入

    输入第一行是两个整数n1 n2，其中n1表示顶点数（则顶点编号为0至n1-1），n2表示图中的边数。
    之后有n2行输入，每行输入表示一条边，格式是“顶点1 顶点2”，把边插入图中。在链表中插入元素时，在链表头部插入。需要注意，由于是无向图，因此同一条边需要在两条链表中都插入。
    例如：

    4 4
    0 1
    1 3
    0 3
    0 2

    输出

    先按0至n1-1输出存储图的邻接表，每个链表占1行，同一行元素之间空1格，最后一个元素之后不要有空格。先输出顶点编号，之后按链表顺序输出相邻顶点编号。
    之后空一行后输出从0号顶点开始的广度优先遍历序列，顶点编号之间空1格。
    例如，对于上面的示例输入，输出为：

    0 2 3 1
    1 3 0
    2 0
    3 0 1
    0 2 3 1

    说明

    输入第1个4表示有4个顶点，第2个4表示有4条边。之后的4行输入代表4条边的顶点。输出前4行为邻接表中的4个链表，之后空一行，然后输出的“0 2 3 1”是深度优先遍历序列。

    代码实现

    邻接表相关定义

    typedef int Vertex;
/* 边 */
typedef struct EdgeNode {
    Vertex v1, v2;
}*Edge;
/* 邻接点 */
typedef struct AdjVNode {
    Vertex adjVertex;
    struct AdjVNode* next;
}*AdjVNodePtr;
/* 邻接表头节点 */
typedef struct VertexNode {
    AdjVNodePtr firstEdge;
}*AdjList;
/* 邻接表图 */
typedef struct ListGraphNode {
    int vertexNum;
    int edgeNum;
    AdjList adjList;
    int* visited;
}*ListGraph;

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21

    图的相关操作

    ListGraph createListGraph(int vertexNum) {
    ListGraph graph = (ListGraph)malloc(sizeof(struct ListGraphNode));
    graph->vertexNum = vertexNum;
    graph->edgeNum = 0;
    graph->visited = (int*)malloc(sizeof(int));
    graph->adjList = (AdjList)malloc(sizeof(struct VertexNode) * graph->vertexNum);
    /* 初始化邻接表和标记数组 */
    for (int i = 0;i < graph->vertexNum;i++) {
        graph->adjList[i].firstEdge = NULL;
        graph->visited[i] = 0;
    }
    return graph;
}
void insertEdge(ListGraph graph, Edge edge) {
	/* 插入边 */
    AdjVNodePtr newNode = (AdjVNodePtr)malloc(sizeof(struct AdjVNode));
    newNode->adjVertex = edge->v2;
    newNode->next = graph->adjList[edge->v1].firstEdge;
    graph->adjList[edge->v1].firstEdge = newNode;
	/* 插入边 */
    newNode = (AdjVNodePtr)malloc(sizeof(struct AdjVNode));
    newNode->adjVertex = edge->v1;
    newNode->next = graph->adjList[edge->v2].firstEdge;
    graph->adjList[edge->v2].firstEdge = newNode;
}
ListGraph buildListGraph() {
    Edge edge = (Edge)malloc(sizeof(struct EdgeNode));
    int vertexNum;
    scanf("%d", &vertexNum);
    ListGraph graph = createListGraph(vertexNum);
    scanf("%d", &graph->edgeNum);
    for (int i = 0;i < graph->edgeNum;i++) {
        scanf("%d%d", &edge->v1, &edge->v2);
        insertEdge(graph, edge);
    }
    return graph;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37

    深度优先搜索BFS和打印邻接表图

    /* 队列及相关操作 */
typedef struct QueueNode {
    int* data;
    int front, rear;
    int maxSize;
}*Queue;
Queue createQueue(int maxSize) {
    Queue queue = (Queue)malloc(sizeof(struct QueueNode));
    queue->maxSize = maxSize;
    queue->data = (int*)malloc(sizeof(int) * queue->maxSize);
    queue->front = queue->rear = 0;
    return queue;
}
int isFull(Queue queue) {
    return queue->front == (queue->rear + 1) % queue->maxSize;
}
int isEmpty(Queue queue) {
    return queue->front == queue->rear;
}
void addQueue(Queue queue, int data) {
    if (isFull(queue))
        return;
    queue->data[queue->rear] = data;
    queue->rear = (queue->rear + 1) % queue->maxSize;
}
int deleteQueue(Queue queue) {
    if (isEmpty(queue))
        return -1;
    int data = queue->data[queue->front];
    queue->front = (queue->front + 1) % queue->maxSize;
    return data;
}
/* 深度优先搜索 */
void BFS(ListGraph graph, Vertex start) {
    Queue queue = createQueue(graph->vertexNum);
    printf("%d ", start);
    graph->visited[start] = 1;
    addQueue(queue, start);
    Vertex v;
    while (!isEmpty(queue)) {
        v = deleteQueue(queue);
        for (AdjVNodePtr w = graph->adjList[v].firstEdge;w;w = w->next) {
            if (!graph->visited[w->adjVertex]) {
                printf("%d ", w->adjVertex);
                graph->visited[w->adjVertex] = 1;
                addQueue(queue, w->adjVertex);
            }
        }
    }
}
/* 打印图 */
void printGraph(ListGraph graph) {
    for (int i = 0;i < graph->vertexNum;i++) {
        printf("%d ", i);
        for (AdjVNodePtr w = graph->adjList[i].firstEdge;w;w = w->next)
            w->next == NULL ? printf("%d\n", w->adjVertex) : printf("%d ", w->adjVertex);
    }
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54
    • 55
    • 56
    • 57
    • 58

    主函数

    int main() {
    ListGraph graph = buildListGraph();
    printGraph(graph);
    BFS(graph, 0);
    system("pause");
    return 0;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7

    运行结果图

    在这里插入图片描述

  • 相关阅读:
    Java 异常中 e.getMessage() 和 e.toString() e.printStackTrace()的区别&常见的几种异常
    机器学习理论公式推导及原理—决策树
    center loss pytorch实现总结
    合宙Air724UG LuatOS-Air LVGL API控件-加载器(Spinner)
    前端页面JS基础学习Day03
    【嵌入式设计】Main Memory：SPM 便签存储器 | 缓存锁定 | 读取 DRAM 内存 | DREM 猝发（Brust）
    关于分布式一致性
    三子棋小游戏（万字详解）可以自定义棋盘大小
    结构体高级应用（变量位置 大小 位域 共用体）
    【C语言数据结构————————二叉树】
  • 原文地址：https://blog.csdn.net/m0_62283830/article/details/127784780