邻接表图的深度优先搜索遍历与广度优先搜索遍历

邻接表表示图：

#define MVNum 100 //最大顶点数为100
typedef char VerTexType;  //图的顶点类型

//邻接表的边结点表示
typedef struct ArcNode
{
	int adjvex;  //表示边结点在顶点数组中的位置
	struct ArcNode* nextarc; //指向下一条边的指针
	//int weight;  //权重信息,视情况加或不加
}ArcNode;

//邻接表的顶点结点表示
typedef struct VNode
{
	VerTexType data;  //邻接表的顶点
	struct ArcNode* firstarc;  //顶点结点指向的第一条边
}VNode,Adjust[MVNum];

//邻接表的表示
typedef struct
{
	Adjust vertices; //顶点数组
	int vexnum, arcnum; //表的属性信息
}ALGraph;  //用邻接表来表示的图，adjust+list+graph

邻接表广度优先搜索遍历（本质是栈实现）：

//首先定义一个visited数组，用来记录第i个结点是否被访问
int visited[MVNum] = { 0 };
void DFS_AL(ALGraph&G, int i)
{
	cout << G.vertices[i].data << endl; //访问第i个顶点
	visited[i] = 1;
	ArcNode* p = G.vertices[i].firstarc;
	//当第i个顶点有相邻的边结点时，访问其边结点
	while(p)
	{
		int j = p->adjvex;
		if (visited[j] != 0)
		{
			DFS_AL(G, j);
			p = p->nextarc;
		}
	}
}

邻接表的广度优先搜索遍历：

//邻接表的广度优先遍历
void BFS_AL(ALGraph& G)
{
	int i;
	//先初始化标志数组
	for (i = 0; i < G.vexnum; i++)
	{
		visited[i] = 0;
	}
	//直接用标准模板库中的队列库来定义一个队列Q
	queue<VNode>Q;
	for (i = 0; i < G.vexnum; i++)
	{
		//如果第i个顶点未被访问过，那么就访问第i个顶点
		if (!visited[i])
		{
			//访问第i个顶点，并使之入队
			visited[i] = 1;
			cout << G.vertices[i].data << endl;
			Q.push(G.vertices[i]);
			//当队列非空时，使队首元素出队，并让它的邻接顶点入队
			while (!Q.empty())
			{
				//记录队首元素并让队首元素出队
				VNode head = Q.front();
				Q.pop();
				//让先前的队首元素的邻接顶点入队
				ArcNode* p = head.firstarc;
				while (p)
				{
					if (!visited[p->adjvex])
					{
						visited[p->adjvex] = 1;
						cout << G.vertices[i].data << endl;
						Q.push(G.vertices[p->adjvex]);
					}
					p = p->nextarc;
				}
			
			}
		}
	}
}