图--邻接表深度广度遍历实现

图的遍历：是实现图算法的基础。

1）深度优先搜索(Depth_First_Search)遍历类似于树的先根遍历，是树的先根遍历的推广。 —>广义栈
描述：从图中某个顶点v出发，访问此顶点，然后依次从v的未访问的邻接点出发深度优先遍历图，直到图中所有和v有路径相通的顶点都被访问到；
若此时图中尚有顶点未被访问，则另选图中一个未曾被访问的顶点作为起点，重复上述过程，知道图中所有顶点都被访问为止。

1）广度优先搜索(Breadth_Fisrt_Search)遍历类似于树的按层次遍历的过程。—>队列
描述：是以v为起始点，由近及远，依次访问和v有路径相通且路径长度为1,2，…的顶点。

实现：(以图的邻接矩阵存储图结构，实现上述两种遍历方)

#include <stdio.h>
#include <stdlib.h>

/*队列,在广度优先搜索中用到队列*/
typedef int QElemType;
typedef struct QNode{
	QElemType data;
	struct QNode *next;
}QNode, *QueuePtr;
typedef struct{
	QueuePtr front;
	QueuePtr rear;
}LinkQueue;
int InitQueue(LinkQueue &Q);
int EnQueue(LinkQueue &Q, QElemType e);
int DeQueue(LinkQueue &Q, QElemType &e);
int QueueEmpty(LinkQueue Q);
int QueueTraverse(LinkQueue Q, int(*visit)(QueuePtr p));
int data_output(QueuePtr p);

//图的邻接表存储表示
#define MAX_VERTEX_NUM 20
#define INF INT_MAX
typedef int InfoType;
typedef int VertexType;
typedef struct ArcNode{
	int adjvex; //邻接点序号
	int value; //表示边的权值
	struct ArcNode* nexttarc; //下一条边的顶点
	InfoType *info;
};
typedef struct VNode{  
	VertexType data;    //顶点信息 
	ArcNode *firsttarc;  //指向第一条边节点
}VNode, AdjList[MAX_VERTEX_NUM];  //单链表的头结点类型

typedef struct{
	AdjList Vertices;   //单链表头结点数组
	int vexnum, arcnum;  //实际的顶点数vexnum 边数arcnum
	int kind;
}ALGraph;

int visited[MAX_VERTEX_NUM];
int graph[6][6] = {
	INF, 5, INF, 7, INF, INF,
	INF, INF, 4, INF, INF, INF,
	8, INF, INF, INF, INF, 9,
	INF, INF, 5, INF, INF, 6,
	INF, INF, INF, 5, INF, INF,
	3, INF, INF, INF, 1, INF
};
/*深度优先搜索遍历DFS*/
void DFS(ALGraph G, int v){
	visited[v] = true;
	printf("v%d-->", v);
	ArcNode * p = G.Vertices[v].firsttarc;
	while(p!=NULL){
		if (!visited[p->adjvex]){
			DFS(G, p->adjvex);
		}
			
		p = p->nexttarc;
	}
}
void DFSTraverse(ALGraph G){
	for (int v = 0; v < G.vexnum; v++){
		visited[v] = false;
	}
	for (int v = 0; v < G.vexnum; v++){
		if (!visited[v]){
			DFS(G, v);
			
		}
	}
}

/*广度优先搜索遍历BFS*/
void BFS(ALGraph G, int v){
	/*初始化队列*/
	LinkQueue Q;
	InitQueue(Q);
	int u;
	for (  ; v < G.vexnum; ++v){
		visited[v] = true;
		printf("v%d-->", v);
		EnQueue(Q, v);
		ArcNode *p;
		while (!(QueueEmpty(Q))){
			DeQueue(Q, u);
			p = G.Vertices[u].firsttarc;
			while (p!=NULL){
				if (!visited[p->adjvex]){
					visited[p->adjvex] = true;
					EnQueue(Q, p->adjvex);
					
				}
				p = p->nexttarc;
			}
		}
	}
}
void BFSTraverse(ALGraph G){
	for (int v = 0; v < G.vexnum; ++v){
		visited[v] = false;
	}
	for (int v = 0; v < G.vexnum; v++){
		if (!visited[v]){
			BFS(G, v);
			
		}
	}
}


void CreateGraph(ALGraph &G){
	G.vexnum = 6;
	G.arcnum = 10;
	//初始化顶点的信息
	for (int i = 0; i < G.vexnum; i++){
		G.Vertices[i].data = i;
		G.Vertices[i].firsttarc = NULL;
	}
	for (int i = 0; i < 6; i++){
		for (int j = 5; j >= 0; j--){
			if (graph[i][j] != INF){
				ArcNode* p = (ArcNode*)malloc(sizeof(ArcNode));
				p->adjvex = j ;
				p->value = graph[i][j];
				p->nexttarc = G.Vertices[i].firsttarc;
				G.Vertices[i].firsttarc = p;
			}
		}
	}
}
void DisplayerGraph(ALGraph &G){
	int i = 0;
	ArcNode *p;
	for (i = 0; i < G.vexnum; i++){
		printf("顶点[V%d]的邻接边 ",G.Vertices[i].data);
		p = G.Vertices[i].firsttarc;
		while (p){
			printf("-->(%d,%d)", p->adjvex, p->value);
			p = p->nexttarc;
		}
		printf("-->(^)\n");
	}
}

int main(){
	ALGraph  *G;
	G = (ALGraph*)malloc(sizeof(ALGraph));
	CreateGraph(*G);
	DisplayerGraph(*G);	
	printf("深度优先搜索：\n");
	DFSTraverse(*G);
	printf("\n");
	printf("广度优先搜索\n");
	BFSTraverse(*G);
	printf("\n");
	return 1;
}

int InitQueue(LinkQueue &Q){
	Q.front = Q.rear = (QueuePtr)malloc(sizeof(QNode));
	if (!Q.front)
		exit(-1);
	Q.front->next = NULL;
	return 1;
}

int EnQueue(LinkQueue &Q, QElemType e){
	QueuePtr p = (QueuePtr)malloc(sizeof(QNode));
	if (!p){
		exit(-1);
	}
	p->data = e;
	p->next = NULL;
	Q.rear->next = p;
	Q.rear = p;
	return 1;
}

int DeQueue(LinkQueue &Q, QElemType &e){
	if (Q.front == Q.rear)
		return -1;
	QueuePtr p = Q.front->next;
	e = p->data;
	Q.front->next = p->next;
	if (Q.rear == p)
		Q.rear = Q.front;
	free(p);
	return 1;
}

int QueueEmpty(LinkQueue Q){
	return (Q.front->next == NULL &&  Q.rear->next == NULL) ? 1 : 0;
}

int QueueTraverse(LinkQueue Q, int(*visit)(QueuePtr p)){
	QueuePtr p = Q.front->next;
	while (p){
		visit(p);
		p = p->next;
	}
	printf("\n");
	return 1;
}
int data_output(QueuePtr p){
	printf("%d  ", p->data);
	return 1;
}