美文网首页
数据结构与算法-图的遍历

数据结构与算法-图的遍历

作者: 卡布奇诺_95d2 | 来源:发表于2020-05-09 17:09 被阅读0次

    定义

    从图中某一个顶点出发访遍图中其余顶点，且使每一个顶点仅被访问一次，这个过程就叫做图的遍历。
    图的遍历有两种方案：

    • 图的深度优先遍历
    • 图的广度优先遍历

    图的深度优先遍历

    图的深度优先遍历又称为深度优先搜索，简称DFS。
    深度优先遍历的思想：它从图中某个顶点V出发，访问此顶点，然后从V的未被访问的邻接点出发，深度优先遍历图，直到图中所有和V有相路径相通的顶点都被访问到。若图中尚有顶点未被访问到，则另选图中一个未曾被访问的顶点作为起始点，重复上述过程，直至图中所有顶点都被访问到。

    邻接矩阵深度遍历代码实现

    #define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0

typedef int Status;    /* Status是函数的类型,其值是函数结果状态代码，如OK等 */
//typedef int Boolean; /* Boolean是布尔类型,其值是TRUE或FALSE */

typedef char VertexType; /* 顶点类型应由用户定义 */
typedef int EdgeType; /* 边上的权值类型应由用户定义 */

#define MAXSIZE 9 /* 存储空间初始分配量 */
#define MAXEDGE 15
#define MAXVEX 9
#define INFINITYC 65535
typedef struct
{
    VertexType vexs[MAXVEX]; /* 顶点表 */
    EdgeType arc[MAXVEX][MAXVEX];/* 邻接矩阵，可看作边表 */
    int numVertexes, numEdges; /* 图中当前的顶点数和边数 */
}MGraph;

void CreateMGraph(MGraph *G)
{
    int i, j;
    
    //1. 确定图的顶点数以及边数
    G->numEdges=15;
    G->numVertexes=9;
    
    /*2.读入顶点信息，建立顶点表 */
    G->vexs[0]='A';
    G->vexs[1]='B';
    G->vexs[2]='C';
    G->vexs[3]='D';
    G->vexs[4]='E';
    G->vexs[5]='F';
    G->vexs[6]='G';
    G->vexs[7]='H';
    G->vexs[8]='I';
    
    /*3. 初始化图中的边表*/
    for (i = 0; i < G->numVertexes; i++)
    {
        for ( j = 0; j < G->numVertexes; j++)
        {
            G->arc[i][j]=0;
        }
    }
    
    /*4.将图中的连接信息输入到边表中*/
    G->arc[0][1]=1;
    G->arc[0][5]=1;
    
    G->arc[1][2]=1;
    G->arc[1][8]=1;
    G->arc[1][6]=1;
    
    G->arc[2][3]=1;
    G->arc[2][8]=1;
    
    G->arc[3][4]=1;
    G->arc[3][7]=1;
    G->arc[3][6]=1;
    G->arc[3][8]=1;
    
    G->arc[4][5]=1;
    G->arc[4][7]=1;
    
    G->arc[5][6]=1;
    
    G->arc[6][7]=1;
    
    /*5.无向图是对称矩阵.构成对称*/
    for(i = 0; i < G->numVertexes; i++)
    {
        for(j = i; j < G->numVertexes; j++)
        {
            G->arc[j][i] =G->arc[i][j];
        }
    }
}

Boolean visited[MAXVEX]; /* 访问标志的数组 */
void DFS(MGraph G,int i){
    //遍历的时候需要将标志置位，否则下次遍历又会找到该顶点
    visited[i] = TRUE;
    printf("%c",G.vexs[i]);
    //找到与该顶点相关的邻接点
    for(int j = 0;j <G.numVertexes; j++){
        //若该邻接点没有被访问，且跟顶点有关，则将该邻接点作为顶点进行遍历
        if(!visited[j] && G.arc[i][j] == 1){
            DFS(G, j);
        }
    }
}

