图的遍历-深度优先遍历与广度优先遍历（C语言）

目录

• 邻接矩阵及邻接表的创建
• 深度优先遍历（DFS）
• • 邻接矩阵的深度优先遍历
  • • 结构定义
    • 邻接矩阵的深度优先遍历操作
    • 邻接矩阵的深度优先递归算法
  • 邻接表的深度优先遍历
  • • 结构定义
    • 邻接表的深度优先遍历操作
    • 邻接表的深度优先递归算法
• 广度优先遍历（BFS）
• • 邻接矩阵的广度遍历
  • • 结构定义
    • 邻接矩阵的广度遍历算法
  • 邻接表的广度优先遍历
  • • 结构定义
    • 邻接表的遍历算法
  • 广度优先遍历所需队列代码

图的遍历
概念：指的是从图中的任一顶点出发，对图中的所有顶点访问一次且只访问一次。

邻接矩阵及邻接表的创建

邻接矩阵及邻接表的创建：
图的存储结构-无向邻接矩阵与无向邻接表（C语言）.

深度优先遍历（DFS）

邻接矩阵的深度优先遍历

结构定义

#include#include#include  //提供_Bool 类型typedef char VertexType;typedef int EdgeType;#define MAXVEX 100#define INFINITY 65535_Bool visited[MAXVEX];//访问标志的数组typedef struct {VertexType vexts[MAXVEX];EdgeType arc[MAXVEX][MAXVEX];int numNodes, numEdges;} MGraph;

邻接矩阵的深度优先遍历操作

