adjgraphsearch.h

《数据结构-使用C语言》第三版

//深度优先遍历  邻接矩阵存储结构 
void DepthFSearch(AdjMGraph G , int v, int visited[], void Visit(DataType Item))
{
	DataType w;
	Visit(G.Vertices.list[v]);
	visited[v]=1;
	
	w=GetFirstVex(G,v);
	while(w!=-1)
	{
		if(!visited[w])
		DepthFSearch(G, w, visited, Visit);
		w=GetNextVex(G, v, w);
	}
}

void DepthFirstSearch(AdjMGraph G, void Visit(DataType item))
{
	int i;
	int *visited=(int *)malloc(sizeof(int)*G.Vertices.size);
	
	for(i=0;i<G.Vertices.size;i++)
	visited[i]=0;
	
	for(i=0;i<G.Vertices.size;i++)
	if(!visited[i])
		DepthFSearch(G, i, visited, Visit);
		
	free(visited);
}

//广度优先遍历  邻接矩阵存储结构 
#include"SeqCQueue.h"
void BroadFSearch(AdjMGraph G, int v, int visited[], void Visit(DataType item))
{
	DataType u, w;
	int cin=1;
	SeqCQueue queue;
	
	Visit(G.Vertices.list[v]);
	visited[v]=1;
	
	QueueInitiate(&queue);
	QueueAppend(&queue, v);
	while(cin<G.Vertices.size)
	//while(QueueNotEmpty(queue))
	{
		QueueDelete(&queue,&u);
		w=GetFirstVex(G, u);
		while(w!=-1)
		{
			if(!visited[w])
			{
				Visit(G.Vertices.list[w]);
				visited[w]=1;
				QueueAppend(&queue, w);
				cin++;
			}
			w=GetNextVex(G, u, w);
		}
	}
}

void BroadFirstSearch(AdjMGraph G, void Visit(DataType item))
{
	int i;
	int *visited=(int *)malloc(sizeof(int)*G.Vertices.size);
	
	for(i=0;i<G.Vertices.size;i++)visited[i]=0;
	
	for(i=0;i<G.Vertices.size;i++)
	if(!visited[i])BroadFSearch(G, i, visited, Visit);
	
	free(visited);
}

//"深广度"优先搜索  邻接矩阵存储结构  非递归算法
#include"SeqStack.h"
void BDepthFSearch(AdjMGraph G , int v, int visited[], void Visit(DataType Item))
{
	DataType u, w;
	int cin=1; 
	SeqStack Vertexs;
	
	Visit(G.Vertices.list[v]);
	visited[v]=1;
	
	StackInitiate(&Vertexs);
	StackPush(&Vertexs, v);
	
	while(cin<G.Vertices.size)
	//while(StackNotEmpty(Vertexs))
	{
		StackPop(&Vertexs, &u);
		w=GetFirstVex(G,u);
		while(w!=-1 )
		{
			if(!visited[w])
			{
				Visit(G.Vertices.list[w]);
				visited[w]=1;
				StackPush(&Vertexs, w);
				cin++;
			}
			w=GetNextVex(G,u,w);
		}
	}
}

void BDepthFirstSearch(AdjMGraph G, void Visit(DataType item))
{
	int i;
	int *visited=(int *)malloc(sizeof(int)*G.Vertices.size);
	
	for(i=0;i<G.Vertices.size;i++)
	visited[i]=0;
	
	for(i=0;i<G.Vertices.size;i++)
	if(!visited[i])
		BDepthFSearch(G, i, visited, Visit);
		
	free(visited);
}

//深度优先遍历  邻接矩阵存储结构  非递归算法
void No_DepthFSearch(AdjMGraph G , int v, int visited[], void Visit(DataType Item))
{
	DataType u, w;
	int cin=1; 
	SeqStack Vertexs;
	
	Visit(G.Vertices.list[v]);
	visited[v]=1;
	
	StackInitiate(&Vertexs);
	StackPush(&Vertexs, v);
	u=v;
	while(cin<G.Vertices.size)
	//while(StackNotEmpty(Vertexs))
	{
		w=GetFirstVex(G,u);
		while(w!=-1)
		{
			if(!visited[w])break;
			w=GetNextVex(G,u,w);
		}
		if(w!=-1 && !visited[w])
		{
			Visit(G.Vertices.list[w]);
			visited[w]=1;
			StackPush(&Vertexs, w);
			u=w;
			cin++;
		}
		else StackPop(&Vertexs, &u);
		StackTop(Vertexs, &u);
	}
}

void No_DepthFirstSearch(AdjMGraph G, void Visit(DataType item))
{
	int i;
	int *visited=(int *)malloc(sizeof(int)*G.Vertices.size);
	
	for(i=0;i<G.Vertices.size;i++)
	visited[i]=0;
	
	for(i=0;i<G.Vertices.size;i++)
	if(!visited[i])
		No_DepthFSearch(G, i, visited, Visit);
	//No_DepthFSearch(G, 0, visited, Visit);
		
	free(visited);
}