实现图的遍历

//MGraph.h
typedef enum{DG,DN,UDG,UDN} GraphKind;//图的种类 
//弧结点结构 
typedef struct{
	char vertex[20];//顶点数组
	int arcs[20][20];//邻接矩阵 
	int vexnum,arcnum;//顶点数和弧数
	GraphKind kind;
}AdjMatrix;

//图的遍历
#include
#include"MGraph.h"
#include
#define TRUE 1
#define FALSE 0
using namespace std;
typedef struct Node
{
	int data;
	struct Node* next;
}LinkQueueNode;
typedef struct
{
	LinkQueueNode* front;
	LinkQueueNode* rear;
}LinkQueue;
int visited[20];
int visitedBFS[20]={0};
void DepthFirstSearch(AdjMatrix g,int v0);
void BreadthFirstSearch(AdjMatrix g);
int main()
{
	AdjMatrix am;
	cout<<"请输入顶点数：";
	cin>>am.vexnum;
	if(am.vexnum>20)
	{
		cout<<"输入数值过大！"<
		return 0; 
	}
	cout<<"请依次输入各顶点：";
	for(int i=0;i
	{
		cin>>am.vertex[i];
	}
	cout<<"请依次输入各边权值："<
	for(int i=0;i
	{
		for(int j=0;j
		{
			cin>>am.arcs[i][j];
		}
	}
	cout<<"     ";
	for(int i=0;i
	{
		cout<"    ";
	}
	cout<
	for(int i=0;i
	{
		cout<"    ";
		for(int j=0;j
		{
			cout<"    ";
		}
		cout<
	}
	cout<<"深度优先遍历序列为：";
	DepthFirstSearch(am,0);
	cout<
	cout<<"广度优先遍历序列为：";
	BreadthFirstSearch(am);
	return 0;
}
void DepthFirstSearch(AdjMatrix g,int v0) /* 图g为邻接矩阵类型AdjMatrix */ 
//函数参数g代表要处理的图，v0代表当前访问的顶点 
{
	cout<
	visited[v0]=1;//标记该顶点已被输出 
	for(int vj=0;vj
	{
		//利用for循环找到该顶点的邻接点，并判断是否未被输出 
		if(!visited[vj]&&g.arcs[v0][vj]!=0) 
		DepthFirstSearch(g,vj);//找到之后以该邻接点为顶点进行递归 
	}
} 
int InitQueue(LinkQueue *Q)
{ 
	/* 将Q初始化为一个空的链队列 */
	Q->front=(LinkQueueNode *)malloc(sizeof(LinkQueueNode));
	if(Q->front!=NULL)
	{
		Q->rear=Q->front;
		Q->front->next=NULL;
 		return(TRUE);
	}
	else  	
	return(FALSE);    /* 溢出！*/
}
int EnterQueue(LinkQueue *Q,int x)
{  
	/* 将数据元素x插入到队列Q中 */
	LinkQueueNode *NewNode;
	NewNode=(LinkQueueNode *)malloc(sizeof(LinkQueueNode));
	if(NewNode!=NULL)
	{
		NewNode->data=x;
		NewNode->next=NULL;
		Q->rear->next=NewNode;
	  	Q->rear=NewNode;
		return(TRUE);
	}
	else  
	return(FALSE);    /* 溢出！*/
}
int DeleteQueue(LinkQueue *Q)
{  
	/* 将队列Q的队头元素出队 */
	LinkQueueNode *p;
	if(Q->front==Q->rear)
		return(FALSE);
	p=Q->front->next;
	Q->front->next=p->next;  /* 队头元素p出队 */
	if(Q->rear==p)  /* 如果队中只有一个元素p，则p出队后成为空队 */
	Q->rear=Q->front;  
	free(p);   /* 释放存储空间 */
	return(TRUE);	
}
int JudgeQueue(LinkQueue *Q)
{
	if(Q->front==Q->rear)
	{
		return 0;
	}
	else
	{
		return 1; 
	}
}
int FindVertex(AdjMatrix g,int k)				//传入无向图G,要查找节点的位序k
{
	if(k>=g.vexnum || k<0 )
	{
		return -1;
	}							//参数不合理直接返回ERROR
	int i;
	for(i=0;i
	{
		if(g.arcs[k][i]==1)					//遍历位序为k的节点的 关系数组行,
			return i;	
	}							    //找到的话返回位序，否则最后返回ERROR
	return -1;
}
int NextAdjvex(AdjMatrix g,int k,int m)					
//传入无向图G,要查找节点的位序k,要找的临接点的起始位序的前一位m
{
	if(k>=g.vexnum|| k<0 || m>=g.vexnum-1 || m<0)
		return -1;									//参数不合理直接返回ERROR
	int i;
	for(i=m+1;i
		if(g.arcs[k][i]==1)				//从m+1开始遍历位序为k的节点的 关系数组行,
			return i;						//找到的话返回位序，否则最后返回ERROR
	return -1;
}
void BreadthFirstSearch(AdjMatrix g)
{
    LinkQueue Q;
    InitQueue(&Q);
    int m,e;
    for (int i=0;i
	{
        if (!visitedBFS[i]) 
		{
            visitedBFS[i] = 1;
            cout<
            EnterQueue(&Q, i); // 顶点i入队列
            while (JudgeQueue(&Q)) {
                e=i;
                DeleteQueue(&Q);
                for (m = FindVertex(g, e); m != -1; m = NextAdjvex(g, e, m))
				 // 检测i的所有邻接顶点
                {
					if (!visitedBFS[m]) // m为i尚未访问的邻接顶点
                    {
                        visitedBFS[m] = 1; // 访问顶点m，做标记
                        cout<
                        EnterQueue(&Q, m); // 顶点m入队列
                    }
                }
            }
        }
    }
}