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

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

          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);
}