有向图和无向图的深度遍历和广度遍历
2020 年 04 月 07 日 313 571 字 暂无评论

最近遇到个问题需要用到数据结构的图,所以自学一下数据结构的这方面内容。

#pragma warning(disable:4996)
#include<iostream>
#include<stdio.h>
#include<stdlib.h>

#define MaxVerNum 20 //图的最大顶点数
#define MaxSize 30   //队列的最大容量
typedef enum
{
    False,
    True
}Bool;

typedef struct ArcNode
{
    int adjvex; //该弧所指向的顶点的位置
    struct ArcNode* nextarc; //指向下一条弧的指针
}ArcNode; //弧结点

typedef struct 
{
    ArcNode* AdjList[MaxVerNum]; //指向第一条依附该顶点的弧的指针
    int vexnum, arcnum;//图的当前顶点和弧数
    int GraphKind; //图的种类,无向图-0,有向图-1
}Graph;

typedef struct
{
    int elem[MaxSize]; //数据域
    int front, rear;   //队头,队尾指针
}SeQueue;

Bool visited[MaxVerNum];//全局变量--访问标志数组

void Create_Graph(Graph* G)
{
    int i, start, end;
    ArcNode* s;
    for ( i = 0; i <= (*G).vexnum; i++)
    {
        (*G).AdjList[i] = NULL;//初始化指针数组
    }
    for (i = 1; i <= (*G).arcnum; i++)
    {
        scanf("%d%d", &start, &end);//输入弧的起点和终点
        s = (ArcNode*)malloc(sizeof(ArcNode));//生成一个弧节点
        s->nextarc = (*G).AdjList[start];
        s->adjvex = end;
        (*G).AdjList[start] = s;
        if ((*G).GraphKind == 0)//若是无向图,再插入到终点的弧链中
        {
            s = (ArcNode*)malloc(sizeof(ArcNode));//生成一个弧节点
            s->nextarc = (*G).AdjList[end];
            s->adjvex = start;
            (*G).AdjList[end] = s;
        }
    }
}

int First_AdjVex(Graph G, int v)//找第vi个顶点的第一个邻接顶点
{
    if (!G.AdjList[v])
        return 0;
    else
        return(G.AdjList[v]->adjvex);
}

int Next_AdjVex(Graph G, int v, int u)//找第vi个顶点相对u的下一个邻接顶点
{
    ArcNode* p;
    p = G.AdjList[v];
    while (p->adjvex != u)//在顶点vi的弧链中找到顶点u
        p = p->nextarc;
    if (p->nextarc == NULL)//若已是最后一个顶点,返回0
        return 0;
    else
        return(p->nextarc->adjvex);//返回下一个邻接顶点的序号
}

void Init_Queue(SeQueue* Q)
{
    (*Q).front = (*Q).rear = 0;//初始化队列
}

Bool Empty_Queue(SeQueue Q)//判断队列是否为空
{
    if (Q.front == Q.rear)
        return True;
    else
        return False;
}

Bool In_Queue(SeQueue* Q, int ch)//入队操作,成功True
{
    if (((*Q).rear + 1) % MaxSize == (*Q).front)
        return False;
    (*Q).elem[(*Q).rear] = ch;
    (*Q).rear = ((*Q).rear + 1) % MaxSize;
    return True;
}

Bool Out_Queue(SeQueue* Q, int* ch)//出队操作,成功True
{
    if ((*Q).front == (*Q).rear)
        return False;
    (*ch) = (*Q).elem[(*Q).front];
    (*Q).front = ((*Q).front + 1) % MaxSize;
    return True;
}

void DFS(Graph G, int i)//从第i个顶点出发递归的深度遍历图
{
    int w;
    visited[i] = True; //访问第i个顶点
    printf("%d->", i);
    for (w = First_AdjVex(G, i); w; w = Next_AdjVex(G, i, w))
    {
        if (!visited[w])
            DFS(G, w);//对尚未访问的邻接顶点w调用DFS
    }
}

void DFS_Traverse(Graph G) //深度优先遍历算法
{
    int i;
    printf("深度优先遍历:");
    for (i = 1; i < G.vexnum; i++)
        visited[i] = False; //访问标志数组初始化
    for ( i = 1; i < G.vexnum; i++)
    {
        if (!visited[i])
            DFS(G, i);
    }
    printf("\b\b \n");
}

void BFS_Traverse(Graph G)//广度优先遍历,非递归,辅助队列Q和访问读标志数组visited
{
    int i, u, w;
    SeQueue Q;
    printf("广度优先遍历:");
    for ( i = 1; i <=G.vexnum; i++)
    {
        visited[i] = False; //访问标志数组初始化
    }
    Init_Queue(&Q); //初始化队列
    for ( i = 1; i <=G.vexnum; i++)
    {
        if (!visited[i])
        {
            visited[i] = True;//访问顶点vi
            printf("%d->", i);
            In_Queue(&Q, i);//将序号i入队
            while (!Empty_Queue(Q)) //若队列不空,继续
            {
                Out_Queue(&Q, &u);//将队首元素出队并置u
                for (w = First_AdjVex(G, u); w; w = Next_AdjVex(G, u, w))
                {
                    if (!visited[w])//对u的尚未访问的邻接顶点w进行访问并入队列
                    {
                        visited[w] = True;
                        printf("%d->", w);
                        In_Queue(&Q, w);
                    }
                }
            }
        }
        printf("\b\b \n");
    }
}

int main(int agrc, const char* argv[])
{
    Graph G;
    char j = 'y';
    while (j != 'N' && j != 'n')
    {
        printf("输入0或1(无向图-0,有向图-1):");
        scanf("%d", &G.GraphKind);
        printf("(如:4,3)输入顶点数和弧数: \n");
        scanf("%d%d", &G.vexnum, &G.arcnum);
        printf("如:1,2\n   1,3\n输入各边弧尾和弧头: \n");
        Create_Graph(&G);
        DFS_Traverse(G);
        BFS_Traverse(G);
        printf("图的遍历完毕,继续进行吗?(Y/N)\n");
        scanf("%c", &j);
    }
    return 0;
}

以上为具体代码,借鉴于https://www.cnblogs.com/duanqibo/p/11126221.html
以下是需要的遍历图:
请输入图片描述

以下是运行结果图:
请输入图片描述

需要注意:

 在vs高级版本中对很多函数进行了安全检查
 具体可以看我上一篇博客[http://zfhblog.com/index.php/archives/12/][4]
 使用指针等时需要注意是否初始化,这里队列头尾指针开始只有申明并未进行初始化赋值
 会报写入访问权限错误,这也是c/c++常见错误

请输入图片描述


版权属于:zfh

本文链接:http://zfhblog.com/index.php/archives/13/



评论已关闭