C/C++ 数据结构与算法【图】 图+邻接矩阵+邻接表+DFS+BFS+最小生成树+最短路径+拓扑排序详细解析【日常学习，考研必备】带图+详细代码

一、图的定义

1）无向图，有向图，完全图

2）稀疏图，稠密图，网，邻接，关联

3）度

4）路径

5）连通图

6）权与网

7）子图

8）连通分量

二、图的类型定义

三、图的存储结构

1）邻接矩阵表示法（数组）

（1）无向图邻接矩阵

（2）有向图邻接矩阵

（3）网的邻接矩阵

（4）邻接矩阵存储表示

1、用两个数组分别存储顶点表和邻接矩阵

#define MVNum 100        //最大顶点数
typedef char VerTexType; //设顶点的数据类型为字符型
typedef int ArcType;     //假设边的权值类型为整型typedef struct{VerTexType vexs[MVNum];      //顶点表ArcType arcs[MVNum][MVNum];   //邻接矩阵int vexnum, arcnum;           //图的当前点数和边数
}AMGraph; // Adjacency Matrix Graph

2、采用邻接矩阵表示法创建无向图

#include <iostream>
#include <climits> // 用于INT_MAX
#include <sstream> // 用于istringstreamusing namespace std;#define MVNum 100        // 最大顶点数
typedef char VerTexType; // 设顶点的数据类型为字符型
typedef int ArcType;     // 假设边的权值类型为整型// 定义状态类型
typedef enum { ERROR, OK } Status;// 图的结构体定义
typedef struct {VerTexType vexs[MVNum];      // 顶点表ArcType arcs[MVNum][MVNum];   // 邻接矩阵int vexnum, arcnum;           // 图的当前顶点数和边数
} AMGraph; // 邻接矩阵图// 查找顶点u的位置，存在则返回顶点表中的下标；否则返回-1
int LocateVex(const AMGraph& G, VerTexType u) {for (int i = 0; i < G.vexnum; ++i) {if (u == G.vexs[i]) {return i;}}return -1;
}// 创建无向网G
Status CreateUDN(AMGraph& G) {cin >> G.vexnum >> G.arcnum; // 输入总顶点数，总边数for (int i = 0; i < G.vexnum; ++i) {cin >> G.vexs[i]; // 依次输入点的信息}// 初始化邻接矩阵for (int i = 0; i < G.vexnum; ++i) {for (int j = 0; j < G.vexnum; ++j) {G.arcs[i][j] = INT_MAX; // 边的权值均置为极大值（无穷大）}}for (int k = 0; k < G.arcnum; ++k) { // 构造邻接矩阵VerTexType v1, v2;ArcType w;cin >> v1 >> v2 >> w; // 输入一条边所依附的顶点及边的权值int i = LocateVex(G, v1); // 确定v1 和 v2在G中的位置int j = LocateVex(G, v2);if (i == -1 || j == -1) return ERROR; // 如果顶点不存在，返回错误G.arcs[i][j] = w; // 边<v1,v2>的权值置为wG.arcs[j][i] = w; // 无向图，对称设置}return OK;
}// 打印图的信息
void PrintGraph(const AMGraph& G) {cout << "图的顶点: ";for (int i = 0; i < G.vexnum; ++i) {cout << G.vexs[i] << ' ';}cout << '\n';cout << "邻接矩阵:\n";for (int i = 0; i < G.vexnum; ++i) {for (int j = 0; j < G.vexnum; ++j) {if (G.arcs[i][j] == INT_MAX) {cout << "INF "; // 表示无穷大}else {cout << G.arcs[i][j] << ' ';}}cout << '\n';}
}int main() {AMGraph G;// 模拟用户输入：3个顶点，3条边// 顶点：A B C// 边：A-B:5 B-C:6 A-C:7istringstream mockInput("3 3\nA B C\nA B 5\nB C 6\nA C 7");// 将mockInput绑定到cin，用于测试streambuf* prevCinBuf = cin.rdbuf(mockInput.rdbuf());if (CreateUDN(G) == OK) {cout << "图创建成功。\n";PrintGraph(G);}else {cerr << "创建图时发生错误。\n";}// 恢复cin至原始状态cin.rdbuf(prevCinBuf);return 0;
}

3、运行结果

4、采用邻接矩阵表示有向图

#include <iostream>
#include <climits> // 用于INT_MAX
#include <sstream> // 用于istringstreamusing namespace std;#define MVNum 100        // 最大顶点数
typedef char VerTexType; // 设顶点的数据类型为字符型
typedef int ArcType;     // 假设边的权值类型为整型// 定义状态类型
typedef enum { ERROR, OK } Status;// 图的结构体定义
typedef struct {VerTexType vexs[MVNum];      // 顶点表ArcType arcs[MVNum][MVNum];   // 邻接矩阵int vexnum, arcnum;           // 图的当前顶点数和边数
} AMGraph; // 邻接矩阵图// 查找顶点u的位置，存在则返回顶点表中的下标；否则返回-1
int LocateVex(const AMGraph& G, VerTexType u) {for (int i = 0; i < G.vexnum; ++i) {if (u == G.vexs[i]) {return i;}}return -1;
}// 创建有向网G
Status CreateDG(AMGraph& G) {cin >> G.vexnum >> G.arcnum; // 输入总顶点数，总边数for (int i = 0; i < G.vexnum; ++i) {cin >> G.vexs[i]; // 依次输入点的信息}// 初始化邻接矩阵for (int i = 0; i < G.vexnum; ++i) {for (int j = 0; j < G.vexnum; ++j) {G.arcs[i][j] = INT_MAX; // 边的权值均置为极大值（无穷大）}}for (int k = 0; k < G.arcnum; ++k) { // 构造邻接矩阵VerTexType v1, v2;ArcType w;cin >> v1 >> v2 >> w; // 输入一条边所依附的顶点及边的权值int i = LocateVex(G, v1); // 确定v1 和 v2在G中的位置int j = LocateVex(G, v2);if (i == -1 || j == -1) return ERROR; // 如果顶点不存在，返回错误G.arcs[i][j] = w; // 有向图，只设置单向边<v1,v2>的权值为w}return OK;
}// 打印图的信息
void PrintGraph(const AMGraph& G) {cout << "图的顶点: ";for (int i = 0; i < G.vexnum; ++i) {cout << G.vexs[i] << ' ';}cout << '\n';cout << "邻接矩阵:\n";for (int i = 0; i < G.vexnum; ++i) {for (int j = 0; j < G.vexnum; ++j) {if (G.arcs[i][j] == INT_MAX) {cout << "INF "; // 表示无穷大}else {cout << G.arcs[i][j] << ' ';}}cout << '\n';}
}int main() {AMGraph G;// 模拟用户输入：3个顶点，3条边// 顶点：A B C// 边：A->B:5 B->C:6 A->C:7istringstream mockInput("3 3\nA B C\nA B 5\nB C 6\nA C 7");// 将mockInput绑定到cin，用于测试streambuf* prevCinBuf = cin.rdbuf(mockInput.rdbuf());if (CreateDG(G) == OK) {cout << "有向图创建成功。\n";PrintGraph(G);}else {cerr << "创建有向图时发生错误。\n";}// 恢复cin至原始状态cin.rdbuf(prevCinBuf);return 0;
}

5、运行结果

邻接矩阵——有什么好处？

• 直观、简单、好理解

• 方便检查任意一对顶点间是否存在边

• 方便找任一顶点的所有“邻接点”（有边直接相连的顶点）

• 方便计算任一顶点的”度“（从该点发出的边数为“出度”，指向该点的边数为“入度”）

  • 无向图：对应行（或列）非0元素的个数

  • 有向图：对应行非0元素的个数是“出度”对应列非0元素的个数是“入度“

邻接矩阵——有什么不好?

1. 不便于增加和删除顶点
2. 浪费空间——存稀疏图（点很多而边很少）有大量无效元素对稠密图（特别是完全图）还是很合算的
3. 浪费时间——统计稀疏图中一共有多少条边

2）邻接表表示法（链式）

（1）无向图邻接表

（2）有向图邻接表

（3）邻接表存储表示

说明**：例如：**AdjList v; **相当于：**VNode v[MVNum];

1、图的结构定义

typedef struct {AdjList vertices;  // vertices--vetex的复数int vexnum,arcnum; // 图的当前顶点数和弧数
} ALGraph;

2、采用邻接表表示法创建无向图

#include <iostream>
#include <sstream> // 用于istringstreamusing namespace std;#define MVNum 100 // 最大顶点数typedef char VerTexType; // 设顶点的数据类型为字符型// 边结点定义
typedef struct ArcNode {int adjvex;              // 该边所指向的顶点的位置struct ArcNode* nextarc; // 指向下一条边的指针
} ArcNode;// 顶点结点定义
typedef struct VNode {VerTexType data;    // 顶点信息ArcNode* firstarc;  // 指向第一条依附该顶点的边的指针
} VNode;// 邻接表类型定义
typedef struct {VNode vertices[MVNum]; // 图的顶点数组int vexnum, arcnum;    // 图的当前顶点数和边数
} ALGraph;// 定义状态类型
typedef enum { ERROR, OK } Status;// 查找顶点u的位置，存在则返回顶点表中的下标；否则返回-1
int LocateVex(const ALGraph& G, VerTexType u) {for (int i = 0; i < G.vexnum; ++i) {if (u == G.vertices[i].data) {return i;}}return -1;
}// 创建无向图G
Status CreateUDG(ALGraph& G) {cin >> G.vexnum >> G.arcnum; // 输入总顶点数，总边数for (int i = 0; i < G.vexnum; ++i) {// 输入各点，构造表头结点表cin >> G.vertices[i].data; // 输入顶点值G.vertices[i].firstarc = NULL; // 初始化表头结点的指针域}for (int k = 0; k < G.arcnum; ++k) {VerTexType v1, v2;cin >> v1 >> v2; // 输入一条边依附的两个顶点int i = LocateVex(G, v1);int j = LocateVex(G, v2);if (i == -1 || j == -1) return ERROR; // 如果顶点不存在，返回错误// 生成新的边结点*p1，并将其插入顶点vi的边表头部ArcNode* p1 = new ArcNode{ j, G.vertices[i].firstarc };G.vertices[i].firstarc = p1;// 生成新的对称边结点*p2，并将其插入顶点vj的边表头部ArcNode* p2 = new ArcNode{ i, G.vertices[j].firstarc };G.vertices[j].firstarc = p2;}return OK;
}// 打印图的信息
void PrintGraph(const ALGraph& G) {cout << "图的顶点: ";for (int i = 0; i < G.vexnum; ++i) {cout << G.vertices[i].data << ' ';}cout << '\n';cout << "邻接表:\n";for (int i = 0; i < G.vexnum; ++i) {cout << G.vertices[i].data << ": ";ArcNode* p = G.vertices[i].firstarc;while (p != NULL) {cout << G.vertices[p->adjvex].data << ' ';p = p->nextarc;}cout << '\n';}
}int main() {ALGraph G;// 模拟用户输入：3个顶点，3条边// 顶点：A B C// 边：A-B A-C B-Cstring input = "3 3\nA B C\nA B\nA C\nB C";istringstream mockInput(input);// 将mockInput绑定到cin，用于测试streambuf* prevCinBuf = cin.rdbuf(mockInput.rdbuf());if (CreateUDG(G) == OK) {cout << "无向图创建成功。\n";PrintGraph(G);} else {cerr << "创建无向图时发生错误。\n";}// 恢复cin至原始状态cin.rdbuf(prevCinBuf);return 0;
}

3、运行结果

4、根据邻接表表示法创建有向图

#include <iostream>
#include <climits> // 用于INT_MAX
#include <sstream> // 用于istringstreamusing namespace std;#define MVNum 100 // 最大顶点数typedef char VerTexType; // 设顶点的数据类型为字符型
typedef int OtherInfo;    // 假设和边相关的信息类型为整型// 边结点定义
typedef struct ArcNode {int adjvex;              // 该边所指向的顶点的位置struct ArcNode* nextarc; // 指向下一条边的指针OtherInfo info;          // 和边相关的信息
} ArcNode;// 顶点结点定义
typedef struct VNode {VerTexType data;   // 顶点信息ArcNode* firstarc; // 指向第一条依附该顶点的边的指针
} VNode;// 邻接表类型定义
typedef struct {VNode vertices[MVNum]; // vertices--vertex的复数int vexnum, arcnum;    // 图的当前顶点数和弧数
} ALGraph;// 定义状态类型
typedef enum { ERROR, OK } Status;// 查找顶点u的位置，存在则返回顶点表中的下标；否则返回-1
int LocateVex(const ALGraph& G, VerTexType u) {for (int i = 0; i < G.vexnum; ++i) {if (u == G.vertices[i].data) {return i;}}return -1;
}// 创建有向图G
Status CreateDG(ALGraph& G) {cin >> G.vexnum >> G.arcnum; // 输入总顶点数，总边数for (int i = 0; i < G.vexnum; ++i) {// 输入各点，构造表头结点表cin >> G.vertices[i].data; // 输入顶点值G.vertices[i].firstarc = NULL; // 初始化表头结点的指针域}for (int k = 0; k < G.arcnum; ++k) {VerTexType v1, v2;cin >> v1 >> v2; // 输入一条边依附的两个顶点int i = LocateVex(G, v1);int j = LocateVex(G, v2);if (i == -1 || j == -1) return ERROR; // 如果顶点不存在，返回错误// 生成一个新的边结点*pArcNode* p = new ArcNode;p->adjvex = j;               // 设置邻接点序号为jp->nextarc = G.vertices[i].firstarc; // 将新结点*p插入顶点vi的边表头部G.vertices[i].firstarc = p;}return OK;
}// 打印图的信息
void PrintGraph(const ALGraph& G) {cout << "图的顶点: ";for (int i = 0; i < G.vexnum; ++i) {cout << G.vertices[i].data << ' ';}cout << '\n';cout << "邻接表:\n";for (int i = 0; i < G.vexnum; ++i) {cout << G.vertices[i].data << ": ";ArcNode* p = G.vertices[i].firstarc;while (p != NULL) {cout << G.vertices[p->adjvex].data << ' ';p = p->nextarc;}cout << '\n';}
}int main() {ALGraph G;// 模拟用户输入：3个顶点，3条边// 顶点：A B C// 边：A->B A->C B->Cstring input = "3 3\nA B C\nA B\nA C\nB C";istringstream mockInput(input);// 将mockInput绑定到cin，用于测试streambuf* prevCinBuf = cin.rdbuf(mockInput.rdbuf());if (CreateDG(G) == OK) {cout << "有向图创建成功。\n";PrintGraph(G);} else {cerr << "创建有向图时发生错误。\n";}// 恢复cin至原始状态cin.rdbuf(prevCinBuf);return 0;
}

5、运行结果

（4）邻接表的特点

3）邻接矩阵与邻接表关系

4）邻接表的改进

（1）十字链表

有向图的十字链表表示

#define MAX_VERTEX_NUM 20
// 定义宏MAX_VERTEX_NUM为20，表示图中最多可以有20个顶点。
// 这是图的最大容量，可以根据需要调整。typedef struct ArcBox
{int tailvex, headvex; // 分别存储边的尾顶点（出发顶点）和头顶点（到达顶点）的索引。struct ArcBox* hlink, * tlink; // hlink指向相同头顶点的下一条边；tlink指向相同尾顶点的下一条边。InfoType* info; // 指向额外信息的指针，如边的权重等。InfoType需要事先定义。
} ArcBox;
// 定义ArcBox结构体，用于表示图中的每一条边（弧）。该结构体包含边的两个端点以及指向入边链表和出边链表中下一个元素的指针。typedef struct VexNode {VertexType data; // 存储顶点的数据，VertexType应该根据实际需求定义。ArcBox* firstin, * firstout; // firstin指向第一个进入此顶点的边；firstout指向从这个顶点出发的第一条边。
} VexNode;
// 定义VexNode结构体，用于表示图中的每一个顶点。该结构体包括顶点数据和指向第一条入边和出边的指针。typedef struct {VexNode xlist[MAX_VERTEX_NUM]; // 定义一个大小为MAX_VERTEX_NUM的VexNode数组，用于存储所有顶点。int vexnum, arcnum; // vexnum存储当前图中顶点的数量，arcnum存储边（弧）的数量。
} OLGraph;
// 定义OLGraph结构体，用于表示整个十字链表形式的有向图。它包含了一个VexNode类型的数组xlist，用以存储图的所有顶点，以及记录顶点数和边数的整型变量。

（2）邻接多重表

无向图的邻接多重表表示

四、图的遍历

图的特点:

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

怎样避免重复访问?

解决思路：设置辅助数组 visited [n ]，用来标记每个被访问过的顶点。

初始状态 visited [i]为0

顶点i被访问，改 visited [i]为1，防止被多次访问

图常用的遍历

深度优先搜索（Depth_First Search——DFS）

广度优先搜索（Breadth_Frist Search——BFS）

1）深度优先遍历DFS

1、介绍

一条路走到黑

方法:

• 在访问图中某一起始顶点v后，由v出发，访问它的任一邻接顶点 w
• 再从 w1 出发，访问与 w1 邻接但还未被访问过的顶点 w2
• 然后再从 w2 出发，进行类似的访问…
• 如此进行下去，直至到达所有的邻接顶点都被访问过的顶点 u 为止
• 接着，退回一步，退到前一次刚访问过的顶点，看是否还有其它没有被访问的邻接顶点
• 如果有，则访问此顶点，之后再从此顶点出发，进行与前述类似的访问
• 如果没有，就再退回一步进行搜索。重复上述过程，直到连通图中所有顶点都被访问过为止

2、算法实现

采用邻接矩阵表示图的深度优先搜索遍历

伪代码：

void DFS(AMGraphG, int v) {// 图G为邻接矩阵类型cout << v;visited[v] = true;    // 访问第v个顶点for (w = 0; w < G.vexnum; w++) {if ((G.arcs[v][w] != 0) && (!visited[w])) {DFS(G, w); //依次检查邻接矩阵v所在的行}}//w是v的邻接点，如果w未访问，则递归调用DFS
}

总代码：

#include <iostream>
using namespace std;// 定义图的最大顶点数量
const int MAX_VERTEX_NUM = 100;// 定义邻接矩阵图的结构体
typedef struct {int arcs[MAX_VERTEX_NUM][MAX_VERTEX_NUM]; // 假设无权图，用0表示没有边，1表示有边int vexnum; // 图中当前顶点个数
} AMGraph;// 全局visited数组，用来记录顶点是否被访问过
bool visited[MAX_VERTEX_NUM];// 深度优先搜索函数
void DFS(AMGraph G, int v) {cout << v << " "; // 输出顶点编号visited[v] = true; // 标记该顶点已被访问for (int w = 0; w < G.vexnum; ++w) { // 遍历与v相邻的所有顶点if (G.arcs[v][w] != 0 && !visited[w]) { // 如果存在边且顶点w未被访问DFS(G, w); // 递归调用DFS访问顶点w}}
}// DFS遍历整个图的辅助函数
void DFSTraverse(AMGraph G) {// 初始化所有顶点为未访问状态for (int i = 0; i < G.vexnum; ++i) {visited[i] = false;}// 可能存在不连通的顶点，因此对每个顶点尝试发起DFSfor (int i = 0; i < G.vexnum; ++i) {if (!visited[i]) { // 如果顶点i未被访问，则从i开始DFSDFS(G, i);}}
}int main() {// 创建一个有5个顶点的图AMGraph G;G.vexnum = 5;// 初始化邻接矩阵为0，表示没有边for (int i = 0; i < MAX_VERTEX_NUM; ++i) {for (int j = 0; j < MAX_VERTEX_NUM; ++j) {G.arcs[i][j] = 0;}}// 添加边到图中，构建一个简单的连通图// 注意：因为是无向图，所以每添加一条边时，需要同时设置两个方向G.arcs[0][1] = G.arcs[1][0] = 1; // 边(0,1)G.arcs[0][2] = G.arcs[2][0] = 1; // 边(0,2)G.arcs[1][3] = G.arcs[3][1] = 1; // 边(1,3)G.arcs[2][4] = G.arcs[4][2] = 1; // 边(2,4)// 输出图的信息cout << "图的邻接矩阵是:" << endl;for (int i = 0; i < G.vexnum; ++i) {for (int j = 0; j < G.vexnum; ++j) {cout << G.arcs[i][j] << " ";}cout << endl;}// 执行深度优先搜索遍历cout << "从顶点0开始的DFS遍历:" << endl;DFSTraverse(G);return 0;
}

运行结果：

采用邻接表表示图的深度优先搜索遍历

伪代码：

void DES_AL(ALGraph G, int v) {// 图G为邻接表类型，从第ν个顶点出发深度优先搜索遍历图Gcout << v;visited[v] = true；//  访问第ν个顶点，并置访问标志数组相应分量值为truep = G.vertices[v].firstarc; // p指向ν的边链表的第一个边节点while (p != NULL) { // 边节点非空w = p->adjvex;  // 表示w是v的邻接点if (!visited[w]) {DFS_AL(G, w); //如果w未访问，则递归调用DES_AL()}p = p->nextarc; // p指向下一个边节点}
}

总代码：

#include <iostream>
using namespace std;// 定义图的最大顶点数量
const int MAX_VERTEX_NUM = 100;// 定义边节点结构体
typedef struct ArcNode {int adjvex; // 该弧所指向的顶点的位置ArcNode* nextarc; // 指向下一条弧的指针
} ArcNode;// 定义顶点结构体
typedef struct VNode {char data; // 顶点信息（这里用字符表示）ArcNode* firstarc; // 指向第一条依附该顶点的弧的指针
} VNode, AdjList[MAX_VERTEX_NUM];// 定义邻接表图结构体
typedef struct {AdjList vertices;int vexnum; // 图中当前顶点个数
} ALGraph;// 全局visited数组，用来记录顶点是否被访问过
bool visited[MAX_VERTEX_NUM];// 创建新的边节点
ArcNode* CreateArcNode(int adjvex) {ArcNode* newNode = new ArcNode();newNode->adjvex = adjvex;newNode->nextarc = NULL;return newNode;
}// 添加边到图中
void AddEdge(ALGraph& G, int v1, int v2) {// 添加从v1到v2的边ArcNode* p = CreateArcNode(v2);p->nextarc = G.vertices[v1].firstarc;G.vertices[v1].firstarc = p;// 因为是无向图，所以也需要添加从v2到v1的边p = CreateArcNode(v1);p->nextarc = G.vertices[v2].firstarc;G.vertices[v2].firstarc = p;
}// 深度优先搜索函数
void DFS_AL(ALGraph G, int v) {cout << v << " "; // 输出顶点编号visited[v] = true; // 标记该顶点已被访问ArcNode* p = G.vertices[v].firstarc; // p指向v的第一个边节点while (p != NULL) { // 遍历与v相邻的所有顶点int w = p->adjvex; // 获取v的邻接点wif (!visited[w]) { // 如果顶点w未被访问，则递归调用DFS_ALDFS_AL(G, w);}p = p->nextarc; // 移动到下一个边节点}
}// DFS遍历整个图的辅助函数
void DFSTraverse(ALGraph G) {// 初始化所有顶点为未访问状态for (int i = 0; i < G.vexnum; ++i) {visited[i] = false;}// 可能存在不连通的顶点，因此对每个顶点尝试发起DFSfor (int i = 0; i < G.vexnum; ++i) {if (!visited[i]) { // 如果顶点i未被访问，则从i开始DFSDFS_AL(G, i);}}
}// 示例主函数
int main() {// 创建一个有5个顶点的图ALGraph G;G.vexnum = 5;// 初始化顶点数据（可以省略这一步，如果不需要显示顶点信息）for (int i = 0; i < G.vexnum; ++i) {G.vertices[i].data = 'A' + i;G.vertices[i].firstarc = NULL; // 初始化为空}// 添加边到图中，构建一个简单的连通图AddEdge(G, 0, 1); // 边(0,1)AddEdge(G, 0, 2); // 边(0,2)AddEdge(G, 1, 3); // 边(1,3)AddEdge(G, 2, 4); // 边(2,4)// 执行深度优先搜索遍历cout << "从顶点0开始的DFS遍历:" << endl;DFSTraverse(G);// 清理动态分配的内存（避免内存泄漏）for (int i = 0; i < G.vexnum; ++i) {ArcNode* current = G.vertices[i].firstarc;while (current != NULL) {ArcNode* next = current->nextarc;delete current;current = next;}}return 0;
}

运行结果：

用邻接矩阵来表示图，遍历图中每一个顶点都要从头扫描该顶m行，时间复杂度为O(n²)，

用邻接表来表示图，虽然有 2e个表结点，但只需扫描e个结点即可完成遍历，加上访问 n个头结点的时间，时间复杂度为O(n+e)。

结论:

• 稠密图适于在邻接矩阵上进行深度遍历。
• 稀疏图适于在邻接表上进行深度遍历。

2）广度优先搜索BFS

优先访问各个结点的邻接点，用队列实现

1、介绍

2、算法实现

伪代码：

void BFS(Graph G, int v) {//按广度优先非递归遍历连通图Gcout << v;visited[v] = true;//访问第v个顶点InitQueue(Q);  //辅助队列Q初始化，置空EnQueue(Q, v); //v进队while (!QueueEmpty(Q)) { // 队列非空DeQueue(Q, u);       // 队头元素出队并置为ufor (w = FirstAdjVex(G, u); w >= 0; w = NextAdjVex(G, u, w)) if (!visited[w]) {cout << w; visited[w] = true; // w为u的尚未访问的邻接顶点EnQueue(Q, w);     // w进队}//if}//while
}//BFS

采用邻接矩阵表示图的广度优先搜索

#include <iostream>
#include <queue>
using namespace std;const int MAX_VERTEX_NUM = 100; // 假设图的最大顶点数
bool visited[MAX_VERTEX_NUM] = { false }; // 访问标记数组
int adjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM]; // 邻接矩阵// 查找顶点u的第一个邻接顶点
int FirstAdjVex(int u) {for (int v = 0; v < MAX_VERTEX_NUM; ++v) {if (adjMatrix[u][v]) return v;}return -1; // 没有邻接顶点返回-1
}// 查找顶点u相对于w的下一个邻接顶点
int NextAdjVex(int u, int w) {for (int v = w + 1; v < MAX_VERTEX_NUM; ++v) {if (adjMatrix[u][v]) return v;}return -1; // 没有下一个邻接顶点返回-1
}void BFS(int v) {queue<int> Q;cout << v << " ";visited[v] = true;Q.push(v);while (!Q.empty()) {int u = Q.front();Q.pop();for (int w = FirstAdjVex(u); w >= 0; w = NextAdjVex(u, w)) {if (!visited[w]) {cout << w << " ";visited[w] = true;Q.push(w);}}}
}int main() {// 初始化一个简单的无向图（例如：A-B-C-D）// 注意：这里假设顶点编号从0开始memset(adjMatrix, 0, sizeof(adjMatrix)); // 初始化邻接矩阵为0adjMatrix[0][1] = adjMatrix[1][0] = 1; // A-BadjMatrix[1][2] = adjMatrix[2][1] = 1; // B-CadjMatrix[2][3] = adjMatrix[3][2] = 1; // C-D// 调用BFS算法cout << "从顶点0开始的BFS遍历: ";BFS(0);cout << endl;return 0;
}

运行结果：

采用邻接表表示图的广度优先搜索遍历

#include <iostream>
#include <queue>
#include <vector>
using namespace std;const int MAX_VERTEX_NUM = 100; // 假设图的最大顶点数
bool visited[MAX_VERTEX_NUM] = { false }; // 访问标记数组
vector<int> adjList[MAX_VERTEX_NUM]; // 邻接表// 邻接表中查找顶点u的第一个邻接顶点
int FirstAdjVex(int u) {if (!adjList[u].empty()) return adjList[u][0];return -1; // 没有邻接顶点返回-1
}// 邻接表中查找顶点u相对于位置idx的下一个邻接顶点
int NextAdjVex(int u, int idx) {if (++idx < adjList[u].size()) return adjList[u][idx];return -1; // 没有下一个邻接顶点返回-1
}void BFS(int v) {queue<int> Q;cout << v << " ";visited[v] = true;Q.push(v);while (!Q.empty()) {int u = Q.front();Q.pop();int w = FirstAdjVex(u), idx = 0;while (w >= 0) {if (!visited[w]) {cout << w << " ";visited[w] = true;Q.push(w);}w = NextAdjVex(u, idx++);}}
}int main() {// 初始化一个简单的无向图（例如：A-B-C-D）// 注意：这里假设顶点编号从0开始adjList[0].push_back(1); // A-BadjList[1].push_back(0);adjList[1].push_back(2); // B-CadjList[2].push_back(1);adjList[2].push_back(3); // C-DadjList[3].push_back(2);// 调用BFS算法cout << "从顶点0开始的BFS遍历: ";BFS(0);cout << endl;return 0;
}

运行结果：

如果使用邻接矩阵，则BFS对于每一个被访问到的顶点，都要循环检测矩阵中的整整一行(n个元素)，总的时间代价为O(n²)

用邻接表来表示图，虽然有 2e 个表结点，但只需扫描e个结点即可完成遍历，加上访问 n个头结点的时间，时间复杂度为O(n+e)。

3）DFS与BFS算法效率比较

空间复杂度相同，都是O(n)（借用了堆栈或队列）

时间复杂度只与存储结构，（邻接矩阵或邻接表）有关，而与搜索路径无关

五、图的应用

1）最小生成树

但是含有 n 个顶点n - 1条边的图不一定是生成树

1、构造最小生成树

2、普利姆（Prim）算法

3、克鲁斯卡尔（Kruskal）算法

2）最短路径问题

1、两点间的最短路径问题

2、某源点到其他各点最短路径

3）两种常见的最短路径问题：

Diikstra(迪杰斯特拉)算法

单源最短路径

算法步骤：

Floyd(弗洛伊德) 算法

所有顶点间的最短路径

方法一：每次以一个顶点为源点，重复执行 Dijkstra 算法 n次。

方法二：弗洛伊德 （Floyd）算法

算法思想：

• 逐个顶点试探
• 从 vi 到 vj 的所有可能存在的路径中
• 选出一条长度最短的路径

4）拓扑排序

有向无环图：无环的有向图，简称 DAG图（Directed Acycline Graph）

有向无环图常用来描述一个工程或系统的进行过程。（通常把计划、施工、生产、程序流程等当成是一个工程）。

一个工程可以分为若干个子工程，只要完成了这些子工程（活动）就可以导致整个工程的完成。

1、AOV 网和AOE 网

AOV 网：拓扑排序
用一个有向图表示一个工程的各子工程及其相互制约的关系，其中以顶点表示活动，弧表示活动之间的优先制约关系，称这种有向图为顶点表示活动的网，简称 AOV网（Activity On Vertex network）。

AOE 网：关键路径
用一个有向图表示一个工程的各子工程及其相互制约的关系，以弧表示活动，以顶点表示活动的开始或结束事件，称这种有向图为边表示活动的网，简称为AOE网（Activity On Edge）。

AOV网特点：

2、拓扑排序介绍

在 AOV 网没有回路的前提下，我们将全部活动排列成一个线性序列，使得若 AOV 网中有弧<i，j>存在，则在这个序列中，i 一定排在 j 的前面，具有这种性质的线性序列称为拓扑有序序列，相应的拓扑有序排序的算法称为拓扑排序。

5）关键路径