注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

Mr.Right

不顾一切的去想,于是我们有了梦想。脚踏实地的去做,于是梦想成了现实。

 
 
 

日志

 
 
关于我

人生一年又一年,只要每年都有所积累,有所成长,都有那么一次自己认为满意的花开时刻就好。即使一时不顺,也要敞开胸怀。生命的荣枯并不是简单的重复,一时的得失不是成败的尺度。花开不是荣耀,而是一个美丽的结束,花谢也不是耻辱,而是一个低调的开始。

网易考拉推荐

C图的遍历---C语言中的楞严经  

2013-02-20 14:18:28|  分类: 编程 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
图的遍历是树的遍历的推广,是按照某种规则(或次序)访问图中各顶点依次且仅一次的操作,亦是将网络结构按某种规则线性化的过程

 
由于图存在回路,为区别一顶点是否被访问过和避免顶点被多次访问,在遍历过程中,应记下每个访问过的顶点,即每个顶点对应有一个标志位,初始为False,一旦该顶点被访问,就将其置为True,以后若又碰到该顶点时,视其标志的状态,而决定是否对其访问。

对图的遍历通常有"深度优先搜索"和"广度优先搜索"方法,二者是人工智能的一个基础。

深度优先搜索(Depth First Search,简称DFS)
算法思路:
类似树的先根遍历。设初始化时,图中各顶点均未被访问,从图中某个顶点(设为V0)出发,访问V0,然后搜索V0的一个邻接点Vi,若Vi未被访问,则访问之,在 搜索Vi的一个邻接点(深度优先)...。若某顶点的邻接点全部访问完毕,则回溯(Backtracking)到它的上一顶点,然后再从此顶点又按深度优先的方法搜索下去,...,直到能访问的顶点都访问完毕为止。

广度优先搜索(Breadth First Search),简称BFS

算法思路:

类似树的按层次遍历。初始时,图中各顶点均未被访问,从图中某顶点(V0)出发,访问V0,并依次访问V0的各邻接点(广度优先)。然后,分别从这些被访问过的顶点出发,扔仍按照广度优先的策略搜索其它顶点,....,直到能访问的顶点都访问完毕为止。

为控制广度优先的正确搜索,要用到队列技术,即访问完一个顶点后,让该顶点的序号进队。然后取相应队头(出队),考察访问过的顶点的各邻接点,将未访问过的邻接点访问 后再依次进队,...,直?到队空为止。

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define MAX 20

//访问记录
int visit[MAX];

//图的结构设计
typedef struct
{
    int vex[MAX];//记录顶点
    int adjmatrix[MAX][MAX];//邻接矩阵
    int n;//顶点的个数
}GRAPH;

//初始化图
int init_graph( GRAPH *pG )
{
    memset( pG, 0, sizeof( GRAPH ) );
    pG->n = -1;
    printf( "input vex\n" );
    while ( scanf( "%d", &pG->vex[++pG->n] ) )
        ;
    while ( getchar() != '\n' )
        ;
#ifndef _DEBUG_
    int i = 0;
    for ( i = 0;i < pG->n ;i ++ )
    {
        printf( "V%d ", pG->vex[i] );
    }
    printf( "\n" );
#endif

    return 0;
}

//获取顶点的位置
int locatevex( GRAPH *pG, int vex )
{
    int i = 0;
    for ( i = 0;i < pG->n;i ++ )
    {
        if ( pG->vex[i] == vex )
            return i;
    }

    return 0;
}

//输入图的顶点之间的边
int input_edge( GRAPH *pG )
{
    int vex1, vex2;
    int i, j;

    printf( "input edge(i,j):\n" );
    //任意字母键结束
    while ( scanf( "(%d,%d)", &vex1, &vex2 ) )
    {
        getchar();
        i = locatevex( pG, vex1 );
        j = locatevex( pG, vex2 );
        pG->adjmatrix[i][j] = pG->adjmatrix[j][i] = 1;
    }

#ifndef _DEBUG_
    int m, n;

    for ( m = 0;m < pG->n;m ++ )
    {
        for ( n = 0;n < pG->n; n ++ )
        {
            printf( "%d ", pG->adjmatrix[m][n] );
        }

        printf( "\n" );
    }

#endif

    return 0;
}

