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

数据结构图的基本操作(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条回答

      报告相同问题?

      相关推荐 更多相似问题

      问题事件

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

      悬赏问题

      • ¥15 Python不使用Selenium怎么实现网页输入和点击
      • ¥50 vue百度地图导致浏览器崩溃
      • ¥15 请问这段C语言代码应该如何修改呢
      • ¥20 Latex 转入带数式的曲线图后数式部分报错
      • ¥15 Arcgis基于一幅栅格提取另一幅栅格单元值
      • ¥15 Verilog数据产生器代码疑点
      • ¥15 电脑部分网页无法访问是为什么?
      • ¥15 如何在vscode导出pdf失败了,拓展也安装了?
      • ¥15 使用python-kivy如何点击按钮选择手机相册中的图片?
      • ¥15 Matlab图像生成后如何对于打开exe文件