graph.c

操作系统中的一个例子

        if ( nControlFlag == 0 )
        {
            /* 步骤2：给顶点标上DFS编码 */
            nDfsCode++;
            pCurrentNode->nMagic = nDfsCode;
        }
        else
        {
            nControlFlag = 0;
        }

        pEdge = NULL;
        /* 步骤3：查找未用过的关联边 */
        while ((pData = SingleList_EnumNext(pCurrentNode->pEdgeList)) != NULL)
        {         
            pEdge = (EDGE *)pData;

            if ( pEdge->nMagic == GRAPH_EDGE_NOT_SEARCH )
            {
                break;
            }
        }

        if ( pData == NULL )
        {
            pEdge = NULL;
        }

        if ( NULL != pEdge ) /* 判断是否找到未用过的边 */
        {
            GRAPHNODE   *pNextNode;

            /* 步骤4：已经找到了一条未用过的关联边 */

            /* 取出当前边的相邻节点放到pNextNode中 */
            if ( pEdge->pNode1 == pCurrentNode )
            {
                pNextNode = pEdge->pNode2;
            }
            else
            {
                pNextNode = pEdge->pNode1;
            }

            /* 判断相邻节点的DFS编码是否为0 */
            if ( pNextNode->nMagic == 0 )
            {
                pEdge->nMagic = GRAPH_EDGE_SEARCHED; /* 将此边标示为用过 */

                /* 将当前节点作为搜索到的节点的父节点 */
                pNextNode->pMagic = pCurrentNode; 
                /* 将当前节点指针指向搜索到的相邻节点 */
                pCurrentNode = pNextNode;   

                nControlFlag = 0;

                if ( EdgeDumpFunc )
                {
                    (*EdgeDumpFunc)(pEdge);
                }

                continue;   /* 转步骤2 */
            }
            else
            {
                /* 此边已经搜索过但不在生成树中 */
                pEdge->nMagic = GRAPH_EDGE_NOT_TREE; 

                if ( EdgeDumpFunc )
                {
                    (*EdgeDumpFunc)(pEdge);
                }

                nControlFlag = 1;
                /* 转步骤3 */
            }

            if ( pEdge == pTagEdge)
            {
                return 2;
            }
        }
        else
        {
            /* 步骤5：如果当前节点编码为1即到了pOrgNode，则已经搜索完毕需中止*/
            if ( pCurrentNode->nMagic == 1 )
            {
                break;
            }

            /* 步骤6：回溯到父节点转步骤3继续查找 */
            pCurrentNode = pCurrentNode->pMagic;

            nControlFlag = 1;
            continue; /* 转步骤3 */
        }
    }
    return 1;
}



/**	图的宽度优先搜索函数
        搜索完后, 节点的nMagic用来存放BFS编码
        节点的pMagic用来存放下一个被搜索到的节点的指针, 因此由pMagic可以得到搜索的
        节点顺序, 边的nMagic是用来存放是否被搜索的标志, 标志为GRAPH_EDGE_SEARCHED
        的边构成一颗生成树, 树的根节点为搜索起点

	@param	LPGRAPH pGraph - 要搜索的图	
	@param	LPGRAPHNODE pOrgNode - 要搜索的起点	
	@param	LPGRAPHNODE pTagNode - 要搜索的目标节点	
	@param	GRAPHNODEDUMPFUNC GraphNodeDumpFunc - 顶点回调函数	
	@param	EDGEDUMPFUNC EdgeDumpFunc - 边回调函数	
	@return	INT - 0表示失败, 1表示搜索完成, 2表示搜索到指定目标节点pTagNode	
*/
INT Graph_BreadFirstSearch(LPGRAPH pGraph, 
                       LPGRAPHNODE pOrgNode,
                       LPGRAPHNODE pTagNode,
                       GRAPHNODEDUMPFUNC GraphNodeDumpFunc,
                       EDGEDUMPFUNC EdgeDumpFunc)
{
    INT         nBfsCode;       /* BFS编码 */
    GRAPHNODE   *pCurrentNode;  /* 记录当前要操作的节点 */
    GRAPHNODE   *pLastNode;     /* 记录最后一个要操作的节点 */
    INT         i;
    SINGLENODE    *pTmpNode;

    for ( i = 0; i < pGraph->nNodeCount; i++ )
    {
        /* nMagic在此算法中是用来记录节点的BFS编码 */
        pGraph->ppNodeArray[i]->nMagic = -1;  /* 初始化为-1表示还没有编码 */
        
        /* pMagic在此算法中是用力将已搜索到但未对本节点进行搜索的节点形成链表*/
        pGraph->ppNodeArray[i]->pMagic = NULL;  
    }

    pTmpNode = pGraph->pEdgeList->pHead;
    while ( NULL != pTmpNode )
    {
        EDGE    *pEdge;
        pEdge = (EDGE *)pTmpNode->pData;
        pEdge->nMagic = GRAPH_EDGE_NOT_SEARCH; 
        pTmpNode = pTmpNode->pNext;
    }


    nBfsCode = 0;               /* 初始化为0 */
    pCurrentNode = pOrgNode;
    pCurrentNode->nMagic = nBfsCode;  /* nMagic用来记录BFS编码 */

    pLastNode = pOrgNode;

    while ( NULL != pCurrentNode )
    {
        SINGLENODE    *pListNode;
        nBfsCode = pCurrentNode->nMagic + 1;

        pListNode = pCurrentNode->pEdgeList->pHead;
        while ( NULL != pListNode )
        {
            EDGE        *pEdge;
            GRAPHNODE   *pNode;

            pEdge = (EDGE *)pListNode->pData;
            
            pListNode = pListNode->pNext;

            if ( pEdge->nMagic != GRAPH_EDGE_NOT_SEARCH )
            {
                /* 边已经被搜索过了 */
                continue;
            }

            if ( pEdge->pNode2 == pCurrentNode )
            {
                pNode = pEdge->pNode1;
            }
            else
            {
               pNode = pEdge->pNode2;
            }
            
            if ( pNode->nMagic == -1 )  /* 等于-1表示节点还未编码 */
            {
                pNode->nMagic = nBfsCode;

                pLastNode->pMagic = pNode;
                pLastNode = pNode;

                pEdge->nMagic = GRAPH_EDGE_SEARCHED;

                if ( GraphNodeDumpFunc )
                {
                    /* 对顶点执行回调函数 */
                    (*GraphNodeDumpFunc)(pNode);
                }
                if ( pNode == pTagNode )
                {
                    return 2;
                }
            }
            else
            {
                pEdge->nMagic = GRAPH_EDGE_NOT_TREE;
            }
            /* 调用边的回调函数 */
            if ( EdgeDumpFunc )
            {
                (*EdgeDumpFunc)(pEdge);
            }

        }
        /* 将当前节点指向下一个未搜索节点 */
        pCurrentNode = pCurrentNode->pMagic;
    }
    return 1;
}