//栈的设计
typedef struct
{
    int buf[MAX];
    int n;
}Stack;

//创建空栈
Stack *create_empty_stack()
{
    Stack *stack;

    stack = ( Stack * )malloc( sizeof( Stack ) );
    stack->n = -1;

    return stack;
}

//出栈
int pop_stack( Stack *stack )
{
    int temp;

    temp = stack->buf[stack->n];
    stack->n --;

    return temp;
}

//入栈
int push_stack( Stack *stack, int data )
{
    stack->n ++;
    stack->buf[stack->n] = data;

    return 0;
}

//判断空栈
int is_empty_stack( Stack *stack )
{
    if ( stack->n == -1 )
        return 1;
    else
        return 0;
}

int visit_all( GRAPH *pG )
{
    int i = 0;

    for ( i = 0;i < pG->n; i ++ )
    {
        if ( visit[i] != 1 )
            break;
    }

    if ( i == pG->n )
        return 1;
    else
        return 0;
}

//图的深度非递归遍历
int DFS( GRAPH *pG, int v )
{
    Stack *stack;
    int i = 0;

    stack = create_empty_stack();
    push_stack( stack, pG->vex[v] );
    visit[v] = 1;
    printf( "V%d ", pG->vex[v] );

    while ( !is_empty_stack( stack ) || !visit_all( pG ) )
    {
        for ( i = 0;i < pG->n;i ++ )
        {
            if ( visit[i] == 0 && pG->adjmatrix[v][i] == 1 )
                break;
        }

        if ( i == pG->n )
        {
            v = pop_stack( stack );

        }
        else
        {

            v = i;
            push_stack( stack, pG->vex[v] );
            visit[v] = 1;
            printf( "V%d ", pG->vex[v] );
        }
    }

    printf( "\n" );

    return 0;
}

//队列的设计
typedef struct node
{
    int data;
    struct node *next;

}ListNode;

typedef struct
{
    ListNode *front;
    ListNode *rear;
}Queue;

//创建空队列
Queue *create_empty_queue()
{
    Queue *queue;
    ListNode *head;

    queue = ( Queue * )malloc( sizeof( Queue ) );
    head = ( ListNode * )malloc( sizeof( ListNode ) );

    queue->front = queue->rear = head;

    return queue;
}

//判断队列是否为空
int is_empty_queue( Queue *queue )
{
    if ( queue->rear == queue->front )
        return 1;
    else
        return 0;
}

//入队
int EnterQueue( Queue *queue, int data )
{
    ListNode *temp;

    temp = ( ListNode * )malloc( sizeof( ListNode ) );
    temp->data = data;
    temp->next = NULL;

    queue->rear->next = temp;
    queue->rear = temp;

    return 0;
}

//出队
int DelQueue( Queue *queue )
{
    ListNode *temp;

    temp = queue->front;
    queue->front = queue->front->next;
    free( temp );
    temp = NULL;

    return queue->front->data;
}

//图的广度遍历
int BFS( GRAPH *pG, int v )
{
    Queue *queue = create_empty_queue();
    int i = 0;

    memset( &visit, 0, sizeof( visit ) );

    EnterQueue( queue, v );
    visit[v] = 1;

    while ( !is_empty_queue( queue ) )
    {
        v = DelQueue( queue );
        printf( "V%d ", pG->vex[v] );


        for ( i = 0;i < pG->n;i ++ )
        {
            if ( visit[i] == 0 && pG->adjmatrix[v][i] == 1 )
            {
                EnterQueue( queue, i );
                visit[i] = 1;
            }
        }
    }

    printf( "\n" );

    return 0;
}

int main()
{
    GRAPH G;

    //输入顶点,初始化图
    init_graph( &G );

    //初始化邻接矩阵
    input_edge( &G );

    //图的深度遍历
printf("DFS\n");
    DFS( &G, 0 );

    //图的广度遍历
printf("BFS\n");
    BFS( &G, 0 );

    return 0;
}
2013年02月20日 - 阿英 - Mr.Right
 

转自:http://blog.chinaunix.net/uid-26833883-id-3171290.html
http://nthucad.cs.nthu.edu.tw/~yyliu/personal/nou/04ds/dfs.html
  评论这张
 
阅读(636)| 评论(0)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2016