１、digraph.h
#ifndef _DIGRAPH_H_H
#define _DIGRAPH_H_H
#define ENABLE_DIGRAPH_TEST 0
#define CHECK_NULL_AND_RET(x) { if((x) == NULL) return -1; }
typedef struct _ADJ_ENTRY
{
int adjoinPoint;
struct _ADJ_ENTRY* pNext;
} ADJ_ENTRY;
typedef struct
{
struct _ADJ_ENTRY* entryHead;
} ADJ_HEAD;
typedef struct
{
int V; //顶点数
int E; //边数
ADJ_HEAD* adjTable; //邻接表
} DIGRAPH;
int digraphCreate(DIGRAPH *pDigraph, int V);
int reverseDigraphCreate(DIGRAPH* pSrcDigraph, DIGRAPH* pDstDigraph);
int digraphDestroy(DIGRAPH *pDigraph);
int V(DIGRAPH *pDigraph);
int E(DIGRAPH *pDigraph);
int addEdge(DIGRAPH *pDigraph, int x, int y);
void showDigraph(DIGRAPH *pDigraph);
#endif
２、digraph.c
#include <stdio.h>
#include <stdlib.h>
#include "digraph.h"
//有向图的数据结构
//当前图对象使用邻接表表示，大部分情况下，图中的所有顶点并非
//都是关联的，这种叫作稀疏图，使用邻接表来做为稀疏图的数据结
//构，可以节省很大的内存空间。如果以前了解过操作系统原理中内
//存机制的一级页表、二级页表机制，就会很快明白，为什么使用邻
//接表来表示稀疏图可以节省大部内存空间了。
//创建图对象，其中Ｖ表示最大顶点个数
int digraphCreate(DIGRAPH *pDigraph, int V)
{
if ( pDigraph == NULL )
{
return -1;
}
pDigraph->V = V;
pDigraph->E = 0;
pDigraph->adjTable = (ADJ_HEAD *)malloc(sizeof(ADJ_HEAD) * V);
CHECK_NULL_AND_RET(pDigraph->adjTable);
return 0;
}
//创建反向图
int reverseDigraphCreate(DIGRAPH* pSrcDigraph, DIGRAPH* pDstDigraph)
{
int i = 0;
if ( pSrcDigraph == NULL || pDstDigraph == NULL )
{
return -1;
}
if ( digraphCreate(pDstDigraph, V(pSrcDigraph)) < 0 )
{
return -1;
}
for ( i = 0; i < V(pSrcDigraph); i++ )
{
ADJ_ENTRY* pCurAdjEntry = (pSrcDigraph->adjTable + i)->entryHead;
while ( pCurAdjEntry != NULL )
{
addEdge(pDstDigraph, pCurAdjEntry->adjoinPoint, i);
pCurAdjEntry = pCurAdjEntry->pNext;
}
}
return 0;
}
//销毁图对象
int digraphDestroy(DIGRAPH *pDigraph)
{
int i = 0;
if ( pDigraph == NULL )
{
return -1;
}
for ( i = 0; i < V(pDigraph); i++ )
{
ADJ_ENTRY *pCurAdjEntry = (pDigraph->adjTable + i)->entryHead;
while ( pCurAdjEntry != NULL )
{
ADJ_ENTRY *pFreeAdjEntry = pCurAdjEntry;
pCurAdjEntry = pCurAdjEntry->pNext;
free(pFreeAdjEntry);
}
}
free(pDigraph->adjTable);
pDigraph->V = 0;
pDigraph->E = 0;
pDigraph->adjTable = NULL;
return 0;
}
//获取图对象的顶点个数
int V(DIGRAPH *pDigraph)
{
if ( pDigraph == NULL )
{
return -1;
}
return pDigraph->V;
}
//获取图对象的边数
int E(DIGRAPH *pDigraph)
{
if ( pDigraph == NULL )
{
return -1;
}
return pDigraph->E;
}
//邻接表添加条目
static int adjAdd(DIGRAPH *pDigraph, int x, int y)
{
ADJ_HEAD *pAdjHead = NULL;
ADJ_ENTRY *pNewAdjEntry = NULL;
if ( pDigraph == NULL )
{
return -1;
}
if ( x >= pDigraph->V || x < 0 || y >= pDigraph->V || y < 0 )
{
return -1;
}
pNewAdjEntry = (ADJ_ENTRY *)malloc(sizeof(ADJ_ENTRY));
CHECK_NULL_AND_RET(pNewAdjEntry);
memset(pNewAdjEntry, 0, sizeof(ADJ_ENTRY));
pNewAdjEntry->adjoinPoint = y;
pAdjHead = (pDigraph->adjTable + x);
pNewAdjEntry->pNext = pAdjHead->entryHead;
pAdjHead->entryHead = pNewAdjEntry;
return 0;
}
//向图对象中增加路径
int addEdge(DIGRAPH *pDigraph, int x, int y)
{
if ( adjAdd(pDigraph, x, y) < 0 )
{
return -1;
}
pDigraph->E++;
return 0;
}
//显示图对象的信息
void showDigraph(DIGRAPH *pDigraph)
{
int i = 0;
if ( pDigraph == NULL )
{
return;
}
printf("point count: %d\r\n", V(pDigraph));
printf("edge count: %d\r\n", E(pDigraph));
printf("------------------\r\n");
for ( i = 0; i < V(pDigraph); i++ )
{
ADJ_ENTRY* pCurEntry = (pDigraph->adjTable + i)->entryHead;
while ( pCurEntry != NULL )
{
printf("%d --> %d\r\n", i, pCurEntry->adjoinPoint);
pCurEntry = pCurEntry->pNext;
}
}
printf("------------------\r\n");
}
#if ENABLE_DIGRAPH_TEST
int main()
{
DIGRAPH digraphObj = {0};
DIGRAPH reverseDigraphObj = {0};
digraphCreate(&digraphObj, 10);
addEdge(&digraphObj, 0, 1);
addEdge(&digraphObj, 0, 2);
addEdge(&digraphObj, 0, 3);
addEdge(&digraphObj, 0, 4);
showDigraph(&digraphObj);
reverseDigraphCreate(&digraphObj, &reverseDigraphObj);
showDigraph(&reverseDigraphObj);
digraphDestroy(&digraphObj);
digraphDestroy(&reverseDigraphObj);
return 0;
}
#endif
３、digraphCycle.c
#include "stdio.h"
#include "digraph.h"
#define CHECK_NULL_RET(x) { if ( (x) == NULL ) return -1; }
enum
{
FALSE,
TRUE
} E_BOOL;
int* gMarked = NULL;
int* gOnStack = NULL;
int gIsCycle = FALSE;
//基于深度优先算法实现的有向图环路检测
void dfs(DIGRAPH* pDigraph, int s)
{
ADJ_ENTRY* pCurAdjEntry = NULL;
if ( s < 0 || s >= V(pDigraph) )
{
printf("invalid s %d\r\n", s);
return;
}
gMarked[s] = TRUE;
gOnStack[s] = TRUE;
pCurAdjEntry = (pDigraph->adjTable + s)->entryHead;
while ( pCurAdjEntry != NULL )
{
if ( !gMarked[pCurAdjEntry->adjoinPoint] )
{
dfs(pDigraph, pCurAdjEntry->adjoinPoint);
}
else if ( gOnStack[pCurAdjEntry->adjoinPoint] )
{
gIsCycle = TRUE;
return;
}
pCurAdjEntry = pCurAdjEntry->pNext;
}
//注意这里gOnStack与gMarked的区别，gMarked是深度优先算法所使用的
//标记，记录当前该点是否走过，如果走过就选择其它点进行尝试。
//而gOnStack表示从源点到当前点的路径，如果在遇到每条路不通的情况下，
//需要退回到上个点，这时候gOnStack中就要撤销标记，如下示例，当走到
//3的时候，此时gOnStack和gMarked一样，0～3的数组索引都标为TRUE，
//但这时候已经没有路，需要退回到2，此时gOnStack[3]则为FALSE，这时候
//发现２也没有其它可走的路，则退回到1，此时gOnStack[2]则为FALSE，
//当从1走到4的时候，gOnStack只有索引0、１、４为TRUE，而gMarked则
//索引0~4都为TRUE。
//
//示例：
//0 --> 1 --> 2 --> 3
// |
// |---> 4 --> 5
gOnStack[s] = FALSE;
}
int main()
{
int size = 0;
DIGRAPH digraphObj = {0};
//创建有向图对象
digraphCreate(&digraphObj, 5);
#if 0
addEdge(&digraphObj, 0, 1);
addEdge(&digraphObj, 0, 2);
addEdge(&digraphObj, 1, 3);
addEdge(&digraphObj, 2, 3);
addEdge(&digraphObj, 3, 4);
#else
addEdge(&digraphObj, 0, 1);
addEdge(&digraphObj, 0, 2);
addEdge(&digraphObj, 1, 3);
addEdge(&digraphObj, 2, 3);
addEdge(&digraphObj, 3, 0);
#endif
showDigraph(&digraphObj);
//资源分配
size = sizeof(int) * V(&digraphObj);
gMarked = (int *)malloc(size);
CHECK_NULL_RET(gMarked);
memset(gMarked, 0, size);
gOnStack = (int *)malloc(size);
CHECK_NULL_RET(gOnStack);
memset(gOnStack, 0, size);
//基于深度优先算法实现的有向图环路检测
dfs(&digraphObj, 0);
printf("Cycle: %s\r\n", gIsCycle ? "TRUE" : "FALSE" );
//资源销毁
free(gMarked);
free(gOnStack);
digraphDestroy(&digraphObj);
return 0;
}