c语言数据结构-图的遍历

简介: c语言数据结构-图的遍历

 (创作不易,感谢有你,你的支持,就是我前行的最大动力,如果看完对你有帮助,请留下您的足迹)目录

定义:

两种遍历方法:

深度优先搜索(DFS):

广度优先搜索(BFS):

定义:

从已给的连通图中某一顶点出发,沿着一些边访遍图中所有的顶点,且使每个顶点仅被访

问一次,就叫做图的遍历

图遍历的实质是找每个顶点的邻接点的过程

                                       

特点:图中可能存在回路 ,且图的任一顶点都可能与其它顶点相通,在访问完某个顶点之后可能会沿着某些边 又回到了曾经访问过的顶点

两种遍历方法:

深度优先搜索(DFS):

仿树的前序遍历过程 (http://t.csdn.cn/zVDgK

如图所示:

1.访问图中某一起始顶点V1,由V1出发,访问它的任一邻接顶点V2

2.再从V2出发,访问与V2邻接但还未被访问过的顶点V3

3.然后再从V3出发,进行类似的访问......

4.如此进行下去,直至到达所有的邻接顶点都被访问过的顶点V5为止

5,接着退回一步,退到前一次刚访问过的顶点,看是否还有其它没有被访问的邻接顶点

如果没有就再退回一步进行搜索,之后再从此顶点出发,进行与前述类似的访问,

如果有则访问此顶点

6.重复上述过程,直到连通图中所有顶点都被访问过为止

/** 保存每个顶点的访问状态[0-未访问;1-已访问 */
int visited[100];
/** 图的类型枚举 */
typedef enum
{
    DG,     //有向图   0
    UDG,    //无向图   1
    DN,     //有向网   2
    UDN     //无向网   3
}GraphKind;
/** 图的邻接矩阵存储表示 */
typedef struct
{
    char* verTexs[100];                     //顶点数组
    int arcs[100][100];                     //邻接矩阵(权数组)
    int verTexCount;                        //图的顶点数
    int arcCount;                           //图的边/弧数
    GraphKind kind;                         //图的类型
}MatrixGraph;
/** 返回某个顶点在顶点集合中的下标(从0开始),不存在返回-1 */
int LocateVex(MatrixGraph* G, char* vex) {
    int index = 0;
    while (index < G->verTexCount) {
        if (strcmp(G->verTexs[index], vex) == 0) {
            break;
        }
        index++;
    }
    return index == G->verTexCount ? -1 : index;
}
/** 深度优先搜索的核心算法,index为深度搜索的某个顶点下标 */
void DFS_AMG(MatrixGraph G, int index) {
    printf(" -> %s", G.verTexs[index]);     //访问当前顶点
    visited[index] = 1;               //更改当前顶点的访问状态
    for (int i = FirstAdjVex_AMG(G, G.verTexs[index]); i;
        i = SecondAdjVex_AMG(G, G.verTexs[index], G.verTexs[i])) {
        if (!visited[i]) {
            DFS_AMG(G, i);  //如果没有访问过,就继续递归调用访问
        }
    }
}
/** 返回顶点vex所在行中的第一个邻接点下标 */
int FirstAdjVex_AMG(MatrixGraph G, char * vex) {
    int i = LocateVex(&G, vex);         //找到顶点vex在顶点数组中的下标
    if (i == -1) return 0;
    int defaultWeight;                  //默认权重
    defaultWeight = G.kind <= 1 ? 0 : INT_MAX;          //图/网
    //搜索图的邻接矩阵中与顶点vex的第一个邻接点下标
    for (int j = i + 1; j < G.verTexCount; j++) {
        if (G.arcs[i][j] != defaultWeight) {
            return j;
        }
    }
    return 0;
}
/** 返回与顶点vex1邻接的另一个邻接点,没有就返回0 */
int SecondAdjVex_AMG(MatrixGraph G, char * vex1, char * vex2) {
    int index1 = LocateVex(&G, vex1);
    int index2 = LocateVex(&G, vex2);
    if (index1 == -1 || index2 == -1) return 0;
    int defaultWeight;
    defaultWeight = G.kind <= 1 ? 0 : INT_MAX;
    for (int i = index2 + 1; i < G.verTexCount; i++) {
        if (G.arcs[index1][i] != defaultWeight) {
            return i;
        }
    }
    return 0;
}
/** 邻接矩阵的深度优先遍历 */
void DFSTraverse_AMG(MatrixGraph G) {
    //初始化状态数组
    for (int i = 0; i < G.verTexCount; i++) {
        visited[i] = 0;     //初始状态设置为未访问
    }
    //DFS遍历
    for (int i = 0; i < G.verTexCount; i++) {
        if (!visited[i]) {//如果某个顶点未访问
            //调用遍历函数
            DFS_AMG(G, i);
        }
    }
}

广度优先搜索(BFS):

广度优先搜索是一种 分层 的搜索过程,每向前走一步可能访问一批顶点,不像深度优先搜索那样有回退的情况。因此,广度优先搜索 不是一个递归的过程

     

如图所示:

1.访问起始点V1

2.依次访问V1的邻接点

3.依次访问这些顶点中未被访问过的邻接点

4.直到所有顶点都被访问过为止

#include"队列.cpp"
/** 保存每个顶点的访问状态[0-未访问;1-已访问 */
int visited[100];
/** 图的类型枚举 */
typedef enum
{
    DG,     //有向图   0
    UDG,    //无向图   1
    DN,     //有向网   2
    UDN     //无向网   3
}GraphKind;
/** 图的邻接矩阵存储表示 */
typedef struct
{
    char* verTexs[100];                     //顶点数组
    int arcs[100][100];                     //邻接矩阵(权数组)
    int verTexCount;                        //图的顶点数
    int arcCount;                           //图的边/弧数
    GraphKind kind;                         //图的类型
}MatrixGraph;
/** 返回某个顶点在顶点集合中的下标(从0开始),不存在返回-1 */
int LocateVex(MatrixGraph* G, char* vex) {
    int index = 0;
    while (index < G->verTexCount) {
        if (strcmp(G->verTexs[index], vex) == 0) {
            break;
        }
        index++;
    }
    return index == G->verTexCount ? -1 : index;
}
/** 返回顶点vex所在行中的第一个邻接点下标 */
int FirstAdjVex_AMG(MatrixGraph G, char* vex) {
    int i = LocateVex(&G, vex);         //找到顶点vex在顶点数组中的下标
    if (i == -1) return 0;
    int defaultWeight;                  //默认权重
    defaultWeight = G.kind <= 1 ? 0 : INT_MAX;          //图/网
    //搜索图的邻接矩阵中与顶点vex的第一个邻接点下标
    for (int j = i + 1; j < G.verTexCount; j++) {
        if (G.arcs[i][j] != defaultWeight) {
            return j;
        }
    }
    return 0;
}
/** 返回与顶点vex1邻接的另一个邻接点,没有就返回0 */
int SecondAdjVex_AMG(MatrixGraph G, char* vex1, char* vex2) {
    int index1 = LocateVex(&G, vex1);
    int index2 = LocateVex(&G, vex2);
    if (index1 == -1 || index2 == -1) return 0;
    int defaultWeight;
    defaultWeight = G.kind <= 1 ? 0 : INT_MAX;
    for (int i = index2 + 1; i < G.verTexCount; i++) {
        if (G.arcs[index1][i] != defaultWeight) {
            return i;
        }
    }
    return 0;
}
/** 广度优先搜索的核心算法 - index为广度优先搜索的某个顶点下标 */
void BFS_AMG(MatrixGraph G, int index) {
    printf(" -> %s", G.verTexs[index]);
    visited[index] = 1;               //设置顶点状态为已访问
    SeqQueue queue;
    initseqqueue(&queue);
    //将当前顶点入队
    OfferSeqQueue(&queue, G.verTexs[index]);
    while (queue.front != queue.rear) {
        //取出队头元素,遍历队头顶点的所有邻接点
        char* vex;                     //取出的队头顶点
        PollSeqQueue(&queue, &vex);
        for (int i = FirstAdjVex_AMG(G, vex); i; i = SecondAdjVex_AMG(G, vex, G.verTexs[i])) {
            if (!visited[i]) {
                printf(" -> %s", G.verTexs[i]);
                visited[i] = 1;        //设置顶点状态为已访问
                OfferSeqQueue(&queue, G.verTexs[i]);
            }
        }
    }
}
/** 邻接矩阵的广度优先遍历 */
void BFSTraverse_AMG(MatrixGraph G) {
    //初始化状态数组
    for (int i = 0; i < G.verTexCount; i++) {
        visited[i] = 0;
    }
    //循环遍历每个顶点
    for (int i = 0; i < G.verTexCount; i++) {
        if (!visited[i]) {
            BFS_AMG(G, i);
        }
    }
}


相关文章
|
12天前
|
算法 数据处理 C语言
C语言中的位运算技巧,涵盖基本概念、应用场景、实用技巧及示例代码,并讨论了位运算的性能优势及其与其他数据结构和算法的结合
本文深入解析了C语言中的位运算技巧,涵盖基本概念、应用场景、实用技巧及示例代码,并讨论了位运算的性能优势及其与其他数据结构和算法的结合,旨在帮助读者掌握这一高效的数据处理方法。
23 1
|
21天前
|
存储 算法 搜索推荐
【趣学C语言和数据结构100例】91-95
本文涵盖多个经典算法问题的C语言实现,包括堆排序、归并排序、从长整型变量中提取偶数位数、工人信息排序及无向图是否为树的判断。通过这些问题,读者可以深入了解排序算法、数据处理方法和图论基础知识,提升编程能力和算法理解。
41 4
|
21天前
|
存储 机器学习/深度学习 搜索推荐
【趣学C语言和数据结构100例】86-90
本文介绍并用C语言实现了五种经典排序算法:直接插入排序、折半插入排序、冒泡排序、快速排序和简单选择排序。每种算法都有其特点和适用场景,如直接插入排序适合小规模或基本有序的数据,快速排序则适用于大规模数据集,具有较高的效率。通过学习这些算法,读者可以加深对数据结构和算法设计的理解,提升解决实际问题的能力。
38 4
|
21天前
|
存储 算法 数据处理
【趣学C语言和数据结构100例】81-85
本文介绍了五个经典算法问题及其C语言实现,涵盖图论与树结构的基础知识。包括使用BFS求解单源最短路径、统计有向图中入度或出度为0的点数、统计无向无权图各顶点的度、折半查找及二叉排序树的查找。这些算法不仅理论意义重大,且在实际应用中极为广泛,有助于提升编程能力和数据结构理解。
35 4
|
21天前
|
算法 数据可视化 数据建模
【趣学C语言和数据结构100例】76-80
本文介绍了五种图论算法的C语言实现,涵盖二叉树的层次遍历及广度优先搜索(BFS)和深度优先搜索(DFS)的邻接表与邻接矩阵实现。层次遍历使用队列按层访问二叉树节点;BFS利用队列从源节点逐层遍历图节点,适用于最短路径等问题;DFS通过递归或栈深入图的分支,适合拓扑排序等场景。这些算法是数据结构和算法学习的基础,对提升编程能力和解决实际问题至关重要。
38 4
|
21天前
|
存储 算法 vr&ar
【趣学C语言和数据结构100例】71-75
本文介绍了五个C语言数据结构问题及其实现,涵盖链表与二叉树操作,包括按奇偶分解链表、交换二叉树左右子树、查找节点的双亲节点、计算二叉树深度及求最大关键值。通过递归和遍历等方法,解决了理论与实际应用中的常见问题,有助于提升编程能力和数据结构理解。
33 4
|
21天前
|
存储 算法 C语言
【趣学C语言和数据结构100例】66-70
本书《趣学C语言和数据结构100例》精选了5个典型的数据结构问题及C语言实现,涵盖链表与数组操作,如有序集合的集合运算、有序序列表的合并、数组中两顺序表位置互换、三递增序列公共元素查找及奇偶数重排。通过详细解析与代码示例,帮助读者深入理解数据结构与算法设计的核心思想,提升编程技能。
32 4
|
13天前
|
存储 缓存 算法
在C语言中,数据结构是构建高效程序的基石。本文探讨了数组、链表、栈、队列、树和图等常见数据结构的特点、应用及实现方式
在C语言中,数据结构是构建高效程序的基石。本文探讨了数组、链表、栈、队列、树和图等常见数据结构的特点、应用及实现方式,强调了合理选择数据结构的重要性,并通过案例分析展示了其在实际项目中的应用,旨在帮助读者提升编程能力。
32 5
|
13天前
|
存储 算法 C语言
C语言中常见的字符串处理技巧,包括字符串的定义、初始化、输入输出、长度计算、比较、查找与替换、拼接、截取、转换、遍历及注意事项
本文深入探讨了C语言中常见的字符串处理技巧,包括字符串的定义、初始化、输入输出、长度计算、比较、查找与替换、拼接、截取、转换、遍历及注意事项,并通过案例分析展示了实际应用,旨在帮助读者提高编程效率和代码质量。
49 4
|
12天前
|
并行计算 算法 测试技术
C语言因高效灵活被广泛应用于软件开发。本文探讨了优化C语言程序性能的策略,涵盖算法优化、代码结构优化、内存管理优化、编译器优化、数据结构优化、并行计算优化及性能测试与分析七个方面
C语言因高效灵活被广泛应用于软件开发。本文探讨了优化C语言程序性能的策略,涵盖算法优化、代码结构优化、内存管理优化、编译器优化、数据结构优化、并行计算优化及性能测试与分析七个方面,旨在通过综合策略提升程序性能,满足实际需求。
36 1