Chinaunix首页 | 论坛 | 博客
  • 博客访问: 320786
  • 博文数量: 64
  • 博客积分: 10
  • 博客等级: 民兵
  • 技术积分: 1972
  • 用 户 组: 普通用户
  • 注册时间: 2012-05-31 21:53
个人简介

文明之精神,野蛮之体魄。

文章分类
文章存档

2015年(4)

2013年(60)

我的朋友

分类: C/C++

2013-10-17 11:13:55

一、      图的遍历

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的各个邻接点v01v02v0x

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);

                 }

           }

      }

}

阅读(2121) | 评论(0) | 转发(1) |
给主人留下些什么吧!~~