assession 2022-11-16 11:07 采纳率: 100%
浏览 89
已结题

数据结构图的基本操作(DFS,BFS算法实现)

图的基本操作
如图,如何在此代码基础上两种存储类型(邻接表,邻接矩阵)实现_DFS,BFS的、递归,非递归算法_!!

#include<stdio.h>
#include<malloc.h>
#define INF 32767
typedef int InfoType;
#define MAXV 100
//领接矩阵类型的定义
typedef struct
{
    int no;
    InfoType info;
}VertexType;

//图的定义
typedef struct
{
    int edges[MAXV][MAXV];
    int n, e;
    VertexType vex[MAXV];
}MGraph;

//领接表类型的定义
typedef struct ANode
{
    int adjvex;
    struct ANode* nextarc;
    InfoType info;
}ArcNode;
typedef struct Vnode
{
    int data;
    int count;
    ArcNode* firstarc;
}VNode;
typedef VNode AdjList[MAXV];
typedef struct
{
    AdjList adjlist;
    int n, e;
}ALGraph;

int visited[MAXV];
//将领接矩阵g转换成邻接表G
void MatToList(MGraph g, ALGraph*& G)
{
    int i, j, n = g.n;
    ArcNode* p;
    G = (ALGraph*)malloc(sizeof(ALGraph));
    for (i = 0; i < n; i++)
        G->adjlist[i].firstarc = NULL;
    for (i=0;i<n;i++)
        for (j = n - 1; j >= 0; j--)
        {
            if (g.edges[i][j] > 0 && g.edges[i][j] < INF)
            {
                p = (ArcNode*)malloc(sizeof(ArcNode));
                p->adjvex = j;
                p->info = g.edges[i][j];
                p->nextarc = G->adjlist[i].firstarc;
                G->adjlist[i].firstarc = p;
            }
            G->adjlist[i].count = 0;
        }
    G->n = n;
    G->e = g.e;
}
//输出邻接矩阵
void DisMat(MGraph g)
{
    int i, j;
    for (i = 0; i < g.n; i++)
    {
        for (j = 0; j < g.n; j++)
            if (g.edges[i][j] >= 0 && g.edges[i][j] < INF)
                printf("%5d", g.edges[i][j]);
            else printf("%s", "INF");
        printf("\n");
    }
}
//输出邻接表
void DisAdj(ALGraph* G)
{
    int i;
    ArcNode* p;
    for (i = 0; i < G->n; i++)
    {
        p = G->adjlist[i].firstarc;
        printf("%3d:", i);
        while (p != NULL)
        {
            printf("%3d(%2d)", p->adjvex, p->info);
            p = p->nextarc;
        }
        printf("\n");
    }
}
//深度优先遍历算法DFS
void ShenduDFS(ALGraph* G, int v)
{
    ArcNode* p;
    visited[v] = 1;
    printf("%2d", v);
    p = G->adjlist[v].firstarc;
    while (p != NULL)
    {
        if (visited[p->adjvex] == 0)
        {
            ShenduDFS(G, p->adjvex);
        }
        p = p->nextarc;
    }
}
//广度优先遍历算法BFS
void GuangduBFS(ALGraph* G, int v)
{
    ArcNode* p;
    int queue[MAXV], front = 0, rear = 0;
    int visited[MAXV];
    int w, i;
    for (i = 0; i < G->n; i++)visited[i] = 0;
    printf("%2d", v);
    visited[v] = 1;
    rear = (rear + 1) % MAXV;
    queue[rear] = v;
    while (front != rear)
    {
        front = (front + 1) % MAXV;
        w = queue[front];
        p = G->adjlist[w].firstarc;
        while (p != NULL)
        {
            if (visited[p->adjvex] == 0)
            {
                printf("%2d", p->adjvex);
                visited[p->adjvex] = 1;
                rear = (rear + 1) % MAXV;
                queue[rear] = p->adjvex;
            }
            p = p->nextarc;
        }
    }
    printf("\n");
}

