数据结构学习笔记（C++）：邻接表实现图的存储结构(深度优先遍历详解)

一、程序功能：

        1、构造一个4个顶点5条边的有向图（参数可调）

        2、实现深度优先遍历和广度优先遍历

二、图示：

        1、需要构建的图：

2、邻接表：

3、深度优先遍历中递归还不理解的小伙伴们看这里

代码骑士的一张图让你深刻理解递归的奥秘：

程序代码：

#include

#define MAXSIZE 100

using namespace std;

int visited[MAXSIZE] = { 0 };

//边表结点
struct EdgeNode
{
	int adjvex;//顶点下标
	EdgeNode* next;//边表结点指针
};

//顶点表结点
struct VertexNode 
{
	char vertext;//顶点数据
	EdgeNode* firstEdge;//边表头结点
};

class ALGraph {
public:
	ALGraph(char a[],int n,int e);
	~ALGraph();
public:
	void DFTraverse(int v);
	void BFTraverse(int v);
private:
	VertexNode adjlist[MAXSIZE];//定义顶点表（包含顶点的数据域和指针域）
	int VertexNum, EdgeNum;//图的顶点数和边数
};
//构造函数
ALGraph::ALGraph(char a[], int n, int e)
{
	int i, j, k;
	EdgeNode* s = NULL;//定义顶点表中的边表的头指针
	VertexNum = n;
	EdgeNum = e;
	for (i = 0; i < VertexNum; i++)//顶点表初始化
	{
		adjlist[i].vertext = a[i];
		adjlist[i].firstEdge = NULL;
	}
	for (k = 0; k < EdgeNum; k++)
	{
		cin >> i >> j;
		s = new EdgeNode;
		s->adjvex = j;//将顶点下标输入边表
		s->next = adjlist[i].firstEdge;//将结点s插入表头
		adjlist[i].firstEdge = s;//使用头插法减少操作数量使程序更高效
	}
}
//析构函数
ALGraph::~ALGraph()
{
	EdgeNode* p = NULL, * q = NULL;
	for (int i = 0; i < VertexNum; i++)
	{
		p = q = adjlist[i].firstEdge;
		while (p != NULL)
		{
			p = p->next;
			delete q;
			q = p;//悲惨的小q，永远的替罪羊
		}
	}
}
//深度优先
void ALGraph::DFTraverse(int v)
{
	int j;
	EdgeNode* p = NULL;
	cout << adjlist[v].vertext;
	visited[v] = 1;
	p = adjlist[v].firstEdge;
	while (p != NULL)
	{
		j = p->adjvex;//将p的下标传给j
		if (visited[j] == 0)
			DFTraverse(j);
		p = p->next;
	}
}
//广度优先
void ALGraph::BFTraverse(int v)
{
	for (int i = 0; i < MAXSIZE; i++)
		visited[i] = 0;
	int w, j, Q[MAXSIZE];
	int front = -1,rear = -1;//队列初始化
	EdgeNode* p = NULL;
	cout << adjlist[v].vertext;
	visited[v] = 1;
	Q[++rear] = v;//被访问顶点入队
	while (front != rear)
	{
		w = Q[++front];
		p = adjlist[w].firstEdge;//p指向顶点v的边表
		while (p != NULL)
		{
			j = p->adjvex;
			if (visited[j] == 0)
			{
				cout << adjlist[j].vertext;
				visited[j] = 1;
				Q[++rear] = j;
			}
			p = p->next;
		}
	}
}

int main()
{
	char ch[4] = { 'A','B','C','D' };
	int i;
	ALGraph ALG(ch, 4, 5);
	for (i = 0; i < MAXSIZE; i++)
		visited[i] = 0;
	cout <