void DFSTravese(MGraph G){
    for(int i =0; i<G.numVertexes; i++){
        visited[i] = FALSE;
    }
    //先找到一个顶点，开始遍历这个顶点
    for(int i = 0; i<G.numVertexes; i++){
        //若该顶点没有被访问过，则继续遍历，否则就不访问
        if(!visited[i]){
            DFS(G,i);
        }
    }
}

int main(int argc, const char * argv[]) {
    printf("邻接矩阵的深度优先遍历!\n");
    MGraph G;
    CreateMGraph(&G);
    DFSTravese(G);
    printf("\n");
    return 0;
}

    邻接表深度遍历代码实现

    #define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0

typedef int Status;    /* Status是函数的类型,其值是函数结果状态代码，如OK等 */
//typedef int Boolean; /* Boolean是布尔类型,其值是TRUE或FALSE */

typedef char VertexType; /* 顶点类型应由用户定义 */
typedef int EdgeType; /* 边上的权值类型应由用户定义 */

#define MAXSIZE 9 /* 存储空间初始分配量 */
#define MAXEDGE 15
#define MAXVEX 9
#define INFINITYC 65535

typedef struct EdgeNode{
    EdgeType adjvex;
    int weight;
    struct EdgeNode* next;
}EdgeNode;

typedef struct VertexNode{
    VertexType data;
    EdgeNode* firstedge;
}VertexNode, AdjList[MAXVEX];

typedef struct
{
    AdjList adjList; /* 顶点表 */
    int numVertexes, numEdges; /* 图中当前的顶点数和边数 */
}graphAdjList,*GraphAdjList;

//用于构建邻接矩阵
typedef struct
{
    VertexType vexs[MAXVEX]; /* 顶点表 */
    EdgeType arc[MAXVEX][MAXVEX];/* 邻接矩阵，可看作边表 */
    int numVertexes, numEdges; /* 图中当前的顶点数和边数 */
}MGraph;

/*4.1 构建一个邻接矩阵*/
void CreateMGraph(MGraph *G){
    int i, j;
    
    //1. 确定图的顶点数以及边数
    G->numEdges=15;
    G->numVertexes=9;
    
    /*2.读入顶点信息，建立顶点表 */
    G->vexs[0]='A';
    G->vexs[1]='B';
    G->vexs[2]='C';
    G->vexs[3]='D';
    G->vexs[4]='E';
    G->vexs[5]='F';
    G->vexs[6]='G';
    G->vexs[7]='H';
    G->vexs[8]='I';
    
    /*3. 初始化图中的边表*/
    for (i = 0; i < G->numVertexes; i++)
    {
        for ( j = 0; j < G->numVertexes; j++)
        {
            G->arc[i][j]=0;
        }
    }
    
    /*4.将图中的连接信息输入到边表中*/
    G->arc[0][1]=1;
    G->arc[0][5]=1;
    
    G->arc[1][2]=1;
    G->arc[1][8]=1;
    G->arc[1][6]=1;
    
    G->arc[2][3]=1;
    G->arc[2][8]=1;
    
    G->arc[3][4]=1;
    G->arc[3][7]=1;
    G->arc[3][6]=1;
    G->arc[3][8]=1;
    
    G->arc[4][5]=1;
    G->arc[4][7]=1;
    
    G->arc[5][6]=1;
    
    G->arc[6][7]=1;
    
    /*5.无向图是对称矩阵.构成对称*/
    for(i = 0; i < G->numVertexes; i++)
    {
        for(j = i; j < G->numVertexes; j++)
        {
            G->arc[j][i] =G->arc[i][j];
        }
    }
}

