[数据结构与算法]采用邻接矩阵的形式存储图，进行图的深度优先搜索并输出结果。

一，首先要用邻接矩阵的形式存储图。定义好图的邻接矩阵，定义一维数组vexs[]用来表示与顶点有关的信息，二维数组arcs[][]用来表示图中不同边的权值。由于广度优先遍历需要的循环队列，所以也要构建队列，以及相关的初始化，入队，判空，出队等配套的函数。然后要创建邻接矩阵，并对邻接矩阵中顶点个数，边的个数，不同边的权值进行初始化。完成邻接矩阵的存储。

二，进行深度优先搜索然后遍历。深度优先遍历是个递归过程，所以这个算法可以用递归实现。首先，若访问过顶点，则该标识设置为1，并输出当前顶点。若某个顶点没有被访问过，则继续进行遍历此顶点，然后继续找下一个邻接点，递归递归进行遍历，当所有临顶点都被访问。在回溯前一个邻接点看是否还有没访问到的节点，直到所有顶点完成。

#include "stdio.h"
#include "stdlib.h"
#define MaxVex 100            //最大顶点数
#define INFINITY 65535        //表示∞
#define TRUE 1
#define FALSE 0
typedef char VertexType;    //顶点类型
typedef int EdgeType;    //权值类型
typedef int Bool;
Bool visited[MaxVex];

//构建邻接矩阵
typedef struct {
	VertexType    vexs[MaxVex];            //顶点数组
	EdgeType    arcs[MaxVex][MaxVex];    //邻接矩阵
	int    numVertexes, numEdges;            //当前图中的结点数以及边数
}MGraph;

//广度优先遍历需要的循环队列
typedef struct {
	int    data[MaxVex];
	int    front, rear;
}Queue;

//初始化
void InitQueue(Queue *Q)
{
	Q->front = Q->rear = 0;
}

//入队
void EnQueue(Queue *Q, int e)
{
	if ((Q->rear + 1) % MaxVex == Q->front)
		return;

	Q->data[Q->rear] = e;
	Q->rear = (Q->rear + 1) % MaxVex;
}

//判空
Bool QueueEmpty(Queue *Q)
{
	if (Q->front == Q->rear)
		return TRUE;
	else
		return FALSE;
}

//出队
void DeQueue(Queue *Q, int *e)
{
	if (Q->front == Q->rear)
		return;

	*e = Q->data[Q->front];
	Q->front = (Q->front + 1) % MaxVex;
}


//建立图的邻接矩阵
void CreateMGraph(MGraph *G)
{
	int i, j, k, w;

	printf("输入顶点数和边数:\n");
	scanf("%d%d", &G->numVertexes, &G->numEdges);
	fflush(stdin);

	printf("==============================\n");
	printf("输入各个顶点:\n");
	for (i = 0; i<G->numVertexes; ++i)
	{
		printf("顶点%d: ", i + 1);
		scanf("%c", &G->vexs[i]);
		fflush(stdin);
	}
	for (i = 0; i<G->numVertexes; ++i)
	{
		for (j = 0; j<G->numVertexes; ++j)
			G->arcs[i][j] = INFINITY;
	}
	printf("==============================\n");
	for (k = 0; k<G->numEdges; ++k)
	{
		printf("输入边(vi, vj)中的下标i和j和权W: \n");
		scanf("%d %d %d", &i, &j, &w);
		G->arcs[i][j] = w;
		G->arcs[j][i] = G->arcs[i][j];
	}
}

//输出
void DisMGraph(MGraph *G)
{
	int i, j, k;
	k = G->numVertexes;
	for (i = 0; i<k; ++i)
	{
		for (j = 0; j<k; ++j)
		{
			printf("%5d ", G->arcs[i][j]);
		}
		putchar('\n');
	}
}

//图的深度优先遍历
void DFS(MGraph G, int i)
{
	int j;
	visited[i] = TRUE;
	printf("%c ", G.vexs[i]);

	for (j = 0; j<G.numVertexes; ++j)
	{
		if (G.arcs[i][j] != INFINITY  &&  !visited[j])
			DFS(G, j);
	}
}

void DFSTraverse(MGraph G)
{
	int i;
	for (i = 0; i < G.numVertexes; ++i)
	{
		visited[i] = FALSE;
	}
	for (i = 0; i<G.numVertexes; ++i)
	{
		if (!visited[i])
			DFS(G, i);
	}
}

//程序入口
int main(){
	MGraph G;
	CreateMGraph(&G);
	printf("\n图的深度优先遍历为: ");
	DFSTraverse(G);
	printf("\n");
	return 0;
}