赞
踩
本文采用邻接表法存储图,具体结构如下:
typedef struct Edge { int weight; int vertexIndex; struct Edge *next; } *Edge; typedef struct Vertex { void *data; Edge firstEdge; } *Vertex, *VertexList; struct AdjacentListGraph { VertexList *vertexList; int vertexCount; int edgeCount; int size; int (*compare)(void *, void *); };
深度优先遍历(DFS)的算法思想是:
void DFS(AdjacentListGraph graph, int vertexIndex, bool isVisited[], LinkedQueue DFSDataQueue) { Vertex vertex = graph->vertexList[vertexIndex - 1]; linkedQueueEnQueue(DFSDataQueue, vertex->data); isVisited[vertexIndex - 1] = true; for (Vertex j = firstVertex(graph, vertex->data); j != NULL; j = nextVertex(graph, vertex->data, j->data)) { int index = getVertexIndex(graph, j->data); if (!isVisited[index - 1]) { DFS(graph, index, isVisited, DFSDataQueue); } } } /** * 深度优先遍历 * @param graph 图 * @param data 起始结点 * @param DFSDataQueue 用于保存遍历顶点 */ void DFSTraverse(AdjacentListGraph graph, void *data, LinkedQueue DFSDataQueue) { bool *isVisited = calloc(graph->vertexCount, sizeof(bool)); int index = getVertexIndex(graph, data); DFS(graph, index, isVisited, DFSDataQueue); for (int i = 1; i <= graph->vertexCount; ++i) { if (!isVisited[i - 1]) { DFS(graph, i, isVisited, DFSDataQueue); } } }
逆拓扑排序的算法思想如下:
没有后继的顶点就是在深度优先遍历递归函数出栈时的点,所以只需要在每次函数出栈时将当前顶点输出到遍历队列即可:
void DFS(AdjacentListGraph graph, int index, bool isVisited[], LinkedQueue queue) { isVisited[index - 1] = true; Vertex vertex = graph->vertexList[index - 1]; for (Edge edge = vertex->firstEdge; edge != NULL; edge = edge->next) { if (!isVisited[edge->vertexIndex - 1]) { DFSInTopological(graph, edge->vertexIndex, isVisited, queue); } } linkedQueueEnQueue(queue, vertex->data); } /** * 深度优先算法求逆拓扑排序 * @param graph * @param queue */ void DFSInTopologicalSort(AdjacentListGraph graph, LinkedQueue queue) { bool *isVisited = calloc(graph->vertexCount, sizeof(bool)); for (int i = 1; i <= graph->vertexCount; ++i) { if (!isVisited[i - 1]) { DFS(graph, i, isVisited, queue); } } }
拓扑排序算法可以用于检测图中是否含有环:如果拓扑序列中含有所有图中的结点,那么该图就没有环,否则就含有环。但是使用DFS改造的算法即使传入的图有环,拓扑序列中也包含所有图中的顶点。那么就该解决这个问题,解决思想如下:
isVisited
数组来标记是否已经访问过该顶点,只需要将其改成一个整型数组,并且有以下值:
isVisited
数组的值设置为2,然后在该函数出栈时再设置为1,在函数运行的时候如果再次访问到了该顶点,只需要判断该顶点的isVisited
数组是否是2就可以知道有没有环了。void DFS(AdjacentListGraph graph, int index, int isVisited[], LinkedQueue queue) { isVisited[index - 1] = 2; Vertex vertex = graph->vertexList[index - 1]; for (Edge edge = vertex->firstEdge; edge != NULL; edge = edge->next) { if (isVisited[edge->vertexIndex - 1] == 0) { DFS(graph, edge->vertexIndex, isVisited, queue); } if (isVisited[edge->vertexIndex - 1] == 2) { throw Error(CYCLIC_GRAPH_ERROR, "图中含有环,逆拓扑排序失败"); } } isVisited[index - 1] = 1; linkedQueueEnQueue(queue, vertex->data); } /** * 深度优先算法求逆拓扑排序 * @param graph * @param queue */ void DFSInTopologicalSort(AdjacentListGraph graph, LinkedQueue queue) { int *isVisited = calloc(graph->vertexCount, sizeof(bool)); for (int i = 1; i <= graph->vertexCount; ++i) { if (isVisited[i - 1] == 0) { DFS(graph, i, isVisited, queue); } } }
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。