/*4.2 根据一个邻接矩阵构建一个邻接表*/
void CreateALGraph(MGraph G,GraphAdjList *GL){
    *GL = (graphAdjList*)malloc(sizeof(graphAdjList));
    (*GL)->numVertexes = G.numVertexes;
    (*GL)->numEdges = G.numEdges;
    for(int i = 0; i<G.numVertexes; i++){
        //顶点信息
        (*GL)->adjList[i].data = G.vexs[i];
        //顶点边表置空
        (*GL)->adjList[i].firstedge = NULL;
    }
    for(int i = 0; i<G.numVertexes; i++){
        for(int j =0; j<G.numVertexes; j++){
            if(G.arc[i][j] != 0){
                EdgeNode* e = (EdgeNode*)malloc(sizeof(EdgeNode));
                e->adjvex = j;
                e->weight = 0;
                e->next = (*GL)->adjList[i].firstedge;
                (*GL)->adjList[i].firstedge = e;
            }
        }
    }
}

Boolean visited[MAXSIZE]; /* 访问标志的数组 */
/* 邻接表的深度优先递归算法 */
void DFS(GraphAdjList GL, int i){
    visited[i] = TRUE;
    printf("%c",GL->adjList[i].data);
    //找到当前顶点的第一个邻接点
    EdgeNode* e = GL->adjList[i].firstedge;
    while(e != NULL){
        //若该点没有被访问，则将该邻接点作为顶点进行遍历
        if(!visited[e->adjvex]){
            DFS(GL, e->adjvex);
        }
        else{//若该点被访问过了，则找该顶点的下一个邻接点
            e = e->next;
        }
    }
}

/* 邻接表的深度遍历操作 */
void DFSTraverse(GraphAdjList GL){
    for(int i = 0; i<GL->numVertexes; i++){
        visited[i] = FALSE;
    }
    for(int i =0;i<GL->numVertexes; i++){
        if(!visited[i]){
            DFS(GL, i);
        }
    }
}

int main(int argc, const char * argv[]) {
    printf("邻接表的深度优先遍历!\n");
      MGraph G;
      GraphAdjList GL;
      CreateMGraph(&G);
      CreateALGraph(G,&GL);
    
      
      DFSTraverse(GL);
      printf("\n");
      return 0;
}

    图的广度优先遍历

    广度优先遍历又称为广度优先搜索，简称BFS。
    广度优先遍历的思想：

    • 把根结点放在队列的末尾。
    • 每次从队列的头部取出一个元素，查看这个元素的所有下一级元素，把它们放到队列的末尾，并把这个元素记为它的下一个元素的前驱。
    • 找到所有要找的元素时程序结束。
    • 如果遍历整棵树还没有找到，程序结束

    邻接矩阵广度遍历代码实现

    #define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0

typedef int Status;    /* Status是函数的类型,其值是函数结果状态代码，如OK等 */
//typedef int Boolean; /* Boolean是布尔类型,其值是TRUE或FALSE */

typedef char VertexType; /* 顶点类型应由用户定义 */
typedef int EdgeType; /* 边上的权值类型应由用户定义 */

#define MAXSIZE 9 /* 存储空间初始分配量 */
#define MAXEDGE 15
#define MAXVEX 9
#define INFINITYC 65535

typedef struct
{
    VertexType vexs[MAXVEX]; /* 顶点表 */
    EdgeType arc[MAXVEX][MAXVEX];/* 邻接矩阵，可看作边表 */
    int numVertexes, numEdges; /* 图中当前的顶点数和边数 */
}MGraph;

/*4.1 构建一个邻接矩阵*/
void CreateMGraph(MGraph *G){
    int i, j;
    
    //1. 确定图的顶点数以及边数
    G->numEdges=15;
    G->numVertexes=9;
    
    /*2.读入顶点信息，建立顶点表 */
    G->vexs[0]='A';
    G->vexs[1]='B';
    G->vexs[2]='C';
    G->vexs[3]='D';
    G->vexs[4]='E';
    G->vexs[5]='F';
    G->vexs[6]='G';
    G->vexs[7]='H';
    G->vexs[8]='I';
    
    /*3. 初始化图中的边表*/
    for (i = 0; i < G->numVertexes; i++)
    {
        for ( j = 0; j < G->numVertexes; j++)
        {
            G->arc[i][j]=0;
        }
    }
    
    /*4.将图中的连接信息输入到边表中*/
    G->arc[0][1]=1;
    G->arc[0][5]=1;
    
    G->arc[1][2]=1;
    G->arc[1][8]=1;
    G->arc[1][6]=1;
    
    G->arc[2][3]=1;
    G->arc[2][8]=1;
    
    G->arc[3][4]=1;
    G->arc[3][7]=1;
    G->arc[3][6]=1;
    G->arc[3][8]=1;
    
    G->arc[4][5]=1;
    G->arc[4][7]=1;
    
    G->arc[5][6]=1;
    
    G->arc[6][7]=1;
    
    /*5.无向图是对称矩阵.构成对称*/
    for(i = 0; i < G->numVertexes; i++)
    {
        for(j = i; j < G->numVertexes; j++)
        {
            G->arc[j][i] =G->arc[i][j];
        }
    }
}

/* 循环队列的顺序存储结构 */
typedef struct
{
    int data[MAXSIZE];
    int front;        /* 头指针 */
    int rear;        /* 尾指针，若队列不空，指向队列尾元素的下一个位置 */
}Queue;

/* 初始化一个空队列Q */
Status InitQueue(Queue *Q){
    Q->front = 0;
    Q->rear = 0;
    return OK;
}

/* 若队列Q为空队列,则返回TRUE,否则返回FALSE */
Status QueueEmpty(Queue Q){
    if(Q.front == Q.rear) return YES;
    return NO;
}

/* 若队列未满，则插入元素e为Q新的队尾元素 */
Status EnQueue(Queue *Q,int e){
    if((Q->rear+1)%MAXVEX == Q->front) return ERROR;
    Q->data[Q->rear] = e;
    Q->rear = (Q->rear+1)%MAXVEX;
    return OK;
}

/* 若队列不空，则删除Q中队头元素，用e返回其值 */
Status DeQueue(Queue *Q,int *e){
    if(QueueEmpty(*Q)) return ERROR;
    *e = Q->data[Q->front];
    Q->front = (Q->front+1)%MAXVEX;
    return OK;
}

void display(Queue Q){
    int i = Q.front;
    printf("\n当前队列里面剩下：\n");
    while(i%MAXVEX != Q.rear){
        printf("%d ", Q.data[i]);
        i = (i+1)%MAXVEX;
    }
    printf("\n");
}

Boolean visited[MAXVEX]; /* 访问标志的数组 */
void BFSTraverse(MGraph G){
    //初始化visited数组
    for(int i = 0; i<G.numVertexes; i++){
        visited[i] = FALSE;
    }
    Queue Q;
    InitQueue(&Q);
    
    //开始遍历整个表
    for(int i = 0; i<G.numVertexes; i++){
        //如果该顶点已经被遍历了，直接找下一个未被遍历的顶点
        if(!visited[i]){
            //打印该顶点信息，并将标志改为已经被遍历
            visited[i] = TRUE;
            //将该顶点索引入队列
            EnQueue(&Q, i);
            //判断当前队列是否为空，如果为空，则此轮遍历完成
            while(!QueueEmpty(Q)){
                //将队列中最前面的顶点出队列
                DeQueue(&Q, &i);
                printf("%c  ",G.vexs[i]);
                for(int j = 0; j<G.numVertexes; j++){
                    //找到与前面出队列的顶点有关，且未加入到队列里的顶点，找到后，将标记修改
                    if(!visited[j] && G.arc[i][j] == 1){
                        visited[j] = TRUE;
                        EnQueue(&Q, j);
                    }
                }
            }
            
        }
    }
    
}

int main(int argc, const char * argv[]) {
    printf("邻接矩阵广度优先遍历!\n");
    MGraph G;
    CreateMGraph(&G);
    BFSTraverse(G);
    printf("\n");
    return 0;
}

    邻接表广度遍历代码实现

    #define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0

typedef int Status;    /* Status是函数的类型,其值是函数结果状态代码，如OK等 */
//typedef int Boolean; /* Boolean是布尔类型,其值是TRUE或FALSE */

typedef char VertexType; /* 顶点类型应由用户定义 */
typedef int EdgeType; /* 边上的权值类型应由用户定义 */

#define MAXSIZE 9 /* 存储空间初始分配量 */
#define MAXEDGE 15
#define MAXVEX 9
#define INFINITYC 65535

typedef struct
{
    VertexType vexs[MAXVEX]; /* 顶点表 */
    EdgeType arc[MAXVEX][MAXVEX];/* 邻接矩阵，可看作边表 */
    int numVertexes, numEdges; /* 图中当前的顶点数和边数 */
}MGraph;

typedef struct EdgeNode{/* 边表结点 */
    int adjvex;    /* 邻接点域,存储该顶点对应的下标 */
    int weight;        /* 用于存储权值,对于非网图可以不需要 */
    struct EdgeNode *next; /* 链域,指向下一个邻接点 */
}EdgeNode;

typedef struct VertexNode{/* 顶点表结点 */
    int in;    /* 顶点入度 */
    char data; /* 顶点域,存储顶点信息 */
    EdgeNode *firstedge;/* 边表头指针 */
}VertexNode, AdjList[MAXVEX];

typedef struct{
    AdjList adjList;
    int numVertexes,numEdges; /* 图中当前顶点数和边数 */
}graphAdjList,*GraphAdjList;

/*4.1 构建一个邻接矩阵*/
void CreateMGraph(MGraph *G){
    int i, j;
    
    //1. 确定图的顶点数以及边数
    G->numEdges=15;
    G->numVertexes=9;
    
    /*2.读入顶点信息，建立顶点表 */
    G->vexs[0]='A';
    G->vexs[1]='B';
    G->vexs[2]='C';
    G->vexs[3]='D';
    G->vexs[4]='E';
    G->vexs[5]='F';
    G->vexs[6]='G';
    G->vexs[7]='H';
    G->vexs[8]='I';
    
    /*3. 初始化图中的边表*/
    for (i = 0; i < G->numVertexes; i++)
    {
        for ( j = 0; j < G->numVertexes; j++)
        {
            G->arc[i][j]=0;
        }
    }
    
    /*4.将图中的连接信息输入到边表中*/
    G->arc[0][1]=1;
    G->arc[0][5]=1;
    
    G->arc[1][2]=1;
    G->arc[1][8]=1;
    G->arc[1][6]=1;
    
    G->arc[2][3]=1;
    G->arc[2][8]=1;
    
    G->arc[3][4]=1;
    G->arc[3][7]=1;
    G->arc[3][6]=1;
    G->arc[3][8]=1;
    
    G->arc[4][5]=1;
    G->arc[4][7]=1;
    
    G->arc[5][6]=1;
    
    G->arc[6][7]=1;
    
    /*5.无向图是对称矩阵.构成对称*/
    for(i = 0; i < G->numVertexes; i++)
    {
        for(j = i; j < G->numVertexes; j++)
        {
            G->arc[j][i] =G->arc[i][j];
        }
    }
}

/*4.2 利用邻接矩阵构建邻接表*/
void CreateALGraph(MGraph G,GraphAdjList *GL){
    (*GL) = (GraphAdjList)malloc(sizeof(graphAdjList));
    (*GL)->numVertexes = G.numVertexes;
    (*GL)->numEdges = G.numEdges;
    for(int i = 0; i<G.numVertexes; i++){
        (*GL)->adjList[i].data = G.vexs[i];
        (*GL)->adjList[i].firstedge = NULL;
    }
    for(int i = 0; i<G.numVertexes; i++){
        for(int j = 0; j<G.numVertexes; j++){
            if(G.arc[i][j] == 1){
                EdgeNode *e = (EdgeNode*)malloc(sizeof(EdgeNode));
                e->adjvex = j;
                e->weight = 0;
                e->next = (*GL)->adjList[i].firstedge;
                (*GL)->adjList[i].firstedge = e;
            }
        }
    }
}