/* 邻接矩阵的深度优先遍历操作 */void DFSTraverse(MGraph G){for (int i = 0; i < G.numNodes; i++)//初始化所有顶点状态为未访问visited[i] = false;for (int i = 0; i < G.numNodes; i++)if (!visited[i]) //对未访问邻接顶点递归调用DFS，如果为连通图仅访问一次DFS(G, i);}

邻接矩阵的深度优先递归算法

/* 邻接矩阵的深度优先递归算法 */void DFS(MGraph G, int i){visited[i] = true; //赋值为真printf("%c ", G.vexts[i]);for (int j = 0; j < G.numNodes; j++)if (G.arc[i][j] ！= INFINITY && !visited[j]) //对未访问邻接顶点递归调用DFS(G, j);}

邻接表的深度优先遍历

结构定义

#define _CRT_SECURE_NO_WARNINGS 1#include#include#include typedef char VertexType;//顶点类型typedef int EdgeType;//边上权值#define MAXVEX 100 // 最大顶点数#define MAXVEX 9_Bool visited[MAXVEX];//访问标志的数组typedef struct EdgeNode {//边表结点int adjvex;//领接点域，存储对应下标EdgeType info; //存储权值，如果是非网图可以省略struct EdgeNode* next;//指向下一个邻接点}EdgeNode;typedef struct VertexNode {//顶点结点VertexType data; //顶点域EdgeNode* firstedge;//边表头指针}VertexNode;typedef struct VertexNode AdjList[MAXVEX];//邻接表类型typedef struct {AdjList adjList;int numNodes, numEdges; //图当前顶点数与边数}GraphAdjList;void CreateALGRAph(GraphAdjList*); //建立图的邻接表结构int LocateVex(GraphAdjList, VertexType);//查找顶点void DFSTraverse(GraphAdjList G);void DFS(GraphAdjList, int);//邻接表的深度优先递归算法

邻接表的深度优先遍历操作

/* 邻接表的深度优先遍历操作 */void DFSTraverse(GraphAdjList G){for (int i = 0; i < G.numNodes; i++)//初始化所有顶点状态为未访问visited[i] = false;for (int i = 0; i < G.numNodes; i++)if (!visited[i]) //对未访问邻接顶点递归调用DFS，如果为连通图仅访问一次DFS(G, i);}

邻接表的深度优先递归算法

/* 邻接表的深度优先递归算法 */void DFS(GraphAdjList G, int i){EdgeNode* p;visited[i] = true;printf("%c", G.adjList[i].data);p = G.adjList[i].firstedge;while (p){if (!visited[p->adjvex])//对未访问邻接顶点递归调用DFS(G, p->adjvex);p = p->next;}}

广度优先遍历（BFS）

邻接矩阵的广度遍历

结构定义

#include#include#includetypedef char VertexType;//顶点类型typedef int EdgeType;//边的权值类型#define MAXVEX 100#define INFINITY 65535//表示无穷大#define MAXSIZE 9 //队列最大长度_Bool visited[MAXVEX];//访问标志的数组typedef struct {VertexType vexts[MAXVEX]; //顶点表EdgeType arc[MAXVEX][MAXVEX]; //邻接矩阵int numNodes, numEdges; //图当前顶点数与边数}MGraph;

邻接矩阵的广度遍历算法

/* 邻接矩阵的广度遍历算法 */void BFSTraverse(MGraph G){int i, j;Queue Q;Q.front = Q.rear = 0; //初始化for (i = 0; i < G.numNodes; i++)visited[i] = false;for (i = 0; i < G.numNodes; i++)//对每个顶点做循环{if (!visited[i])//如果未访问过{visited[i] = true;//访问printf("%c ", G.vexts[i]);EnQueue(&Q, i); //入队while (Q.front != Q.rear)//队不为空{DeQueue(&Q, &i); //队首元素出队for (j = 0; j < G.numNodes; j++){if (G.arc[i][j] !=INFINITY && !visited[j]) //此顶点存在且边未访问过{visited[j] = true;printf("%c ", G.vexts[j]);EnQueue(&Q, j);//将此顶点入队}}}}}}

邻接表的广度优先遍历

结构定义

#include#include#includetypedef char VertexType;//顶点类型typedef int EdgeType;//边上权值#define MAXVEX 100 // 最大顶点数#define MAXSIZE 9 //队列最大长度_Bool visited[MAXVEX];//访问标志的数组typedef struct EdgeNode {//边表结点int adjvex;//领接点域，存储对应下标EdgeType info; //存储权值，如果是非网图可以省略struct EdgeNode* next;//指向下一个邻接点}EdgeNode;typedef struct VertexNode {//顶点结点VertexType data; //顶点域EdgeNode* firstedge;//边表头指针}VertexNode;typedef struct VertexNode AdjList[MAXVEX];//邻接表类型typedef struct {AdjList adjList;int numNodes, numEdges; //图当前顶点数与边数}GraphAdjList;

邻接表的遍历算法

/* 邻接表的遍历算法 */void BFSTraverse(GraphAdjList G){int i;EdgeNode* p;Queue Q;Q.front = Q.rear = 0; //初始化for (i = 0; i < G.numNodes; i++)visited[i] = false;for (i = 0; i < G.numNodes; i++)//对每个顶点做循环{if (!visited[i])//如果未访问过{visited[i] = true;//访问printf("%c ", G.adjList[i].data);EnQueue(&Q, i); //入队while (Q.front != Q.rear)//队不为空{DeQueue(&Q, &i);p = G.adjList[i].firstedge;while (p){if (!visited[p->adjvex]){visited[p->adjvex] = true;printf("%c ", G.adjList[p->adjvex].data);EnQueue(&Q, p->adjvex);}p = p->next;}}}}}

广度优先遍历所需队列代码

/* 循环队列顺序储存*/typedef struct {int data[MAXVEX];int front; //头指针int rear; //尾指针，如果队列不空，指向队列尾元素的下一个位置}Queue;/* 入队列 */void EnQueue(Queue* Q, int e){if ((Q->rear + 1) % MAXSIZE == Q->front)//队满exit(-1);Q->data[Q->rear] = e;Q->rear = (Q->rear + 1) % MAXSIZE;}/* 删除头元素，用e返回 */void DeQueue(Queue* Q, int* e){if (Q->front == Q->rear)//如果为空exit(-1);*e = Q->data[Q->front];Q->front = (Q->front + 1) % MAXSIZE;}