数据结构_图的遍历
图的遍历
深度优先遍历
遍历思想
Depth First Search (DFS)遍历类似于树的先序遍历，是树的先序遍历的推广。
过程：
- 选择一个顶点，访问顶点
- 选择刚访问顶点的第一个未被访问的邻接点，访问该点。以该点为顶点继续访问第一个未被访问的邻接点，直到没有未被访问的邻接点为止。
- 回溯上一个顶点，选择下一个未被访问的邻接点。
重复2，3.
代码
由于不同存储结构的图对于遍历实现有细微差别，本处以邻接矩阵和邻接表为例实现。邻接矩阵、邻接表思想、头文件代码和其他存储方式实现可以参考本专栏图知识———数据结构_图
- 邻接矩阵的深度遍历函数
//该顶点的第一个邻接点开始，找寻第一个邻接点的邻接点
void DFS_AM(G_Amatreix &g, int v) {
printf("%c", g.V[v]);
visited[v] = true;
for (int i = 0; i < g.n; ++i) {
if (g.E[v][i] != Maxint && !visited[i])
DFS_AM(g, i);
}
}
//依次对n个顶点遍历邻接点（对不同的连通分量进行遍历）
void DFSTraverse(G_Amatreix g) {
for (int i = 0; i < g.n; ++i)
visited[i] = false;
for (int i = 0; i < g.n; ++i) {
if (!visited[i])
DFS_AM(g, i);
}
}
- 邻接表的深度遍历函数
//该顶点的第一个邻接点开始，找寻第一个邻接点的邻接点
void DFS_AL(GAlist& g, int v) {
printf("%c", g.list[v].v);
visited[v] = true;
Ep p = g.list[v].fristE;
while(p){
if (!visited[p->vnum])
DFS_AL(g, p->vnum);
p = p->Enext;
}
}
//依次对n个顶点遍历邻接点（对不同的连通分量进行遍历）
void DFSTraverse1(GAlist g) {
for (int i = 0; i < g.n; ++i)
visited[i] = false;
for (int i = 0; i < g.n; ++i) {
if (!visited[i])
DFS_AL(g, i);
}
}
广度优先遍历
遍历思想
Breadth First Search (BFS)遍历类似于树的层次遍历的过程。
过程：
- 选择一个顶点，访问顶点
- 以此访问顶点的未被访问的邻接点。直到没有未被访问的邻接点为止。
- 从第一个被访问的邻接点开始，依次访问它们的邻接点，直到所有已被访问的邻接点访问完。
重复3
代码
图广度优先遍历和树的层次遍历一样需要借助一个先进先出的数据结构，本文采用队列，具体实现可以参考本专栏——数据结构_栈和队列
- 邻接矩阵的广度遍历函数
/// =========================================================
/// 邻接矩阵BFS实现
/// =========================================================
//该顶点的第一个邻接点开始，遍历所有邻接点
void BFS_AM(G_Amatreix& g,int v) {
Lkqueue Q;
QueueInit(Q);
item e = { v };
QueueEn(Q, e); //将第一个顶点入队列
printf("%c", g.V[v]);
visited[v] = true;
while (Q.front != Q.rear) { //队列不为空时，将队列中的顶点取出并将它的邻接点全部入队列
item e1;
QueueOut(Q, e1);
int j = e1.data;
for (int i = 0; i < g.n; ++i) {
if (g.E[j][i] != Maxint && !visited[i]) {
item e2 = { i };
QueueEn(Q, e2);
printf("%c", g.V[i]);
visited[i] = true;
}
}
}
}
//依次对n个顶点遍历邻接点（对不同的连通分量进行遍历）
void BFSTraverse(G_Amatreix g) {
for (int i = 0; i < g.n; ++i)
visited[i] = false;
for (int i = 0; i < g.n; ++i) {
if (!visited[i])
BFS_AM(g, i);
}
}
- 邻接表的广度遍历函数
/// =========================================================
/// 邻接表BFS实现
/// =========================================================
//该顶点的第一个邻接点开始，遍历所有邻接点
void BFS_AM(GAlist& g, int v) {
Lkqueue Q;
QueueInit(Q);
item e = { v };
QueueEn(Q, e); //将第一个顶点入队列
printf("%c", g.list[v].v);
visited[v] = true;
while (Q.front != Q.rear) { //队列不为空时，将队列中的顶点取出并将它的邻接点全部入队列
item e1;
QueueOut(Q, e1);
int j = e1.data;
Ep p = g.list[j].fristE;
while (p) {
if (!visited[p->vnum]) {
item e2 = { p->vnum };
QueueEn(Q, e2);
printf("%c", g.list[p->vnum].v);
visited[p->vnum] = true;
}
p = p->Enext;
}
}
Queuefree(Q);
}
//依次对n个顶点遍历邻接点（对不同的连通分量进行遍历）
void BFSTraverse1(GAlist g) {
for (int i = 0; i < g.n; ++i)
visited[i] = false;
for (int i = 0; i < g.n; ++i) {
if (!visited[i])
BFS_AM(g, i);
}
}
完整代码和测试
代码
所需头文件
- Lkqueue.h
///Lkqueue.h
#pragma once
#include<stdbool.h>
#include<stdio.h>
#ifndef Itemtype
#define Itemtype int
#endif // !Itemtype
//栈数据元素（更改数据元素，修改基本元素结构体和接口的实现即可）
typedef struct item {
//数据项
Itemtype data;
bool operator==(const item& a) {
return data == a.data;
}
}Item;
typedef struct Queue{
Item e;
struct Queue* next;
}*Lqueue;
struct Lkqueue {
Lqueue rear;
Lqueue front;
};
//初始化
bool QueueInit(Lkqueue& q);
//入队
bool QueueEn(Lkqueue& q, Item e);
//出队
bool QueueOut(Lkqueue& q, Item& e);
//取头元素
bool GetItem(const Lkqueue q, Item& e);
- GAmatrix.h
///GAmatrix.h
#pragma once
#include<stdio.h>
#define Maxint 32767
#ifndef MAX
#define MAX 20
#endif // MAX
typedef char VertexType;
typedef int Edgetype;
typedef struct {
VertexType V[MAX];
Edgetype E[MAX][MAX];
int n, e;
}G_Amatreix;
//创建图
void CreateG(G_Amatreix& g);
//找到顶点在顶点集中的标号
int LocateV(G_Amatreix g, VertexType v);
- GAlist.h
///GAlist.h
#pragma once
#include<stdio.h>
#ifndef MAX
#define MAX 20
#endif // MAX
typedef char VertexType;
typedef int Edgetype;
typedef struct Enode{
int vnum;
Edgetype info;
struct Enode* Enext;
}ENode,*Ep;
typedef struct Vnode{
VertexType v;
Ep fristE;
}VNode,Alist[MAX];
struct GAlist {
Alist list;
int n, e;
};
//创建图
void CreateG(GAlist& g);
//找到顶点在顶点集中的标号
int LocateV(GAlist g, VertexType v);
//释放边结点
void freeG(GAlist& g);
实现和测试文件
#include<stdio.h>
#include"GAmatrix.h" //定义图的邻接矩阵
#include"GAlist.h" //定义图的邻接表
#define Itemtype int //定义栈的存储类型
#include"Lkqueue.h"
bool visited[MAX]; //标记数组
/// ========================================================
/// 邻接矩阵接口实现
/// ========================================================
//创建图
void CreateG(G_Amatreix& g) {
printf("input n , e:\n");
scanf_s("%d,%d", &g.n, &g.e);
getchar();
//初始化V
for (int i = 0; i < g.n; ++i) {
printf("input V[%d]:", i);
scanf_s("%c", &g.V[i], 1);
char ch = getchar();
while (ch != '\n')
ch = getchar();
}
//初始化E
for (int i = 0; i < g.n; ++i) {
for (int j = 0; j < g.n; ++j) {
g.E[i][j] = Maxint; //创立网是为无穷大，图时为0
}
}
//输入边
char v1 = 0, v2 = 0;
int m = 0;;
int j, k;
for (int i = 0; i < g.e; ++i) {
printf("input the edge:(v1 v2 w)\n");
scanf_s("%c %c %d", &v1, 1, &v2, 1, &m);
char ch = getchar();
while (ch != '\n')
ch = getchar();
j = LocateV(g, v1);
k = LocateV(g, v2);
g.E[j][k] = m; //创立网时为权值w,图时为1
g.E[k][j] = g.E[j][k]; //无向时为对称矩阵
}
//输出边
/*for (int i = 0; i < g.n; ++i) {
printf("顶点%c:\n", g.V[i]);
for (int j = 0; j < g.n; ++j) {
if (g.E[i][j] != Maxint)
printf("边为<%c,%c>,权值为%d:\n", g.V[i], g.V[j], g.E[i][j]);
}
}*/
}
//找到顶点在顶点集中的标号
int LocateV(G_Amatreix g, VertexType v) {
int j = 0;
for (; j < g.n; ++j) {
if (g.V[j] == v)
return j;
}
return j;
}
/// ========================================================
/// 邻接表图接口实现
/// ========================================================
//创建图
void CreateG(GAlist& g) {
printf("input n , e:\n");
scanf_s("%d,%d", &g.n, &g.e);
getchar();
//初始化Alist
for (int i = 0; i < g.n; ++i) {
printf("input V[%d]:", i);
scanf_s("%c", &g.list[i].v, 1);
g.list[i].fristE = NULL;
char ch = getchar();
while (ch != '\n')
ch = getchar();
}
//输入边
char v1 = 0, v2 = 0;
int m = 0;
int j, k;
for (int i = 0; i < g.e; ++i) {
printf("input the edge:(v1 v2 w)\n");
scanf_s("%c %c %d", &v1, 1, &v2, 1, &m);
char ch = getchar();
while (ch != '\n')
ch = getchar();
j = LocateV(g, v1);
k = LocateV(g, v2);
//生成边结点
Ep p = new ENode;
p->vnum = k;
p->info = m;
p->Enext = g.list[j].fristE;
g.list[j].fristE = p;
//对称结点的边结点生成
Ep p2 = new ENode;
p2->vnum = j;
p2->info = m;
p2->Enext = g.list[k].fristE;
g.list[k].fristE = p2;
}
//输出边
/*for (int i = 0; i < g.n; ++i) {
printf("顶点%c:\n", g.list[i].v);
Ep p = g.list[i].fristE;
if (!p)
printf("null");
while (p) {
int j;
Ep q = p->Enext;
j = p->vnum;
printf("边为<%c,%c>,权值为%d:\n", g.list[i].v, g.list[j].v, p->info);
p = q;
}
}*/
}
//找到顶点在顶点集中的标号
int LocateV(GAlist g, VertexType v) {
int j = 0;
for (; j < g.n; ++j) {
if (g.list[j].v == v)
return j;
}
return j;
}
//释放边结点
void freeG(GAlist& g) {
for (int i = 0; i < g.n; ++i) {
Ep p = g.list[i].fristE;
while (p) {
Ep q = p->Enext;
delete p;
p = q;
}
}
}
/// ========================================================
///链式队列接口实现
/// ========================================================
//初始化
bool QueueInit(Lkqueue& q) {
q.front = q.rear = new Queue;
q.front->next = NULL;
return true;
}
//入队
bool QueueEn(Lkqueue& q, Item e) {
q.rear->e = e;
Lqueue p = new Queue;
p->next = NULL;
q.rear->next = p;
q.rear = p;
return true;
}
//出队
bool QueueOut(Lkqueue& q, Item& e) {
if (q.front == q.rear) {
printf("false\n");
return false;
}
e = q.front->e;
Lqueue q1 = q.front;
q.front = q.front->next;
delete q1;
}
//取头元素
bool GetItem(const Lkqueue q, Item& e) {
if (q.front == q.rear)
return false;
e = q.front->e;
return true;
}
//free
void Queuefree(Lkqueue& q) {
while (q.front) {
Lqueue q1 = q.front;
q.front = q.front->next;
delete q1;
}
if (!q.front)
printf("\nfreed\n");
}
/// =========================================================
/// 邻接矩阵DFS实现
/// =========================================================
//该顶点的第一个邻接点开始，找寻第一个邻接点的邻接点
void DFS_AM(G_Amatreix& g, int v) {
printf("%c", g.V[v]);
visited[v] = true;
for (int i = 0; i < g.n; ++i) {
if (g.E[v][i] != Maxint && !visited[i])
DFS_AM(g, i);
}
}
//依次对n个顶点遍历邻接点（对不同的连通分量进行遍历）
void DFSTraverse(G_Amatreix g) {
for (int i = 0; i < g.n; ++i)
visited[i] = false;
for (int i = 0; i < g.n; ++i) {
if (!visited[i])
DFS_AM(g, i);
}
}
/// =========================================================
/// 邻接表DFS实现
/// =========================================================
///
//该顶点的第一个邻接点开始，找寻第一个邻接点的邻接点
void DFS_AL(GAlist& g, int v) {
printf("%c", g.list[v].v);
visited[v] = true;
Ep p = g.list[v].fristE;
while(p){
if (!visited[p->vnum])
DFS_AL(g, p->vnum);
p = p->Enext;
}
}
//依次对n个顶点遍历邻接点（对不同的连通分量进行遍历）
void DFSTraverse1(GAlist g) {
for (int i = 0; i < g.n; ++i)
visited[i] = false;
for (int i = 0; i < g.n; ++i) {
if (!visited[i])
DFS_AL(g, i);
}
}
/// =========================================================
/// 邻接矩阵BFS实现
/// =========================================================
//该顶点的第一个邻接点开始，遍历所有邻接点
void BFS_AM(G_Amatreix& g,int v) {
Lkqueue Q;
QueueInit(Q);
item e = { v };
QueueEn(Q, e);
printf("%c", g.V[v]);
visited[v] = true;
while (Q.front != Q.rear) {
item e1;
QueueOut(Q, e1);
int j = e1.data;
for (int i = 0; i < g.n; ++i) {
if (g.E[j][i] != Maxint && !visited[i]) {
item e2 = { i };
QueueEn(Q, e2);
printf("%c", g.V[i]);
visited[i] = true;
}
}
}
}
//依次对n个顶点遍历邻接点（对不同的连通分量进行遍历）
void BFSTraverse(G_Amatreix g) {
for (int i = 0; i < g.n; ++i)
visited[i] = false;
for (int i = 0; i < g.n; ++i) {
if (!visited[i])
BFS_AM(g, i);
}
}
/// =========================================================
/// 邻接表BFS实现
/// =========================================================
//该顶点的第一个邻接点开始，遍历所有邻接点
void BFS_AM(GAlist& g, int v) {
Lkqueue Q;
QueueInit(Q);
item e = { v };
QueueEn(Q, e);
printf("%c", g.list[v].v);
visited[v] = true;
while (Q.front != Q.rear) {
item e1;
QueueOut(Q, e1);
int j = e1.data;
Ep p = g.list[j].fristE;
while (p) {
if (!visited[p->vnum]) {
item e2 = { p->vnum };
QueueEn(Q, e2);
printf("%c", g.list[p->vnum].v);
visited[p->vnum] = true;
}
p = p->Enext;
}
}
Queuefree(Q);
}
//依次对n个顶点遍历邻接点（对不同的连通分量进行遍历）
void BFSTraverse1(GAlist g) {
for (int i = 0; i < g.n; ++i)
visited[i] = false;
for (int i = 0; i < g.n; ++i) {
if (!visited[i])
BFS_AM(g, i);
}
}
int main(int argc, char* argv[]) {
//邻接矩阵
G_Amatreix g;
CreateG(g);
printf("\nmatrix DFS:\n");
DFSTraverse(g);
printf("\nmatrix BFS:\n");
BFSTraverse(g);
//邻接表
/*GAlist g1;
CreateG(g1);
printf("\nlist DFS:\n");
DFSTraverse1(g1);
printf("\nlist BFS:\n");
BFSTraverse1(g1);
freeG(g1);*/
return 0;
}
测试：
邻接表矩阵的测试
邻接表的测试
测试的结果的顺序和邻接表的存储结构的实现有关，本文的邻接表的实现采取的是前插结点，所以遍历顺序正好从右到左。