欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

邻接表实现--图的深度优先遍历DFS和广度优先遍历BFS

程序员文章站 2022-05-21 23:06:16
...

          图论中一个基本的概念就是遍历。就是访问到图的每一个顶点,同时每个顶点只访问一次。

          DFS和BFS的概念和思路网上说明的很详细了。但是网上很多代码实现有缺陷,基本都没有考虑图不连通的情况,比如某个顶点A和其它任何一个顶点都不关联,那么这个顶点A就访问不到了。如果遍历的起点刚好是孤立的顶点A,就只能访问顶点A了,其它顶点就访问不到了。

          我这边的代码就是增加了这些情况的处理,确保每个顶点都能可以访问到。

          完整的代码如下(通过邻接表实现图):

#define MAX_VERTEX 16

typedef enum
{
	UNDIRECTED_GRAPH = 0, //无向图
	DIRECTED_GRAPH = 1, //有向图
	UNDIRECTED_NET = 2, //无向网
	DIRECTED_NET = 3, //有向网
}GRAPH_TYPE;

typedef struct _ARC_NODE
{
	int index; //邻接顶点在顶点数组中的索引值
	struct _ARC_NODE* next;//指向下一个相邻顶点
}ARC_NODE,*PARC_NODE;

typedef struct _VERTEX
{
	char data;//顶点数据值
	PARC_NODE outHead;//出边表头指针
	PARC_NODE inHead; //入边表头指针
}VERTEX,*PVERTEX;

typedef struct
{
	GRAPH_TYPE type; //图的类型
	int vertexCount;//顶点个数
	BOOL visitFlag[MAX_VERTEX];
	VERTEX vertex[MAX_VERTEX]; 
}LINKED_GRAPH,*PLINKED_GRAPH; //邻接表方式的图或者网

void DFS(PLINKED_GRAPH graph,int startVertexIndex);
void BFS(PLINKED_GRAPH graph,int startVertexIndex);


void Visit(PLINKED_GRAPH graph,int vIndex)
{
	graph->visitFlag[vIndex] = TRUE; //设置已访问标志
	printf("Visit Vertex: %c\r\n",graph->vertex[vIndex].data);
}

void InitVistFlag(PLINKED_GRAPH graph)
{
	for(int i=0;i<graph->vertexCount;i++)
	{
		graph->visitFlag[i] = FALSE;
	}
}

void DFS(PLINKED_GRAPH graph,int startVertexIndex)
{
	stack<int> s; //访问栈
	s.push(startVertexIndex);
	while(!s.empty())
	{
		int vertexIndex = s.top();
		if(!graph->visitFlag[vertexIndex])//未访问过
		{
			Visit(graph,vertexIndex);
		}

		s.pop();//vertexIndex顶点出栈

		//这里我们通过出度表来遍历
		PARC_NODE p = graph->vertex[vertexIndex].outHead;
		while(p)
		{
			//与vertexIndex相邻的顶点并且未访问过的顶点全部入栈
			if(!graph->visitFlag[p->index])
			{
				s.push(p->index);
			}
			p = p->next;//指向下一个与vertexIndex相邻的顶点
		}
	}

	//图并不一定是连通的,因此要确保每个顶点都遍历过
	for(int i=0;i<graph->vertexCount;i++)
	{
		if(!graph->visitFlag[i])
		{
			printf("Not Connected vertex start DFS: %c\r\n",graph->vertex[i]);
			DFS(graph,i);
		}
	}
}

void BFS(PLINKED_GRAPH graph,int startVertexIndex)
{
	queue<int> q; //访问队列
	q.push(startVertexIndex);//起始访问的顶点入队

	while(!q.empty())
	{
		int vertexIndex = q.front();
		if(!graph->visitFlag[vertexIndex])//未访问过
		{
			Visit(graph,vertexIndex);
		}

		q.pop();//vertexIndex顶点出队

		//这里我们通过出度表来遍历
		PARC_NODE p = graph->vertex[vertexIndex].outHead;
		while(p)
		{
			//与vertexIndex相邻的顶点并且未访问过的顶点全部入队
			if(!graph->visitFlag[p->index])
			{
				q.push(p->index);
			}
			p = p->next;//指向下一个与vertexIndex相邻的顶点
		}
	}

	//图并不一定是连通的,因此要确保每个顶点都遍历过
	for(int i=0;i<graph->vertexCount;i++)
	{
		if(!graph->visitFlag[i])
		{
			printf("Not Connected vertex start BFS: %c\r\n",graph->vertex[i]);
			BFS(graph,i);
		}
	}
}

