本文将先介绍图的存储方式：邻接矩阵和邻接表，接着介绍图的基本算法：广度优先搜索和深度优先搜索。
图是一种非线性的数据结构。在图论中，图是一种数学结构，用来表示一组对象，这些对象之间有一些成对的关系。对象可以包含任意信息，例如单个值、某段代码或公司员工的姓名，具体取决于图的用途。
这里我们尽可能简单地用一个字母标识每个对象，将图中对象称为顶点(vertices)，对象间关系称为边(edges)。使用 G = ( V , E ) G = (V,E) G=(V,E) 描述顶点V 和边E 的集合，顶点V 的个数为 n = ∣ V ∣ n = |V| n=∣V∣，边的个数 m = ∣ E ∣ m = |E| m=∣E∣。
边用于描述顶点的移动，这种移动称为路径，边可以是有方向的，也可以是无方向的。也就是说，通过多个顶点到顶点的边，可能从顶点y到达顶点v。图中y到v的路径可以记为：
y
∗
→
G
v
_y \ \underrightarrow{*}_G\ {_v}
y
∗G v 。图可以有一个根节点r，表示图的起点，这时候图记为
G
=
(
V
,
E
,
r
)
G=(V,E,r)
G=(V,E,r)。
一般会使用邻接矩阵（Adjacency Matrix）和邻接表（Adjacency List）两种方式存储图。
这里直接使用算法导论上的原图。邻接矩阵和连接表的优缺点也非常明显。邻接矩阵的优点是比较直观，两个顶点的关系比较容易计算，缺点是比较浪费存储空间，尤其对于稀疏图。而邻接表的优点是比较节省存储空间，而缺点是两个顶点的关系计算相对比较困难一些。实际应用需要根据场景和需求选择合适的存储方式。
邻接矩阵存储的参考代码：
#define MaxVertexNum 10
typedef char VertexType;
typedef int EdgeType;
typedef struct
{
VertexType vertex[MaxVertexNum];
EdgeType edge[MaxVertexNum][MaxVertexNum];
int vexnum, edgenum;
} AdjMatGraph;
邻接表参考代码：
#define MaxVertexNum 100
typedef char VertexType;
typedef int EdgeType;
typedef struct Edge{
int adjvex; //边指向的顶点的位下标
EdgeType weight; //权值
struct Edge *next; //指向下一个邻接点
}Edge;
typedef struct Vertex{
VertexType value; //顶点信息
Edge *firstedge; //边指针
}Vertex, AdjList[MaxVertexNum];
typedef struct{
AdjList adjList;
int vexnum, edgenum;
}AdjListGraph;
如果你的图没有权值，顶点信息比较简单，也可以直接使用 C++ 的 vector 表示：
std::vector<std::vector<int>> graph;
广度优先搜索（BFS：Breadth-first search）是从源节点到达所有节点，并且从已发现节点搜索未发现节点的时候，始终是从已发现节点的广度方向展开，这优点类似树的层次遍历。BFS 算法生成以源节点 s 到达所有节点 v 的一棵广度优先搜索树。
借助队列，BFS 算法流程如上图所示。以邻接表存储为例，给出 BFS 的算法：
bool visited[MaxVertexNum];
void BFS(const AdjListGraph& g) {
for (int i = 0; i < g.vexnum; i++) {
visited[i] = false;
}
queue<int> q;
for (int i = 0; i < g.vexnum; i++) { // 防止存在非联通子图
if (!visited[i]) {
visited[i] = true;
// visit
cout << g.adjList[i].value;
q.push(i);
while (!q.empty()) {
int u = q.front();
q.pop();
for (Edge* edge = g.adjList[u].firstedge; edge != nullptr; edge = edge->next) {
if (!visited[edge->adjvex]) {
// visit
cout << g.adjList[edge->adjvex].value;
visited[edge->adjvex] = true;
q.push(edge->adjvex);
}
}
}
}
}
cout << endl;
}
深度优先搜索（DFS：Depth-first search）尽可能深地搜索一个图。首先访问其实一个起始节点 v，然后访问 v 的一个邻接节点 w， 接着 w 的邻接节点。重复上述过程，当无法继续访问时，则回退到最近访问的节点，继续上述过程，直到所有节点都被访问过。
DFS 算法的递归方式比较简单：
bool visited[MaxVertexNum];
void dfs(const AdjListGraph& g, int u) {
// visit
cout << g.adjList[u].value;
visited[u] = true;
for (Edge* edge = g.adjList[u].firstedge; edge != nullptr; edge = edge->next) {
if (!visited[edge->adjvex]) {
dfs(g, edge->adjvex);
}
}
}
void DFS(const AdjListGraph& g) {
for (int i = 0; i < g.vexnum; i++) {
visited[i] = false;
}
for (int i = 0; i < g.vexnum; i++) { // 防止存在非联通子图
if (!visited[i]) {
dfs(g, i);
}
}
}
最后，附上本文源码，方便大家验证。
#include<iostream>
#include<queue>
#include<memory>
using namespace std;
#define MaxVertexNum 100
typedef char VertexType;
typedef int EdgeType;
typedef struct Edge{
int adjvex; //边指向的顶点的位下标
// EdgeType weight; //权值
struct Edge *next; //指向下一个邻接点
}Edge;
typedef struct Vertex{
VertexType value; //顶点信息
Edge *firstedge; //边指针
}Vertex, AdjList[MaxVertexNum];
typedef struct{
AdjList adjList;
int vexnum, edgenum;
}AdjListGraph;
// lookup index of vertex u in the graph
int LocateVex(const AdjListGraph& g, VertexType u)
{
int i;
for(i = 0; i < g.vexnum; ++i)
if(u == g.adjList[i].value)
{
return i;
}
return -1;
}
void printGraph(const AdjListGraph& g)
{
for(int i = 0; i < g.vexnum; i++)
{
cout << g.adjList[i].value;
Edge* edge = g.adjList[i].firstedge;
while(edge != nullptr)
{
cout << "->" << g.adjList[edge->adjvex].value;
edge = edge->next;
}
cout << endl;
}
}
void deleteGraph(AdjListGraph& g) {
// TODO
}
void createGraph(AdjListGraph &g) {
cout << "Enter vertex num: ";
cin >> g.vexnum;
cout << "Enter edge num: ";
cin >> g.edgenum;
cout << "Enter " << g.vexnum << " vertex value: ";
for (int i = 0; i < g.vexnum; i++) {
cin >> g.adjList[i].value;
g.adjList[i].firstedge = nullptr;
}
cout << "Enter" << g.edgenum << " edge info:" << endl;
for (int e = 0; e < g.edgenum; e++) {
VertexType v1, v2;
cin >> v1 >> v2;
int i = LocateVex(g, v1);
int j = LocateVex(g, v2);
if (i == -1 || j == -1) {
cout << "Error edge info" << endl;
}
Edge* e1 = new Edge();
e1->adjvex = j;
e1->next = g.adjList[i].firstedge;
g.adjList[i].firstedge = e1;
Edge* e2 = new Edge();
e2->adjvex = i;
e2->next = g.adjList[j].firstedge;
g.adjList[j].firstedge = e2;
}
}
bool visited[MaxVertexNum];
void BFS(const AdjListGraph& g) {
for (int i = 0; i < g.vexnum; i++) {
visited[i] = false;
}
queue<int> q;
for (int i = 0; i < g.vexnum; i++) {
if (!visited[i]) {
visited[i] = true;
// visit
cout << g.adjList[i].value;
q.push(i);
while (!q.empty()) {
int u = q.front();
q.pop();
for (Edge* edge = g.adjList[u].firstedge; edge != nullptr; edge = edge->next) {
if (!visited[edge->adjvex]) {
// visit
cout << g.adjList[edge->adjvex].value;
visited[edge->adjvex] = true;
q.push(edge->adjvex);
}
}
}
}
}
cout << endl;
}
void dfs(const AdjListGraph& g, int u) {
// visit
cout << g.adjList[u].value;
visited[u] = true;
for (Edge* edge = g.adjList[u].firstedge; edge != nullptr; edge = edge->next) {
if (!visited[edge->adjvex]) {
dfs(g, edge->adjvex);
}
}
}
void DFS(const AdjListGraph& g) {
for (int i = 0; i < g.vexnum; i++) {
visited[i] = false;
}
for (int i = 0; i < g.vexnum; i++) {
if (!visited[i]) {
dfs(g, i);
}
}
}
int main () {
AdjListGraph g;
createGraph(g);
printGraph(g);
BFS(g);
DFS(g);
deleteGraph(g);
}
reference: