数据结构邻接矩阵深度及广度优先

邻接矩阵这个想了挺久，因为数据结构的定义，网上很多直接用二位数组，这里用的是指针数组。比起二叉树应用于简单的搜索和分页，图更像是用来表示几种事物之间的复杂联系。

从A到D分别为矩阵第1到4列，1到4行，如Edges[0]表示的是A点与其他点的连接情况，Edges[0][1] = 1 表示为A与B相连，Edges[0][2] = 0 表示为A与C不相连。

还是三个文件

LinkMatrix.h

#include<stdio.h>

typedef char NodeType;
typedef float SideType;
typedef char DataType;

typedef struct LinkMatrix *PMatrix;
typedef struct LinkMatrix{
	int n;
	NodeType *Node;
	SideType *Side[]; 
};

typedef struct Node *PNode;
struct Node{
	DataType info;
	PNode link;
};
typedef struct LinkQueqe *PQueqe;
struct LinkQueqe{
	PNode f;
	PNode b;
};

PMatrix createMatrix(int n);
void printMatrix(PMatrix pmatrix);
void depthOrder(PMatrix pmatrix,NodeType node);
void breadthOrder(PMatrix pmatrix,NodeType node);
void recovervisit(int visited[100],int n);
void breadthpushQueqe(PMatrix,NodeType node);
NodeType adjacent(PMatrix pmatrix,NodeType node); 
NodeType nextadjacent(PMatrix pmatrix,NodeType node,int from);
PQueqe createQueqe();
void pushQueqe(PQueqe pqueqe,DataType element);
void popQueqe(PQueqe pqueqe);
DataType topQueqe(PQueqe pqueqe); 
int findNode(PMatrix pmatrix,NodeType node);

LinkMatrix.c

#include "LinkMatrix.h"
int visited[100];

void recovervisit(int visited[100],int n){
	int i;
	for(i= 0; i<n;i++){
		visited[i] = 0;
	}
}

PQueqe createQueqe(){
	PQueqe pqueqe = (PQueqe)malloc(sizeof(struct LinkQueqe));
	if(pqueqe == NULL) printf("create fail");
	pqueqe ->f = NULL;
	pqueqe ->b = NULL;
	return pqueqe;
}

void pushQueqe(PQueqe pqueqe,DataType element){
	PNode p = (PNode)malloc(sizeof(struct Node));
	if(p == NULL) printf("nothing push");
	p ->info = element;
	p ->link = NULL;
	if(pqueqe ->f == NULL){
		 pqueqe->f = p;
	//printf(" f  %5d
",pqueqe->f->info);
	}
	else pqueqe ->b ->link = p;
	pqueqe ->b = p;
	//	printf("b   %d
",pqueqe->b->info);
}

void popQueqe(PQueqe pqueqe){
	PNode p;
    if(!pqueqe) printf("queqe is empty");
    p = pqueqe ->f;
    pqueqe ->f = p->link;
    free(p);  
}

DataType topQueqe(PQueqe pqueqe){
	if(pqueqe->f == NULL){
		printf("nothing top");
		return NULL;
	} 
	return pqueqe -> f->info ;
}


void printQueqe(PQueqe pqueqe){
	PNode p = pqueqe ->f;
    if(	!pqueqe){
		printf("nothing print");
	} 
	while(pqueqe->f!= NULL){
		printf("%c
",pqueqe->f->info);
		pqueqe ->f = pqueqe ->f ->link;
	} 
	pqueqe ->f = p;//此处的f随着link的变化变化  最后需要还原回去！ 
}

PMatrix createMatrix(int n){
	PMatrix pmatrix = (PMatrix)malloc(sizeof(struct LinkMatrix));
	int i,j;
	if(!pmatrix){
		printf("create fail");
	}else{
		//printf("test");
		pmatrix ->n = n;
		recovervisit(visited,n);
		pmatrix ->Node = (NodeType *)malloc(sizeof(NodeType)*n);
		for(i = 0; i < n; i++){		
			pmatrix ->Side[i] = (SideType *)malloc(sizeof(SideType)*n);
			for(j = 0; j < n ; j++)
			pmatrix ->Side[i][j] = 0;
		}
	//	printf("test");
	}
	
	return pmatrix;
	
}
void printMatrix(PMatrix pmatrix){
	int i,j;
	for(i = 0; i < pmatrix->n; i++){		
		for(j = 0; j < pmatrix->n ; j++){
			if(pmatrix ->Side[i][j] == 1)
				printf("%c -> %c 
",pmatrix->Node[i],	pmatrix ->Node[j]);
		}			
	}
}

void depthOrder(PMatrix pmatrix,NodeType node){
	int n,i,j;	
	for(i = 0; i < pmatrix->n; i++){
			if(pmatrix ->Node[i] == node)
				n = i;
	}//找到这个node在矩阵中的位置。 
	printf("%c
",pmatrix->Node[n]);
	visited[n] = 1;
	for(i = 0; i < pmatrix->n; i++){		
		if(pmatrix ->Side[i][n] == 1 && visited[i] != 1){		
			depthOrder(pmatrix,pmatrix->Node[i]);
		}									
	}

}

int findNode(PMatrix pmatrix,NodeType node){
	int i,n;
	for(i = 0; i < pmatrix->n; i++){
			if(pmatrix ->Node[i] == node)
				n = i;
	}
	return n;
}//找到这个node在矩阵中的位置。

NodeType adjacent(PMatrix pmatrix,NodeType node){
	int n,i,j;	
	for(i = 0; i < pmatrix->n; i++){
			if(pmatrix ->Node[i] == node )
				n = i;
	}//找到这个node在矩阵中的位置。 
	for(i = 0; i < pmatrix->n; i++){		
		if(pmatrix ->Side[i][n] == 1 && visited[i] == 0){		
			return pmatrix ->Node[i];
		}									
	}
	return NULL;
}

NodeType nextadjacent(PMatrix pmatrix,NodeType node,int from){
	int n,i,j;	
	for(i = 0; i < pmatrix->n; i++){
			if(pmatrix ->Node[i] == node)
				n = i;
	}//找到这个node在矩阵中的位置。 
	for(i = from+1; i < pmatrix->n; i++){		
		if(pmatrix ->Side[i][n] == 1 && visited[i] == 0){		
			return pmatrix ->Node[i];
		}									
	}
	return NULL;
}

void breadthOrder(PMatrix pmatrix,NodeType node){
	PQueqe pqueqe;  
	int n,i,j;	
	recovervisit(visited,pmatrix->n);//将深度优先时 visited的值变回0
	breadthpushQueqe(pmatrix, node);
	while(node!= NULL){
		node = adjacent(pmatrix,node);
	if(visited[findNode(pmatrix,node)] == 0)
		breadthpushQueqe(pmatrix, node);
	} 
	
	
}

void breadthpushQueqe(PMatrix pmatrix,NodeType node){
	int i,n,count;
	NodeType ftemp,temp;
	PQueqe pqueqe = createQueqe();
	n = findNode(pmatrix,node);
		if(visited[n] == 0 && n != 1){
			pushQueqe(pqueqe,node);			
			printf("%c
",topQueqe(pqueqe));		
			popQueqe(pqueqe);
			visited[n] = 1;
		}
		temp = adjacent(pmatrix,node);
		n = findNode(pmatrix,temp);
		while(temp != NULL && visited[n] == 0) {
			n = findNode(pmatrix,temp); 
			pushQueqe(pqueqe,temp); 	
			printf("%c
",topQueqe(pqueqe));
			if(nextadjacent(pmatrix,temp,n)== NULL)
				visited[n] = 1;	 
			popQueqe(pqueqe);
			temp = nextadjacent(pmatrix,node,n);		
		}
 
}

main.c

#include "LinkMatrix.h"

int main(){
	PMatrix p = createMatrix(4);
	p -> Node[0] = 'A';
	p -> Node[1] = 'B';
	p -> Node[2] = 'C';
	p -> Node[3] = 'D';
	
	p->Side[0][1] = 1;
	p->Side[0][4] = 1;
	p->Side[1][0] = 1;
	p->Side[1][2] = 1;
	p->Side[1][3] = 1;
	p->Side[2][1] = 1;
	p->Side[3][0] = 1;
	p->Side[3][1] = 1;
//数组越界 程序自动崩溃 
	printf("output the linkmatrix : 
"); 
	printMatrix(p);	
	printf("output the linkmatrix in depthorder : 
");
	depthOrder(p,p->Node[0]);
	printf("output the linkmatrix in depthorder : 
");
	breadthOrder(p,p->Node[0]);
	return 0;
}

深度优先用一个递归即可，麻烦的是广度优先，因为要把一个点周围的点取出来，所以用到队列，放进队列后，要标记好其余的点，再循环此步，在这一步写得有漏洞，再去参考别人的代码，看看别人怎么写，再改到最好。

自己写和自己之前纯抄有很大区别，之前没有多用心学，感觉很复杂，静下心后，慢慢敲，接下来捣鼓一下排序的算法，差不多就完成了。

数据结构 邻接矩阵深度及广度优先

数据结构邻接矩阵深度及广度优先