traverse.cpp

文件夹中包括常用的数据结构的算法

#include <stdio.h>

#define INFINITY		INT_MAX
#define MAX_VERTEX_NUM	20
#define  V_NUM  8


/*
// 定义图的类型
typedef enum
{
	DG, 		// 有向图, 0
	DN, 		// 有向网, 1
	AG, 		// 无向图, 2
	AN			// 无向网, 3
}GraphKind;


// 邻接矩阵
typedef struct ArcCell
{
	int	adj;		// 顶点之间的关系的类型，对于无
						// 权图，1或0表示是否相邻，对于
						// 网，则为权值的类型。
	InfoType	*pInfo;		// 与该弧相关的信息的指针
}ArcCell, AdjMatrax[MAX_VERTEX_NUM][MAX_VERTEX_NUM];
*/

int visited[V_NUM] ={0} ;

typedef struct queue
{
    int que[V_NUM+1];
	int front,rear;
}queue;



typedef struct Mgraph
{
	int  vexs[V_NUM] ;// 顶点向量
	int	 arcs[V_NUM][V_NUM];			// 邻接矩阵
	int	 vexnum , arcnum;		// 顶点数和弧数
//	GraphKind 	kind;				// 图的类型
}Mgraph;

void DFSM(Mgraph &G, int v) //采用邻接矩阵
{ // 从顶点v出发，深度优先搜索遍历连通图 G
	visited[v] = 1;   
	printf("%d,\t", G.vexs[v]);
    
    for(int j=0;  j<G.vexnum;  j++)
    {
		if (!visited[j]&&G.arcs[v][j]==1)  
                 DFSM(G, j);    
    }// 对v的尚未访问的邻接顶点w
        //递归调用DFSM
} // DFSM



void BFSMTraverse(Mgraph  &G, int source)  // 采用邻接矩阵  source 为遍历的起始点对应的数据元素
{ 
    queue Q;
	int u;

	for (int v=0; v < G.vexnum; ++v) visited[v] = 0;  //初始化访问标志
    Q.front=Q.rear=0;       // 置空的辅助队列Q
    
	for ( v= (source - 1);  v<G.vexnum;  ++v )   //source 为遍历的起始点对应的数据元素,所以要-1
	{
        if ( !visited[v]) // v 尚未访问
        {     
			visited[v] = true; 
			printf("%d,\t", G.vexs[v]);    // 访问v

            Q.que[Q.rear++] = v;             // v入队列
			while (Q.front < Q.rear)  //当队列不空
			{  
				u = Q.que[Q.front++];           //u=DeQueue(&Q);        // 队头元素出队并置为u
				for(int j=0; j < G.vexnum; j++)
				{
				    if (G.arcs[u][j]==1 && !visited[j]) 
					{ 
						visited[j]= true;  
					    printf("%d,\t", G.vexs[j]);    // 访问v       //Visit(vexs[j]);
					    Q.que[Q.rear++] = j;             // v入队列                   //	EnQueue(&Q,j );
					}; // if
				};
					
			} // while 

		} 
	}
  } // BFSTraverse



void main()
{
    Mgraph G;
    int arcsMatrix[V_NUM][V_NUM] = {0, 1, 1, 0, 0, 0, 0, 0,
		                            1, 0, 0, 1, 1, 0, 0, 0,
									1, 0, 0, 0, 0, 1, 1, 0,
									0, 1, 0, 0, 0, 0, 0, 1,
									0, 1, 0, 0, 0, 0, 0, 1,
									0, 0, 1, 0, 0, 0, 0, 1,
									0, 0, 1, 0, 0, 0, 0, 1,
									0, 0, 0, 1, 1, 1, 1, 0};
	G.vexnum = V_NUM;
	for(int i = 0; i < V_NUM; i++)
	{
		G.vexs[i] = i+1;
	    for(int j = 0; j < V_NUM; j++)
		{
			G.arcs[i][j] = arcsMatrix[i][j];
		}
	}; 
    DFSM(G, 0);
	printf("\n");

	BFSMTraverse(G, 2);
	printf("\n");

}