图的BFS和DFS（邻接表）

上一篇已经叙述了相关的概念了。主要用代码实现一下。建议先看一下王道的课吧！个人感觉c语言基础比较可以的才能理清这指针指来指去的。反正我已经快麻木了。
今天给大家换个例子，尝尝鲜。

上图包含了邻接表的直观感受。
看一下邻接表的代码定义

//顶点
typedef struct Vnode{
	char data;		//对应图中data A，B···用来存储顶点信息
	struct ArcNode * first;//指向与该顶点的相连的边
}Vnode,AdjList[MaxVertexnum];//这是创建了一个结构体数组
//图---邻接表存储
typedef struct{
	AdjList Vertices;//顶点表
	int Vexnum,arcnum;//顶点数和边数
}ALGraph;
//边
typedef struct ArcNode{
	int adjvex;//存放相连顶点对应顶点表的下标
	struct ArcNode * next;//next指针，指向下一个边
}ArcNode;

是不是很简单，好吧，没那么简单。
看一下图的建立对应的代码
注释（）掉的部分是头插的，未注释的是尾插

void input_MGraph(ALGraph &G){
	int x=0,y=0;
	for(int i=0;i
		printf("请输入图边的无序对：");
		scanf("%d,%d",&x,&y);
		
		//加入x->y的边
		ArcNode * p=(ArcNode*)malloc(sizeof(ArcNode)); //申请空间
		p->adjvex=y;  //放入边对应下标
		if(G.Vertices[x].first==NULL){//如果与这个顶点没有与之相连的顶点
			G.Vertices[x].first=p;//边表的first指针指向新节点
			p->next=NULL;
		}
		else{//这个顶点有与之相连的边了
			ArcNode * q=G.Vertices[x].first;
			while(1){//q指向最后一个边节点
				if(q->next!=NULL) q=q->next;
				else break;
			}
			q->next=p;//把新节点加入最后一个结点的后面
			p->next=NULL;
		}
		//加入y->x的边
		p=(ArcNode*)malloc(sizeof(ArcNode));
		p->adjvex=x;
		if(G.Vertices[y].first==NULL){
			G.Vertices[y].first=p;
			p->next=NULL;
		}
		else{
			ArcNode * q=G.Vertices[y].first;
			while(1){
				if(q->next!=NULL) q=q->next;
				else break;
			}
			q->next=p;
			p->next=NULL;
		}
	}
}

其他的就没啥子东西了。
看一下完整的代码（注释很少，如果需要的话先看之前的吧！）

#include
#include
#define MaxVertexnum 6

//顶点
typedef struct Vnode{
	char data;
	struct ArcNode * first;
}Vnode,AdjList[MaxVertexnum];
//图---邻接表存储
typedef struct{
	AdjList Vertices;
	int Vexnum,arcnum;
}ALGraph;

bool visited[MaxVertexnum];

//边
typedef struct ArcNode{
	int adjvex;
	struct ArcNode * next;
}ArcNode;


//队列节点的结构定义 
typedef struct Linknode{
	int data;
	struct Linknode *next;
}Linknode;
//队列首尾指针的定义 
typedef struct{
	Linknode *front,*rear;
}LinkQueue;

//初始化队列 
void InitQueue(LinkQueue &Q){
	//带头结点的链队列 
	Q.front=(Linknode*)malloc(sizeof(Linknode));
	Q.rear=Q.front;
	Q.front->next=NULL;
}
//入队 
void EnQueue(LinkQueue &Q,int p){
	//S指向新节点，连接Q.rear后面
	Linknode *S=(Linknode*)malloc(sizeof(Linknode));
	S->data=p;
	S->next=NULL;
	Q.rear->next=S;
	Q.rear=S; 	
} 
//出队
bool DeQueue(LinkQueue &Q,int &p){
	//如果队空就不能出队列了
	if(Q.front==Q.rear) return false;
	Linknode *q=Q.front->next;
	p=q->data;
	Q.front->next=q->next;
	//刚好最后一个结点出队了，把rear指向头结点从而判空
	if(q==Q.rear){
		Q.rear=Q.front;
	}
	free(q);
	return true;
}
//判空 
bool isEmptyQueue(LinkQueue Q){
	if(Q.front==Q.rear) return true;
	else return false;
}


 
void input_MGraph(ALGraph &G){
	int x=0,y=0;
	for(int i=0;i
		printf("请输入图边的无序对：");
		scanf("%d,%d",&x,&y);
		
		//加入x->y的边
		ArcNode * p=(ArcNode*)malloc(sizeof(ArcNode));
		p->adjvex=y;
		if(G.Vertices[x].first==NULL){
			G.Vertices[x].first=p;
			p->next=NULL;
		}
		else{
			ArcNode * q=G.Vertices[x].first;
			while(1){
				if(q->next!=NULL) q=q->next;
				else break;
			}
			q->next=p;
			p->next=NULL;
		}
		//加入y->x的边
		p=(ArcNode*)malloc(sizeof(ArcNode));
		p->adjvex=x;
		if(G.Vertices[y].first==NULL){
			G.Vertices[y].first=p;
			p->next=NULL;
		}
		else{
			ArcNode * q=G.Vertices[y].first;
			while(1){
				if(q->next!=NULL) q=q->next;
				else break;
			}
			q->next=p;
			p->next=NULL;
		}
	}
}

void FirstNeighbor(ALGraph &G,int v,ArcNode * &p){
	p=G.Vertices[v].first;	
}

int NextNeighbor(ALGraph &G,ArcNode * &w){
	w=w->next;
}

void DFS(ALGraph &G,int v);
void DFSTraverse(ALGraph &G){
	for(int i=0;i
		if(!visited[i]) DFS(G,i);
	}
}
void DFS(ALGraph &G,int v){
	printf("%c  ",G.Vertices[v].data);
	visited[v]=true;
	ArcNode * w=NULL;
	for(FirstNeighbor(G,v,w);w!=NULL;NextNeighbor(G,w)){
		if(!visited[w->adjvex]) DFS(G,w->adjvex);
	}
}

void BFS(ALGraph &G,LinkQueue &Q,int v);

void BFSTravese(ALGraph &G){
	for(int i=0;i
		if(!visited[i]) BFS(G,Q,i);
	}
} 
void BFS(ALGraph &G,LinkQueue &Q,int v){
	ArcNode * w=NULL;
	printf("%c  ",G.Vertices[v].data);
	visited[v]=true;
	EnQueue(Q,v);
	while(!isEmptyQueue(Q)){
		DeQueue(Q,v);
		for(FirstNeighbor(G,v,w);w!=NULL;NextNeighbor(G,w)){
			if(!visited[w->adjvex]){
				printf("%c  ",G.Vertices[w->adjvex].data);
				visited[w->adjvex]=true;
				EnQueue(Q,w->adjvex);
			}
		}
	}
}
int main()
{
	ALGraph G;
	input_MGraph(G);
	printf("n深度优先遍历序列：");
	DFSTraverse(G); 
	printf("n广度优先遍历序列：");
	BFSTravese(G);
	return 0;
}

结果

尽可能的实现吧。老实现代码复习的很慢。上次考试没考上。往后推了，这个大概更新不了几篇了。大致接近尾声了。