int main()
{
    int i, j, u = 0, v = 0, d = -4;
    bool flag = false;
    MGraph g;
    ALGraph* G;
    int A[MAXV][6] = {
        {0,5,INF,7,INF,INF },
        {INF,0,4,INF,INF,INF},
        {8,INF,0,INF,INF,9},
        {INF,INF,5,0,INF,6},
        {INF,INF,INF,5,0,INF},
        {3,INF,INF,INF,1,0} };
    g.n = 6; g.e = 10;
    for (i = 0; i < g.n; i++)
        for (j = 0; j < g.n; j++)
            g.edges[i][j] = A[i][j];
    printf("\n");
    printf("有向带权图G的邻接矩阵:\n");
    DisMat(g);
    G = (ALGraph*)malloc(sizeof(ALGraph));
    printf("转换成邻接表:\n");
    MatToList(g, G);
    DisAdj(G);
    printf("\n");
    printf("深度优先序列(DFS):");
    ShenduDFS(G, 0);
    printf("\n");
    printf("广度优先序列(BFS):");
    GuangduBFS(G, 0);
}

img

img

  • 写回答

8条回答 默认 最新

  • 语言-逆行者 2022-11-16 13:38
    关注

    非递归前序遍历:

    void preorder(bitree *t)//前序遍历的非递归算法
    {
     bitree *temp = t;//定义一个树节点,用它来遍历
     while(temp != NULL || s.top != 0)
     {
      while(temp != NULL)//先遍历左孩子,并输出。
      {
       printf("%4d",temp->data);
       push(temp);
       temp = temp->lchild;
      }
      if(s.top != 0)//当左孩子遍历完后,取栈顶,找右孩子。此时循环还没有结束,再遍历它的左孩子,直至孩子全部遍历结束。
      {
       temp = pop();
       temp = temp->rchild;
      }
     }
     printf("\n");
    }
    
    

    非递归中序遍历:

    void inorder(bitree *t)//中序遍历的非递归算法
    {
     bitree *temp = t;
     while(temp != NULL||s.top != 0)
     {
      while(temp != NULL)//先把左孩子入栈,所有左孩子入栈结束
      {
       push(temp);
       temp = temp->lchild;
      }
      if(s.top != 0)//左孩子入栈结束,取栈顶,输出栈顶元素,遍历右孩子
      {
       temp = pop();
       printf("%4d",temp->data);
       temp = temp->rchild;
      }
     }
     printf("\n");
    }
    
    

    非递归后序遍历:

    void laorder(bitree *root)//后序遍历的非递归算法
    {
        bitree *temp = root;
     while(temp!=NULL||s.top!=0)
        {
            while(temp!= NULL)
            {
                temp->cishu=1;       // 当前节点首次被访问
                push(temp);
                temp=temp->lchild;
            }
            if(s.top!=0)
            {
                temp=pop( );
                if(temp->cishu == 1)   // 第一次出现在栈顶
                {
    
                    temp->cishu++;
                    push(temp);
                    temp=temp->rchild;
                }
                else
        if(temp->cishu==2)//第二次输出并制空,防止陷入死循环
        {
                    printf("%4d",temp->data);
                    temp=NULL;
        }
            }
        }
     printf("\n");
    }
    
    

    参考连接1:
    《二叉树的非递归遍历(前序中序后序非递归C语言)》 https://blog.csdn.net/sinat_43009982/article/details/83343229?utm_source=app&app_version=5.0.1&code=app_1562916241&uLinkId=usr1mkqgl919blen
    参考链接2:
    《【数据结构】--- 二叉树的递归遍历和非递归遍历【C语言实现】》, 一起来围观吧 https://blog.csdn.net/qq_40587575/article/details/107410498?utm_source=app&app_version=5.0.1&code=app_1562916241&uLinkId=usr1mkqgl919blen

    本回答被题主选为最佳回答 , 对您是否有帮助呢?
    评论 编辑记录
查看更多回答(7条)

报告相同问题?

问题事件

  • 系统已结题 11月24日
  • 已采纳回答 11月16日
  • 修改了问题 11月16日
  • 修改了问题 11月16日
  • 展开全部

悬赏问题

  • ¥15 有偿求做台风过境全过程模拟仿真
  • ¥50 求!AutomationDesk 如何自动导入Variant数据
  • ¥20 Next.JS 静态导出路由
  • ¥15 我做一个对中文文本情感分析的项目 我用了CNN,和keras框架 报的错误我一直处理不好
  • ¥15 unity使用bakery打光烘焙所遇到的问题。
  • ¥99 二维有限元方法求解,泊松方程
  • ¥15 我需要在PC端 开两个抖店工作台客户端.(语言-java)
  • ¥15 有没有哪位厉害的人可以用C#可视化呀
  • ¥15 可以帮我看看代码哪里错了吗
  • ¥15 设计一个成绩管理系统