/**	距离比较函数

	@param	void *p1 - 要比较的边指针1	
	@param	void *p2 - 要比较的边指针2	
	@return	INT - 1表示p1的距离大于p2的距离
                  0表示p1的距离等于p2的距离
                  -1表示p1的距离小于p2的距离
*/
INT DistanceCompare(void *p1, void *p2)
{
    EDGE    *pEdge1;
    EDGE    *pEdge2;

    pEdge1 = (EDGE *)p1;
    pEdge2 = (EDGE *)p2;

    if ( pEdge1->distance > pEdge2->distance )
    {
        return 1;
    }
    else if ( pEdge1->distance < pEdge2->distance )
    {
        return -1;
    }
    return 0;
}

/**	图的边排序函数，对所有边使用归并排序算法进行排序

	@param	LPGRAPH pGraph - 图指针	
	@return	INT - CAPI_SUCCESS表示成功，CAPI_FAILED表示失败。	
*/
INT Graph_SortEdgeInOrder(LPGRAPH pGraph)
{
    if ( NULL == pGraph )
    {
        return CAPI_FAILED;
    }
    return SingleList_MergeSort(pGraph->pEdgeList, DistanceCompare, 32);
}


/**	利用Kruskal算法求最小生成树
        计算过程中,节点的nMagic用来记录父顶点编号
        计算完后, nMagic为GRAPH_EDGE_SEARCHED的边组成一颗最小生成树

	@param	LPGRAPH pGraph - 要求最小生成树的图	
	@return	INT - CAPI_FAILED表示失败, 1表示成功	
*/
INT Graph_GetMinTree(LPGRAPH pGraph)
{
    SINGLENODE    *pEdgeListNode;
    INT         i;
    INT         *pNodeNo; /* 用来记录所有节点父节点号便于进行成环的判断 */

    if ( NULL == pGraph )
    {
        return CAPI_FAILED;
    }

    pNodeNo = (INT *)malloc(pGraph->nNodeCount * sizeof(INT));
    if ( NULL == pNodeNo )
    {
        return CAPI_FAILED;
    }

    /* 初始化所有节点的nMagic为节点编号, 父节点号为-1表示还没有加入到生成树中 */
    for ( i = 0; i < pGraph->nNodeCount; i++ )
    {
        pGraph->ppNodeArray[i]->nMagic = i;
        pNodeNo[i] = -1; /* 初始化所有节点的父节点号为-1表示还没有计算过 */
    }

    Graph_SortEdgeInOrder(pGraph);
    
    /* 初始化所有边的nMagic为GRPAH_EDGE_NOT_SEARCH */
    pEdgeListNode = pGraph->pEdgeList->pHead;
    while ( NULL != pEdgeListNode )
    {
        EDGE        *pEdge;
        pEdge = (EDGE *)pEdgeListNode->pData;

        pEdge->nMagic = GRAPH_EDGE_NOT_SEARCH;

        pEdgeListNode = pEdgeListNode->pNext;

    }

    pEdgeListNode = pGraph->pEdgeList->pHead;
    while ( NULL != pEdgeListNode )
    {
        EDGE        *pEdge;
        INT         bnf;    /* 一条边开始顶点的父节点编号 */
        INT         edf;    /* 一条边结束顶点的父节点编号 */

        pEdge = (EDGE *)pEdgeListNode->pData;

        bnf = pEdge->pNode1->nMagic; /* nMagic表示节点编号 */
        while ( pNodeNo[bnf] != -1 )
        {
            bnf = pNodeNo[bnf];
        }

        edf = pEdge->pNode2->nMagic; /* nMagic表示节点编号 */
        while ( pNodeNo[edf] != -1 )
        {
            edf = pNodeNo[edf];
        }

        if ( bnf != edf )
        {
            /* 没有成环, 将编号为edf的节点作为编号为bnf的节点的父节点 */
            pNodeNo[bnf] = edf; 

            /* 将此边标示为已经搜索过, 也就是说放入了生成树中 */
            pEdge->nMagic = GRAPH_EDGE_SEARCHED;
        }
        else
        {
            /* 已经成环成环, 将此边标示为不在生成树中 */
            pEdge->nMagic = GRAPH_EDGE_NOT_TREE;
        }

        pEdgeListNode = pEdgeListNode->pNext;
    } /* while */ 
    
    free(pNodeNo);
    return 1;
}