void InitLinkedGraph(PLINKED_GRAPH graph)
{
	graph->type = UNDIRECTED_GRAPH; //无向图
	graph->vertexCount = 10;
	for(int i=0;i<graph->vertexCount;i++)
	{
		graph->vertex[i].data = 'A'+i; //顶点为'A','B','C'等等
	}

	graph->vertex[0].outHead = new ARC_NODE;
	graph->vertex[0].outHead->index = 1; //AB有边
	graph->vertex[0].outHead->next = new ARC_NODE;
	graph->vertex[0].outHead->next->index = 4;//AE有边
	graph->vertex[0].outHead->next->next = NULL;

	graph->vertex[1].outHead = new ARC_NODE;
	graph->vertex[1].outHead->index = 0; //BA有边
	graph->vertex[1].outHead->next = new ARC_NODE;
	graph->vertex[1].outHead->next->index = 3;//BD有边
	graph->vertex[1].outHead->next->next = NULL;

	graph->vertex[2].outHead = new ARC_NODE;
	graph->vertex[2].outHead->index = 4; //CE有边
	graph->vertex[2].outHead->next = new ARC_NODE;
	graph->vertex[2].outHead->next->index = 5;//CF有边
	graph->vertex[2].outHead->next->next = new ARC_NODE;
	graph->vertex[2].outHead->next->next->index = 6;//CG有边
	graph->vertex[2].outHead->next->next->next = new ARC_NODE;
	graph->vertex[2].outHead->next->next->next->index = 7; //CG有边
	graph->vertex[2].outHead->next->next->next->next = NULL;

	graph->vertex[3].outHead = new ARC_NODE;
	graph->vertex[3].outHead->index = 1; //DB有边
	graph->vertex[3].outHead->next = NULL;

	graph->vertex[4].outHead = new ARC_NODE;
	graph->vertex[4].outHead->index = 2; //EC有边
	graph->vertex[4].outHead->next = NULL;

	graph->vertex[5].outHead = new ARC_NODE;
	graph->vertex[5].outHead->index = 2; //FC有边
	graph->vertex[5].outHead->next = NULL;

	graph->vertex[6].outHead = new ARC_NODE;
	graph->vertex[6].outHead->index = 2; //GC有边
	graph->vertex[6].outHead->next = new ARC_NODE;
	graph->vertex[6].outHead->next->index = 8;//GI有边
	graph->vertex[6].outHead->next->next = new ARC_NODE;
	graph->vertex[6].outHead->next->next->index= 9;//GJ有边
	graph->vertex[6].outHead->next->next->next = NULL;

	graph->vertex[7].outHead = new ARC_NODE;
	graph->vertex[7].outHead->index = 2; //HC有边
	graph->vertex[7].outHead->next = NULL;

	graph->vertex[8].outHead = new ARC_NODE;
	graph->vertex[8].outHead->index = 6; //IG有边
	graph->vertex[8].outHead->next = NULL;

	graph->vertex[9].outHead = new ARC_NODE;
	graph->vertex[9].outHead->index = 6; //JG有边
	graph->vertex[9].outHead->next = NULL;
}

void PrintLinkedGraph(PLINKED_GRAPH graph)
{
	printf("Linked Graph Info:\r\n");
	for(int i=0;i<graph->vertexCount;i++)
	{
		printf("%2c",graph->vertex[i].data);
		PARC_NODE p = graph->vertex[i].outHead;
		while(p)
		{
			printf(" --> %2c",graph->vertex[p->index].data);
			p = p->next;
		}
		printf("\r\n");
	}
	printf("\r\n");
}

void DestroyLinkedGraph(PLINKED_GRAPH graph)
{
	for(int i=0;i<graph->vertexCount;i++)
	{
		PARC_NODE p = graph->vertex[i].outHead;
		while(p)
		{
			PARC_NODE pNext = p->next;

			p->next = NULL;
			delete p;

			p = pNext;
		}
	}
}

void TestLinkedGraph()
{
	LINKED_GRAPH graph = {UNDIRECTED_GRAPH,0};
	InitLinkedGraph(&graph);
	InitVistFlag(&graph);
	PrintLinkedGraph(&graph);

	printf("Linked Graph DFS:\r\n");
	DFS(&graph,0);
	printf("\r\n");

	InitVistFlag(&graph);
	printf("Linked Graph DFS:\r\n");
	BFS(&graph,0);
	printf("\r\n");

	DestroyLinkedGraph(&graph);
}

相关标签: dfs bfs 邻接表