图的深度遍历(Depth First Serch),即DFS。采用递归方法。如果当前顶点有一下层节点则没有被访问过，则访问，否则回溯。
下面动画，展示了DFS算法的具体过程。
代码如下
//TestMGraph.cpp
#include "MatrixGraph.h"
#define DefA 0
#define DefB 1
#define DefC 2
#define DefD 3
#define DefE 4
#define DefF 5
#define DefG 6
#define DefH 7
#define DefI 8
void CreateGraph1(MatrixGraph & mGraph)
{
std::vector<char> vertexName;
char arr[]={'A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I'};
vertexName.insert(vertexName.begin(), arr, arr+9);
std::vector<Edge> edges;
Edge e;
//1
e.weight = 1;
e.i = DefA;e.j=DefB;
edges.push_back(e);
//2
e.i = DefF;e.j=DefE;
edges.push_back(e);
//3
e.i = DefC;e.j=DefD;
edges.push_back(e);
//4
e.i = DefI;e.j=DefD;
edges.push_back(e);
//5
e.i = DefA;e.j=DefF;
edges.push_back(e);
//6
e.i = DefB;e.j=DefG;
edges.push_back(e);
//7
e.i = DefB;e.j=DefC;
edges.push_back(e);
//8
e.i = DefD;e.j=DefE;
edges.push_back(e);
//9
e.i = DefG;e.j=DefD;
edges.push_back(e);
//10
e.i = DefG;e.j=DefF;
edges.push_back(e);
//11
e.i = DefB;e.j=DefI;
edges.push_back(e);
//12
e.i = DefG;e.j=DefH;
edges.push_back(e);
//13
e.i = DefH;e.j=DefD;
edges.push_back(e);
//14
e.i = DefH;e.j=DefE;
edges.push_back(e);
//
e.i = DefC;e.j=DefI;
edges.push_back(e);
CreateMatrixGraph(mGraph, vertexName, edges);
}
void TestMGraph()
{
MatrixGraph mGraph;
CreateGraph1(mGraph);
MDFSTraverse(mGraph, 0);
//MBFSTraverse(mGraph, 0);
}
//MatrixGraph.h
#pragma once
#include <vector>
struct MatrixGraph
{
enum{MAXVEX=100};
static const int INFINITY;
char vexs[MAXVEX]; //顶点类型 char
int arc[MAXVEX][MAXVEX]; //邻接矩阵
int numVerteices; //图中当前的顶点数
int numEdges; //图中当前的边数
MatrixGraph();
};
void CreateMatrixGraph(MatrixGraph & mGraph, std::vector<char> & vertexName, std::vector<Edge> & edges);
void MDFSTraverse(MatrixGraph & mGraph, int v);
//MatrixGraph.cpp
#include "MatrixGraph.h"
#include <iostream>
#include <memory.h>
#include <queue>
const int MatrixGraph::INFINITY = INT_MAX;
bool visited[MatrixGraph::MAXVEX];
MatrixGraph::MatrixGraph()
:numVerteices(0),
numEdges(0)
{
//temp
memset(vexs, 0, sizeof(char)*MAXVEX);
for(int i=0; i<MAXVEX; i++)
{
for(int j=0; j<MAXVEX; j++)
{
arc[i][j] = INFINITY;
}
}
for(int i=0; i<MAXVEX; i++)
{
arc[i][i] = 0;
}
}
void CreateMatrixGraph(MatrixGraph & mGraph, std::vector<char> & vertexName, std::vector<Edge> & edges)
{
int count = vertexName.size();
mGraph.numVerteices = count;
//生成顶点
for(int i=0; i<count; i++)
{
mGraph.vexs[i] = vertexName[i]; //i为顶点的编号
}
//生成边
count = edges.size(); //一定是偶数
for(int k=0;k<count; k++)
{
mGraph.arc[edges[k].i][edges[k].j] = mGraph.arc[edges[k].j][edges[k].i] = edges[k].weight; //无向图
}
}
//返回v节点的第一个邻接顶点。若顶点v在图中没有邻接顶点，则返回-1
int FirstAdjVex(MatrixGraph & mGraph, int v)
{
for(int j=0; j<mGraph.numVerteices; j++)
{
//图的边有权重 不相连的边的权重为INFINITY 权重为非负整数
if(mGraph.arc[v][j] != MatrixGraph::INFINITY && mGraph.arc[v][j] != 0 && !visited[j])
//if(mGraph.arc[v][j] != MatrixGraph::INFINITY && mGraph.arc[v][j] != 0)
return j;
}
return -1;
}
//返回v的(相对于w的)下一个邻接顶点。若访问完了v的所有顶点，则返回-1
int NextAdjVex(MatrixGraph & mGraph, int v, int w)
{
for(int j=w; j<mGraph.numVerteices; j++)
{
//图的边有权重 不相连的边的权重为INFINITY 权重为非负整数
if(mGraph.arc[v][j] != MatrixGraph::INFINITY&& !visited[j])
//if(mGraph.arc[v][j] != MatrixGraph::INFINITY)
{
return j;
}
}
return -1;
}
//《结构结构》(c语言版) 严蔚敏
void MDFS(MatrixGraph & mGraph, int v, int parentID)
{
//从第v个顶点出发递归深度优先遍历图G
visited[v] = true;
std::cout<<mGraph.vexs[v] <<":parent="<<mGraph.vexs[parentID]<<std::endl;
for(int w = FirstAdjVex(mGraph, v); w>-1; w=NextAdjVex(mGraph, v, w))
{
if(!visited[w])
MDFS(mGraph, w, v); //对v的沿未访问的邻接顶点w递归调用DFS
}
}
void MDFSTraverse(MatrixGraph & mGraph, int v)
{
memset(visited, 0, sizeof(bool)*MatrixGraph::MAXVEX);
MDFS(mGraph, v, 0);
}
结果
A:parent=A B:parent=A C:parent=B D:parent=C E:parent=D F:parent=E G:parent=F H:parent=G I:parent=D 请按任意键继续. . .
随便说一下，代码结构参考《数据结构》(c语言版) 严蔚敏【1】。但【1】中的代码不能从任意一个顶点开始深度遍历。且【1】中的代码可以遍历非连通图，并不是专门为遍历连通图设计的。
给CSDN提个建议:通过CSDN博客上传GIF图片，插入博客中。GIF图片是死图。建议修改成活图。