2013年（118）
分类： C/C++
2013-10-18 15:49:00
原文地址：数据结构深入剖析（13）--图的遍历 作者：mq24705
一、 图的遍历
1. 定义：从图中的某一顶点出发，沿着一些边访问图中所有的顶点，使得每个顶点仅被访问一次。
2. 深度优先遍历
关键：整个过程需要一个标记顶点是否被访问过的辅助数组visited[]。
算法描述：
访问起始顶点v
当v还有邻接顶点未被访问时------深度遍历未访问过的邻接顶点w。
当v的所有邻接点都被访问过时
若图中所有顶点均已访问------算法结束
若图中还有未访问的顶点-------以为访问顶点作为起始顶点深度遍历。
邻接链表中实现：
static void recursive_dfs(TLGraph* graph,int v,int visited[],LGraph_Printf* pFunc)
{
int i = 0;
pFunc(graph->v[v]);
visited[v] = 1;
printf(",");
for(i = 0; i < LinkList_Length(graph->la[v]);i++){
TListNode* node = (TListNode*)LinkList_Get(graph->la[v],i);
if(!visited[node->v]){
recursive_dfs(graph,node->v,visited,pFunc);
}
}
}
邻接矩阵中实现：
static void recursive_dfs(TMGraph* graph,int v,int visited[],MGraph_Printf* pFunc)
{
int i = 0;
pFunc(graph->v[v]);
visited[v] = 1;
printf(" ,");
for(i = 0;i < graph->count;i++){
if((graph->matrix[v][i] != 0) && !visited[i]){
recursive_DFS(graph,i,visited,pFunc);
}
}
}
调用：
void LGraph_DFS(LGraph* graph,int v,LGraph_Printf* pFunc)
{
TLGraph* tGraph = (TLGraph*)graph;
int* visited = NULL;
int condition = (tGraph != NULL);
condition = condition && (0 <= v) && (v < tGraph->count) && (pFunc != NULL);
visited = (int*)calloc(tGraph->count,sizeof(int));
condition = condition && (visited != NULL);
if(condition){
int i = 0;
recursive_dfs(tGraph,v,visited,pFunc);
for(i = 0;i < tGraph->count;i++){
if(!visited[i]){
recursive_dfs(tGraph,i,visited,pFunc);
}
}
}
}
3. 广度优先遍历
关键：整个过程需要一个标记顶点是否被访问过的辅助数组visited[]。
算法描述：
a、访问起始顶点v0
b、依次访问v0的各个邻接点v01，v02，…，v0x
c、假设设最近一次访问的顶点依次为vi1,vi2,…,viy,则依次访问vi1,vi2,…,viy的未被访问的邻接点
d、重复c，直到所有顶点均被访问。
邻接链表中实现：
static void bfs(TLGraph* graph,int v,int visited[],LGraph_Printf* pFunc)
{
LinkQueue* queue = LinkQueue_Create();
if(queue != NULL){
LinkQueue_Append(queue,graph->v + v);
visited[v] = 1;
while(LinkQueue_Length(queue) > 0){
int i = 0;
v = (LVertex**)LinkQueue_Retrieve(queue) - graph->v;
pFunc(graph->v[v]);
printf(",");
for(i = 0;i < LinkList_Length(graph->la[v]);i++){
TListNode* node = (TListNode*)LinkList_Get(graph->la[v],i);
if(!visited[node->v]){
LinkQueue_Append(queue,graph->v + node->v);
visited[node->v] = 1;
}
}
}
}
LinkQueue_Destroy(queue);
}
邻接矩阵实现：
static void bfs(TMGraph* graph,int v,int visited[],MGraph_Printf* pFunc)
{
LinkQueue* queue = LinkQueue_Create();
if(queue != NULL){
LinkQueue_Append(queue,graph->v + v);
visited[v] = 1;
while(LinkQueue_Length(queue) > 0){
int i = 0;
v = (MVertex**)LinkQueue_Retrieve(queue) - graph->v;
pFunc(graph->v[v]);
printf(" ,");
for(i = 0;i < graph->count;i++){
if((graph->matrix[v][i] != 0) && !visited[i]){
LinkQueue_Append(queue,graph->v + i);
visited[i] = 1;
}
}
}
}
LinkQueue_Destroy(queue);
}
调用：
void LGraph_BFS(LGraph* graph,int v,LGraph_Printf* pFunc)
{
TLGraph* tGraph = (TLGraph*)graph;
int* visited = NULL;
int condition = (tGraph != NULL);
condition = condition && (0 <= v) && (v < tGraph->count) && (pFunc != NULL);
visited = (int*)calloc(tGraph->count,sizeof(int));
condition = condition && (visited != NULL);
if(condition){
int i = 0;
bfs(tGraph,v,visited,pFunc);
for(i = 0;i < tGraph->count;i++){
if(!visited[i]){
bfs(tGraph,i,visited,pFunc);
}
}
}
}
