图的深度优先算法和广度优先算法

本文主要是介绍图的深度优先算法和广度优先算法，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

        f记录的是当前结点，比如运行到f = 2，f按行往里面走，如果对应的点不是0，并且那个点没被遍历过则把那个结点位置进入q数组，留给下一个结点遍历，next数组记录遍历过的点；那个for循环对应的就是计算与当前结点有联系的结点；建议自己画图走一遍；

        例如：从  A开始 先找到B，然后找到C，因为B,C和A有联系，这种方法是从一个结点开始，找完和这个结点相关的所有结点，然后再进行下一个

void BFS(ArrayGraph *pGraph,int *next,int k)
{
	int q[MAXSIZE];	//	记录每一个遍历过的结点
	next[k] = 1;
	q[0] = k;
	int i,j,f= 0,r=0;
	while(f<=r)
	{
		i = q[f];	//	记录到哪个节点了 
		for(j = 0;j<MAXSIZE;j++)
		{
			if(pGraph->data[i][j]&&!next[j])
			{
				r++;
				next[j] = 1;
				q[r] = j;
			}
		}
		f++;
	} 
	for(i=0;i<MAXSIZE;i++)
	{
		printf("%c ",pGraph->Vertex[q[i]]);
	}
}

深度优先算法：

        用next数组记录遍历过的结点，用一个for循环开始,因为这是一个数组，从第一个结点开始，找到第一个和他有联系的结点，然后递归从第二个结点开始寻找，

        例如  从 A 开始,  先找到B      从B开始第一个找到C.......

void DFS(ArrayGraph *pGraph,int *next,int k)
{
	next[k] = 1 ;
	printf("%c ",pGraph->vertexArr[k]);
	
	for(int w=0;w<MAX_VERTEX;w++)
	{
		if(pGraph->edge[k][w]&&!next[w])
		{
			DFS(pGraph,next,w);
		}
	} 
}

总代码如下：

#include <stdio.h>

#define MAX_VERTEX 6
    //四个顶点的图

typedef char ElemType;

//	定义图 
typedef struct 
{
	ElemType vertexArr[MAX_VERTEX];   //	存放顶点元素
	int edge[MAX_VERTEX][MAX_VERTEX]; 	  //	存放边矩阵二维数组 
}ArrayGraph; 

//	初始化图 ,所有对角线元素都为0； 
void ArrayGraph_init(ArrayGraph *pGraph)
{
	for(int i =0;i<MAX_VERTEX;i++)
	{
		pGraph->edge[i][i] = 0;
	}
} 

//	创建图
void ArrayGraph_create(ArrayGraph *pGraph)
{
	for(int i = 0;i<MAX_VERTEX;i++)
	{
		printf("输入第%d个顶点为：",i+1);
		
		scanf(" %c",&(pGraph->vertexArr[i]));
	}
	
	for(int i = 0;i<MAX_VERTEX;i++)
	{
		for(int j = i+1;j<MAX_VERTEX;j++)
		{
			printf("若顶点 %c 和 %c 有边则输入1，否则输入0\n",pGraph->vertexArr[i],pGraph->vertexArr[j]);
			
			scanf("%d",&(pGraph->edge[i][j]));
			
			pGraph->edge[j][i] = pGraph->edge[i][j] ;
		}
	}
} 


void DFS(ArrayGraph *pGraph,int *next,int k)
{
	next[k] = 1 ;
	printf("%c ",pGraph->vertexArr[k]);
	
	for(int w=0;w<MAX_VERTEX;w++)
	{
		if(pGraph->edge[k][w]&&!next[w])
		{
			DFS(pGraph,next,w);
		}
	} 
}


int main()
{
	int next[MAX_VERTEX];
	
	for(int i = 0;i<MAX_VERTEX;i++)
	{
		next[i] = 0;
	} 
	ArrayGraph g;
    ArrayGraph_init(&g);       //初始化图 
    ArrayGraph_create(&g);     //创建图 
    //ArrayGraph_show(&g);       //打印图 
	for(int i=0;i<MAX_VERTEX;i++)
	{
		if(!next[i])
		{
			DFS(&g,next,i);
		}
	}
	

	return 0;
} 

这篇关于图的深度优先算法和广度优先算法的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！