邻接表实现--图的拓扑排序

     有向图的拓扑排序是基础算法，也是很重要的一个算法。

     它的思路如下：

      （1）统计所有顶点的入度，接着把入度为0的全部入栈或者入队列。

      （2）取出栈顶元素，或者队列的首个元素，标记该顶点为"已访问"状态。

               接着删除该顶点与其它顶点的联系，即把其它相邻顶点的入度减少1。相邻顶点中，入度减少1之后，如果存在入度为0的新顶点，把新顶点入栈或者入队列。

      （3）第二步一直循环处理，知道栈为空或者队列为空。

      （4）判断是否所有的顶点都访问过了。如果存在某些顶点未访问过，那边该图至少存在一个环，那么拓扑排序就不存在。

      我这里使用邻接表和栈实现。OK，测试结果和代码如下：

       

       

#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 TopologySort(PLINKED_GRAPH graph);
void TestTopology();

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

BOOL AllVertexHasVisited(PLINKED_GRAPH graph)
{
	for(int i=0;i<graph->vertexCount;i++)
	{
		if(!graph->visitFlag[i])
		{
			return FALSE;
		}
	}

	return TRUE;
}

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 TopologySort(PLINKED_GRAPH graph)
{
	int inDegree[MAX_VERTEX] = {0};
	//由于这里暂时只有出度表，要先通过出度表计算每个顶点的入度
	for(int i=0;i<graph->vertexCount;i++)
	{
		PARC_NODE p = graph->vertex[i].outHead;
		while(p)
		{
			inDegree[p->index]++;
			p = p->next;
		}
	}

	stack<int> s; //栈用于存放入度为0的栈
	//入度为0的顶点先入栈
	for(int i=0;i<graph->vertexCount;i++)
	{
		if(0 == inDegree[i])
		{
			s.push(i);
		}
	}

	while(!s.empty())
	{
		int vertexIndex = s.top();
		s.pop();//出栈
		Visit(graph,vertexIndex);

		//对该顶点的出度表中的每个邻接顶点，他们的入度都减少1
		PARC_NODE p = graph->vertex[vertexIndex].outHead;
		while(p)
		{
			inDegree[p->index]--;//入度减少1
			//如果出现了入度为0的顶点，则入栈
			if(0 == inDegree[p->index])
			{
				s.push(p->index);
			}
			p = p->next;
		}
	}

	if(AllVertexHasVisited(graph))
	{
		printf("\r\nTopology Sort Success!This Graph has no loop!\r\n");
	}
	else
	{
		printf("\r\nTopology Sort Fail!!!This Graph has loop!\r\n");
	}
}