/* 循环队列的顺序存储结构 */
typedef struct{
    int data[MAXSIZE];
    int front;        /* 头指针 */
    int rear;        /* 尾指针，若队列不空，指向队列尾元素的下一个位置 */
}Queue;

/* 初始化一个空队列Q */
Status InitQueue(Queue *Q){
    Q->front = 0;
    Q->rear = 0;
    return OK;
}

/* 若队列Q为空队列,则返回TRUE,否则返回FALSE */
Status QueueEmpty(Queue Q){
    if(Q.front == Q.rear) return YES;
    return NO;
}

/* 若队列未满，则插入元素e为Q新的队尾元素 */
Status EnQueue(Queue *Q,int e){
    if((Q->rear+1)%MAXVEX == Q->front) return ERROR;
    Q->data[Q->rear] = e;
    Q->rear = (Q->rear+1)%MAXVEX;
    return OK;
}

/* 若队列不空，则删除Q中队头元素，用e返回其值 */
Status DeQueue(Queue *Q,int *e){
    if(QueueEmpty(*Q)) return ERROR;
    *e = Q->data[Q->front];
    Q->front = (Q->front+1)%MAXVEX;
    return OK;
}

void display(Queue Q){
    int i = Q.front;
    printf("\n当前队列里面剩下：\n");
    while(i%MAXVEX != Q.rear){
        printf("%d ", Q.data[i]);
        i = (i+1)%MAXVEX;
    }
    printf("\n");
}

Boolean visited[MAXVEX]; /* 访问标志的数组 */

void BFSTraverse(GraphAdjList GL){
    for(int i = 0; i<GL->numVertexes; i++){
        visited[i] = FALSE;
    }
    
    Queue Q;
    InitQueue(&Q);
    EdgeNode* e;
    
    for(int i = 0; i<GL->numVertexes; i++){
        if(!visited[i]){
            visited[i] = TRUE;
            EnQueue(&Q, i);
            while(!QueueEmpty(Q)){
                DeQueue(&Q, &i);
                printf("%c ", GL->adjList[i].data);
                e = GL->adjList[i].firstedge;
                while(e){
                    if(!visited[e->adjvex]){
                        visited[e->adjvex] = TRUE;
                        EnQueue(&Q, e->adjvex);
                    }
                    e = e->next;
                }
            }
        }
    }
}

int main(int argc, const char * argv[]) {
    printf("邻接表广度优先遍历\n");
    MGraph G;
    GraphAdjList GL;
    CreateMGraph(&G);
    CreateALGraph(G,&GL);

    BFSTraverse(GL);
    printf("\n");
    return 0;
}

    总结

    对比图的深度遍历和广度遍历算法，会发现他们在算法复杂度上是一样的。不同之处仅仅是对顶点访问的顺序不同。可见在全图遍历上没有优劣之分，实际使用可根据情况选择不同的算法。
    深度优先遍历更适合目标比较明确，以找为目标为主要目的的情况。
    广度优先遍历适合在不断扩大遍历范围时，找到相对最优解的情况。

    相关文章

      网友评论

          本文标题：数据结构与算法-图的遍历

          本文链接：https://www.haomeiwen.com/subject/hmohnhtx.html

          延伸阅读

          深度阅读

          • 您也可以注册成为美文阅读网的作者，发表您的原创作品、分享您的心情！

          栏目导航

          热点阅读

          关于我们|服务条款|联系我们|数据结构与算法-图的遍历|投稿指南|网站地图|RSS订阅|排版工具|手机版

          提供经典美文摘抄,优美散文欣赏,现代诗歌精选,短篇小说,心情随笔,表白情书范文,故事会在线阅读欣赏

          Copyright © 2014-2023 Haomeiwen.com All Rights Reserved. 好美文阅读网 版权所有

          备案信息：桂公网安备 45052102000051号 · 桂ICP备13007215号-3

          本站所收录作品、热点评论等信息部分来源互联网，目的只是为了系统归纳学习和传递资讯

          所有作品版权归原创作者所有，与本站立场无关，如不慎侵犯了你的权益，请联系我们告知，我们将做删除处理！