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

邻接矩阵的表示：

#define MAXINT 32767   //表示极大值
#define MVNum 100 //邻接矩阵的最大顶点数
typedef char VerTexType; //假设顶点的数据类型为char型
typedef int ArcType; //假设边的权值类型为int型

//定义一个邻接矩阵图
typedef struct
{
	VerTexType vexs[MVNum]; //顶点数组用来存储每个顶点
	ArcType arcs[MVNum][MVNum]; //n*n阶矩阵（即二维数组）用来表示边
	int vexnum, arcnum; //顶点和边用来表示图的属性
}AMGraph;

邻接矩阵的深度优先搜索遍历连通图（本质是栈实现）：

//邻接矩阵的深度优先搜索遍历算法——DFS
int visited[MVNum]={0}; //定义的是全局数组，故函数内部也可以访问
//i表示访问图中第i个结点
void DFS_AM(AMGraph& G, int i)
{
	cout << G.vexs[i]; //访问（输出）第i个结点
	visited[i] = 1; //表示访问过第i个结点了，接下来就是该访问它的邻接顶点了
	for (int j = 0; j < G.vexnum; j++)
	{
		//访问与第i个结点相邻且未被访问过的结点
		if ((G.arcs[i][j]) != 0 && !visited[j])
		{
			DFS_AM(G, j);
		}
	}
}

深度优先搜索遍历非连通图：

void DFSTraverse_AM(AMGraph&G)
{
	for (int i = 0; i < G.vexnum; i++)
	{
		//访问标志数组初始化
		visited[i] = 0;
	}
	//循环调用算法
	for (int i = 0; i < G.vexnum; i++)
	{
		//对未访问过的顶点进行调用DFS_AM算法
		if (!visited[i])
		{
			DFS_AM(G, i);
		}
	}
	//最后，DFS_AM函数被调用几次，那么就说明有几个连通分量
}

邻接矩阵的广度优先搜索遍历连通图（本质是队列实现）：

void BFS_AM(AMGraph& G, int i)
{
	//直接调用c++中的队列算法，定义一个队列Q
	queue<VerTexType> Q;
	//访问第i个结点
	cout << G.vexs[i] << endl;
	visited[i] = 1;
    //第i个结点成为首先入队的结点
	Q.push(G.vexs[i]);
	//当队列非空时，先让队头元素出队，然后让与队头元素邻接的顶点入队
	while (!Q.empty())
	{
		VerTexType v=Q.front();
        Q.pop();
        i=LocateVex[v];
		for (int j = 0; j < G.vexnum; j++)
		{
			if (G.arcs[i][j] == 1 && visited[j] == 0)
			{
				cout << G.vexs[j] << endl;
				visited[j] = 1;
				Q.push(G.vexs[j]);
			}
		}
	}
}

对于非连通图的广度优先搜素遍历，其算法应该类似非连通图的深度优先搜素遍历。