📄 graph.c
字号:
成功时返回两点间最短路径的总距离
*/
DISTANCE Graph_GetShortDistance(LPGRAPH pGraph, LPGRAPHNODE pSrcNode,
LPGRAPHNODE pTagNode)
{
INT i, j, k; /* 循环变量 */
INT nCalCount; /* 用来记录已经计算好的到pSrcNode最短路径的节点数量 */
GRAPHNODE **ppNode; /* 用来存放已经计算好的到pSrcNode最短路径的节点数组 */
DISTANCE nTagDis; /* 用来保存pTagNode到pSrcNode最短路径的距离值 */
nTagDis = -1; /* 初始化为-1, 即初始时pTagNode和pSrcNode还没有计算出路径 */
/* 参数校验 */
if ( NULL == pGraph || NULL == pSrcNode || NULL == pTagNode )
{
return GRAPH_ERROR;
}
ppNode = (GRAPHNODE **)malloc(pGraph->nNodeCount * sizeof(GRAPHNODE *));
if ( NULL == ppNode )
{
return GRAPH_ERROR;
}
memset(ppNode, 0, pGraph->nNodeCount * sizeof(GRAPHNODE *) );
for ( i = 0; i < pGraph->nNodeCount; i++ )
{
pGraph->ppNodeArray[i]->nMagic = -1; /* 初始化为-1表示还没有计算过 */
pGraph->ppNodeArray[i]->pMagic = NULL;
}
ppNode[0] = pSrcNode;
ppNode[0]->nMagic = 0; /*初始化为0，同时也表示pSrcNode到pSrcNode的距离为0*/
ppNode[0]->pMagic = NULL;
nCalCount = 1; /* 初始化为1，表示pSrcNode这1个节点已经计算完了 */
/* k从1开始循环是因为ppNode[0]已经不需计算 */
for ( k = 1; k < pGraph->nNodeCount; k++ )
{
/* nTotalDis用来保存所有未计算节点中到pSrcNode节点最短距离的距离值 */
DISTANCE nTotalDis;
/* pSNode用来表示目标节点到pSrcNode最短路径上和目标节点相邻的节点 */
GRAPHNODE *pSNode;
/* pTNode用来表示所有未计算节点中到pSrcNode节点最短距离的节点 */
GRAPHNODE *pTNode;
pSNode = NULL;
pTNode = NULL;
nTotalDis = 0;
for ( i = 0; i < nCalCount; i++ )
{
DISTANCE nMinDis;
/* 用来表示所有未计算节点到某个已算好的节点的最短距离的那个节点 */
GRAPHNODE * pShortNode;
SINGLENODE * pNode;
SINGLELIST * pList;
nMinDis = 0;
pShortNode = NULL;
for ( j = 0; j < pGraph->nNodeCount; j++ )
{
if ( pGraph->ppNodeArray[j]->nMagic != -1 )
{
/* 节点已经计算出结果 */
continue;
}
pList = pGraph->ppNodeArray[j]->pEdgeList;
pNode = pList->pHead;
while ( pNode != NULL )
{
EDGE *pEdge = (EDGE *)pNode->pData;
if ( pEdge->pNode1 == ppNode[i]
|| pEdge->pNode2 == ppNode[i] )
{
if ( nMinDis == 0 )
{
nMinDis = ppNode[i]->nMagic + pEdge->distance;
pShortNode = pGraph->ppNodeArray[j];
}
else
{
if (nMinDis > ppNode[i]->nMagic + pEdge->distance)
{
nMinDis = ppNode[i]->nMagic + pEdge->distance;
pShortNode = pGraph->ppNodeArray[j];
}
}
break; /* 在邻居中找到对应节点后应中止查找 */
}
pNode = pNode->pNext;
} /* while ( p ) */
} /* for ( j = 0 */
if ( nTotalDis == 0 )
{
nTotalDis = nMinDis; /* 重新初始化nTotaldis */
pTNode = pShortNode;
pSNode = ppNode[i];
}
else
{
if ( nTotalDis > nMinDis )
{
nTotalDis = nMinDis;
pTNode = pShortNode;
pSNode = ppNode[i];
}
}
} /* for ( i = 0 */
if ( NULL != pTNode )
{
pTNode->nMagic = nTotalDis;
pTNode->pMagic = pSNode; /* 在pMagic中存放最短路径上的相邻节点 */
if ( pTNode == pTagNode )
{
/* 已经计算到了pTagNode和pSrcNode的最短路径 */
nTagDis = nTotalDis;
break;
}
}
/* 已经找出了一个到pSrcNode的最短路径pTNode,
* 下一轮循环需要扩大ppNode中的数量
*/
ppNode[nCalCount] = pTNode;
nCalCount++;
} /* for ( k = 0 */
return nTagDis; /* 返回目标节点到源节点的最短路径 */
}
/** 计算图中两个节点间的最短路径函数
计算完后，每个节点的pMagic是用来存放到源节点最短路径的下一个节点指针
nMagic用来存放到源节点的最短路径的总距离
@param LPGRAPH pGraph - 要计算的图
@param LPGRAPHNODE pSrcNode - 源节点
@param LPGRAPHNODE pTagNode - 目标节点
@return DISTANCE - GRAPH_ERROR 表示参数错误
GRAPH_NOT_PATH 表示没有路径
成功时返回两点间最短路径的总距离
*/
DISTANCE Graph_GetShortDistance2(LPGRAPH pGraph, LPGRAPHNODE pSrcNode,
LPGRAPHNODE pTagNode)
{
INT i, k; /* 循环变量 */
INT nCalCount;/* 用来记录已经计算好的到pSrcNode最短路径的节点数量*/
GRAPHNODE **ppNode; /* 用来存放已经计算好的到pSrcNode最短路径的节点数组*/
DISTANCE nTagDis; /* 用来保存pTagNode到pSrcNode最短路径的距离值 */
nTagDis = -1; /* 初始化为-1, 即初始时pTagNode和pSrcNode还没有计算出路径 */
/* 参数校验 */
if ( NULL == pGraph || NULL == pSrcNode || NULL == pTagNode )
{
return GRAPH_ERROR;
}
ppNode = (GRAPHNODE **)malloc(pGraph->nNodeCount * sizeof(GRAPHNODE *));
if ( NULL == ppNode )
{
return GRAPH_ERROR;
}
memset(ppNode, 0, pGraph->nNodeCount * sizeof(GRAPHNODE *) );
for ( i = 0; i < pGraph->nNodeCount; i++ )
{
pGraph->ppNodeArray[i]->nMagic = -1; /* 初始化为-1表示还没有计算过 */
pGraph->ppNodeArray[i]->pMagic = NULL;
}
ppNode[0] = pSrcNode;
ppNode[0]->nMagic = 0; /*初始化为0，同时也表示pSrcNode到pSrcNode的距离为0*/
ppNode[0]->pMagic = NULL;
nCalCount = 1; /* 初始化为1，表示pSrcNode这1个节点已经计算完了 */
/* k从1开始循环是因为ppNode[0]已经不需计算 */
for ( k = 1; k < pGraph->nNodeCount; k++ )
{
/* 用来保存所有未计算节点中到pSrcNode节点最短距离的距离值 */
DISTANCE nTotalDis;
/* 用来表示目标节点到pSrcNode最短路径上和目标节点相邻的节点 */
GRAPHNODE *pSNode;
/* 用来表示所有未计算节点中到pSrcNode节点最短距离的节点 */
GRAPHNODE *pTNode;
pSNode = NULL;
pTNode = NULL;
nTotalDis = 0;
for ( i = 0; i < nCalCount; i++ )
{
/* 用来表示所有未计算节点到某个已算好的节点的最短距离的那个节点 */
GRAPHNODE * pShortNode;
SINGLENODE * pNode;
SINGLELIST * pList;
DISTANCE nMinDis;
nMinDis = GRAPH_MAX_DISTANCE;
pShortNode = NULL;
pList = ppNode[i]->pEdgeList;
pNode = pList->pHead;
while ( pNode != NULL )
{
EDGE *pEdge;
GRAPHNODE *pGraphNode;
pEdge = (EDGE *)pNode->pData;
if ( pEdge->pNode1 == ppNode[i] )
{
pGraphNode = pEdge->pNode2;
}
else
{
pGraphNode = pEdge->pNode1;
}
if ( pGraphNode->nMagic != -1 )
{
pNode = pNode->pNext;
continue;
}
if ( nMinDis > ppNode[i]->nMagic + pEdge->distance )
{
nMinDis = ppNode[i]->nMagic + pEdge->distance;
pShortNode = pGraphNode;
}
pNode = pNode->pNext;
}
if ( nTotalDis == 0 )
{
nTotalDis = nMinDis; /* 重新初始化nTotaldis */
pTNode = pShortNode;
pSNode = ppNode[i];
}
else
{
if ( nTotalDis > nMinDis )
{
nTotalDis = nMinDis;
pTNode = pShortNode;
pSNode = ppNode[i];
}
}
} /* for ( i = 0 */
if ( NULL != pTNode )
{
pTNode->nMagic = nTotalDis;
pTNode->pMagic = pSNode; /* 在pMagic中存放最短路径上的相邻节点 */
if ( pTNode == pTagNode )
{
/* 已经计算到了pTagNode和pSrcNode的最短路径 */
nTagDis = nTotalDis;
break;
}
}
/* 已经找出了一个到pSrcNode的最短路径pTNode,
* 下一轮循环需要扩大ppNode中的数量
*/
ppNode[nCalCount] = pTNode;
nCalCount++;
} /* for ( k = 0 */
return nTagDis; /* 返回目标节点到源节点的最短路径 */
}
/** 对图进行深度优先搜索
计算完后，每个节点的pMagic是用来存放父节点指针
节点的nMagic是用来存放DFS编码
边的nMagic是用来存放是否使用的标志, 搜索完后, 标志为GRAPH_EDGE_SEARCHED
的边构成一颗生成树, 树的根节点为搜索起点
@param LPGRAPH pGraph - 要搜索的图
@param LPGRAPHNODE pOrgNode - 要搜索的起点, 为图中的某个顶点
@param LPEDGE pTagEdge - 要搜索的指定的边, 当搜索到此边后停止搜索
如果为NULL则一直将整个图完全遍历搜索
@param EDGEDUMPFUNC EdgeDumpFunc - 边的回调函数, 为NULL则不执行回调
@return INT - 0 表示失败，1表示搜索完成, 2表示搜索到指定边pTagEdge.
*/
INT Graph_DepthFirstSearch(LPGRAPH pGraph,
LPGRAPHNODE pOrgNode,
LPEDGE pTagEdge,
EDGEDUMPFUNC EdgeDumpFunc)
{
LPGRAPHNODE pCurrentNode;
INT nDfsCode;
INT i;
SINGLENODE *pListNode;
EDGE *pEdge;
INT nControlFlag;
if ( NULL == pGraph || NULL == pOrgNode )
{
return CAPI_FAILED;
}
/* 初始化变量 */
nControlFlag = 0;
nDfsCode = 0;
pCurrentNode = NULL;
/* 初始化所有节点的DFS编码为0以及父节点指针为空 */
for ( i = 0; i < pGraph->nNodeCount; i++ )
{
/* 本算法中，nMagic被用来记录DFS编码 */
pGraph->ppNodeArray[i]->nMagic = 0;
/* 本算法中，pMagic被用来记录父节点 */
pGraph->ppNodeArray[i]->pMagic = NULL;
}
/* 初始化所有的边为0表示未用过，
* 注：pEdge->nMagic为GRAPH_EDGE_NOT_SEARCH时表示边未用过，
* 为GRAPH_EDGE_SEARCHED表示已被搜索过
*/
pListNode = pGraph->pEdgeList->pHead;
while ( pListNode != NULL )
{
pEdge = (EDGE *)pListNode->pData;
/* 初始化nMagic为GRAPH_EDGE_NOT_SEARCH表示此边未被搜索过 */
pEdge->nMagic = GRAPH_EDGE_NOT_SEARCH;
pListNode = pListNode->pNext;
}
pCurrentNode = pOrgNode;
/* 将所有节点的邻居列表当前位置放置在链表头部以便于后面从头搜索 */
for ( i = 0; i < pGraph->nNodeCount; i++ )
{
SingleList_EnumBegin(pGraph->ppNodeArray[i]->pEdgeList);
}
for ( ; ; )
{
void *pData;
⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -