数据结构 图及其应用

这篇具有很好参考价值的文章主要介绍了数据结构 图及其应用。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

一、要求

  1.设计并验证如下算法:图采用邻接矩阵表示,实现无向图的深度优先搜索与有向图的广度优先搜索。

  2.设计并验证如下算法:带权图采用邻接表表示,实现无向图的广度优先搜索与有向图的深度优先搜索。

二、代码

1.

#include<stdio.h>
#include<stdlib.h>
#include<time.h>
#define INFINITY INT_MAX
#define MAX_VERTEX_NUM 20
typedef struct queue
{
    int Data[MAX_VERTEX_NUM];
    int front;
    int rear;
}SqQueue;


int visited[MAX_VERTEX_NUM];//1--已访问   0--未访问 

typedef struct mgraph
{
    char vexs[MAX_VERTEX_NUM];//顶点向量 
    int arcs[MAX_VERTEX_NUM][MAX_VERTEX_NUM];//邻接矩阵
    int vexnum;//图的顶点数
}Mgraph;

void init_queue(SqQueue *);
void EnQueue(SqQueue *,int);
void DeQueue(SqQueue *);
int empty_queue(SqQueue *);
void DFS(Mgraph G,int v); 
void DFSTraverse(Mgraph G);
void BFSTraverse(Mgraph G);

int main()
{
    Mgraph G;
    printf("请输入图的顶点数\n");
    scanf("%d",&G.vexnum);
    printf("输入图的各个顶点向量\n");
    scanf("%s",&G.vexs);
    srand((unsigned)time(NULL)); 
    for(int i=0;i<G.vexnum;i++)//随机生成邻接矩阵 
    {
        for(int j=0;j<G.vexnum;j++)
            G.arcs[i][j]=rand()%2;
    }
    printf("该图的邻接矩阵如下:\n");
    for(int i=0;i<G.vexnum;i++)//随机生成邻接矩阵 
    {
        for(int j=0;j<G.vexnum;j++)
            printf("%d ",G.arcs[i][j]);
        printf("\n");
    }
    printf("深度优先遍历结果如下:\n"); 
    DFSTraverse(G);
    printf("\n");
    printf("广度优先遍历结果如下:\n"); 
    BFSTraverse(G);
    return 0;
}
void DFSTraverse(Mgraph G)
{
    for(int v=0;v<G.vexnum;v++)//标记赋值为未访问 
        visited[v]=0; 
    for(int v=0;v<G.vexnum;v++)//调用DFS 
        if(!visited[v])
           DFS(G,v); 
}
void DFS(Mgraph G,int v)
{
    visited[v]=1;
    printf("%c ",G.vexs[v]);
    for(int n=0;n<G.vexnum;n++)
    {
        if((visited[n]==0)&&(G.arcs[v][n]==1))
            DFS(G,n);
    }
}

void BFSTraverse(Mgraph G)//广度优先遍历 
{
    SqQueue Q;
    for(int i=0;i<G.vexnum;i++)
        visited[i]=0;
    init_queue(&Q);
    for(int i=0;i<G.vexnum;i++)
    {
        if(!visited[i])
        {
            visited[i]=1;
            printf("%c ",G.vexs[i]);
            EnQueue(&Q,i);
        }
        while(!empty_queue(&Q))
        {
            DeQueue(&Q);
            for(int j=0;j<G.vexnum;j++)
            {
                if(!visited[j]&&G.arcs[i][j])
                {
                    visited[j]=1;
                    printf("%c ",G.vexs[j]);
                    EnQueue(&Q,j);
                }
            }
         } 
    }
}

void init_queue(SqQueue *Q)
{
    Q->front=Q->rear=0;
}

void EnQueue(SqQueue *Q,int e)
{
        Q->Data[Q->rear]=e;
        Q->rear++;
}

void DeQueue(SqQueue *Q)
{
    Q->front++;
}

int empty_queue(SqQueue *Q)
{
    if(Q->front==Q->rear)
        return 1;
    else
        return 0;
}

运行结果

数据结构 图及其应用

 

 2.

#include<stdio.h>
#include<stdlib.h>  
#define MAX_SIZE 20
int visited[MAX_SIZE];

typedef struct queue
{
    int Data[MAX_SIZE];
    int front;
    int rear;
}SqQueue;

typedef struct ArcNode 
{
    int adjvex;//该弧指向顶点的位置 
    struct ArcNode *next;
}ArcNode;

typedef struct vnode
{
    int data;//顶点信息 
    ArcNode *first;//指向第一条依附该顶点的弧的指针 
}VNode;    

typedef struct 
{
    VNode vertices[MAX_SIZE];
    int vexnum;
    int edgenum;
}ALGraph;

void init_queue(SqQueue *);
void EnQueue(SqQueue *,int);
void DeQueue(SqQueue *);
int empty_queue(SqQueue *);
void DFSTraverse(ALGraph *G);
void DFS(ALGraph *G,int v); 
void BFSTraverse(ALGraph G);
void createALGraph(ALGraph *);                                                                                                                                                                                                                                                                                                                                                            
int main()
{
    ALGraph G;
    createALGraph(&G);
    DFSTraverse(&G);
    printf("\n");
    BFSTraverse(G);
    return 0;
 } 
 void DFSTraverse(ALGraph *G)
{
    for(int v=0;v<G->vexnum;v++)//标记赋值为未访问 
        visited[v]=0; 
    for(int v=0;v<G->vexnum;v++)//调用DFS 
        if(!visited[v])
           DFS(G,v); 
}
void DFS(ALGraph *G,int v)
{
    ArcNode *p;
    p = G->vertices[v].first;
    visited[v]=1;
    printf("%d ",G->vertices[v].data);
    while(p)
    {
        if(!visited[p->adjvex])
            DFS(G,p->adjvex);
        p=p->next;
    }
    
}

void BFSTraverse(ALGraph G)
{
    SqQueue Q;
    ArcNode *p;
    for(int i=0;i<G.vexnum;i++)
        visited[i]=0;
    init_queue(&Q);
    for(int i=0;i<G.vexnum;i++)
    {
        p = G.vertices[0].first;
        if(!visited[i])
        {
            visited[i]=1;
            printf("%d ",G.vertices[i].data);
            EnQueue(&Q,i);
        }
        while(!empty_queue(&Q))
        {
            DeQueue(&Q);
            while(p)
            {
                if(!visited[p->adjvex])
                {
                    visited[p->adjvex]=1;
                    printf("%d ",G.vertices[p->adjvex].data);
                    EnQueue(&Q,i);
                }
                p=p->next;
            }
                    
        }    
    }
}

void init_queue(SqQueue *Q)
{
    Q->front=Q->rear=0;
}

void EnQueue(SqQueue *Q,int e)
{
        Q->Data[Q->rear]=e;
        Q->rear++;
}

void DeQueue(SqQueue *Q)
{
    Q->front++;
}

int empty_queue(SqQueue *Q)
{
    if(Q->front==Q->rear)
        return 1;
    else
        return 0;
}

void createALGraph(ALGraph *G)
{
    int i, j;
    ArcNode *e; 
    printf("输入顶点数和边数:\n");
    scanf("%d %d",&G->vexnum,&G->edgenum);
    printf("输入顶点");
    for(i = 0; i < G->vexnum; i++)
    {
        scanf("%d", &G->vertices[i].data);
        G->vertices[i].first = NULL;
    } //输入边
    printf("输入边(i, j)上的顶点:\n");
    for(int k = 0; k < G->edgenum; k++)
    {
        scanf("%d %d", &i, &j);
        e = (ArcNode *) malloc (sizeof (ArcNode));
        e->adjvex = j;
        e->next = G->vertices[i].first;
        G->vertices[i].first = e;
        e = (ArcNode *) malloc (sizeof (ArcNode));
        e->adjvex = i;
        e->next = G->vertices[j].first;
        G->vertices[j].first= e;
    }
}

 

运行结果:

 

 数据结构 图及其应用文章来源地址https://www.toymoban.com/news/detail-760083.html

到了这里,关于数据结构 图及其应用的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 深入理解数据结构:队列的实现及其应用场景

    队列(Queue)是一种具有先进先出(FIFO)特性的数据结构。在队列中,数据的插入和删除操作分别在队列的两端进行。插入操作在队列的尾部进行,而删除操作则在队列的头部进行。这种特性使得队列在很多实际应用中非常有用,比如任务调度、缓冲区管理等。 线性表是一种

    2024年04月28日
    浏览(51)
  • 数据结构第三次实验-图及其应用

    一、实验目的 掌握图的存储、构建、搜索等操作和应用,能用最短路径及其搜索等算法编制较 综合性的程序,求解最优路线问题,进行程序设计、数据结构和算法设计等方面的综合训练。 二、实验内容及要求 1、任务描述 实验内容: 用户驾车出行由于出行目的的不同对道

    2024年02月06日
    浏览(40)
  • 头歌数据结构实训参考---二叉树及其应用

    第1关 实现二叉树的创建 第2关 计算二叉树的深度和节点个数 第3关 递归实现二叉树左右子树交换 第4关 非递归实现二叉树左右子树交换 第5关 层次遍历二叉树

    2024年02月05日
    浏览(41)
  • 【023】C/C++数据结构之链表及其实战应用

    💡 作者简介:专注于C/C++高性能程序设计和开发,理论与代码实践结合,让世界没有难学的技术。包括C/C++、Linux、MySQL、Redis、TCP/IP、协程、网络编程等。 👉 🎖️ CSDN实力新星,社区专家博主 👉 🔔 专栏介绍:从零到c++精通的学习之路。内容包括C++基础编程、中级编程、

    2024年02月08日
    浏览(53)
  • 数据密集型应用系统设计--3.1 数据库核心:数据结构

    3.1 数据库核心:数据结构 数据库只需做两件事情:向它插入数据肘,它就保存数据:之后查询时,它应该返回那些数据。 本章我们主要从数据库的角度再来探讨同样的问题,即如何存储输入的数据,井在收到查询请求时,怎样重新找到数据. 了解存储引擎的底层机制。 存储

    2024年01月24日
    浏览(48)
  • 数据结构与算法课程设计---最小生成树的应用

    1.问题 假定有这么一个问题,有11个城市,城市之间有一些天然气管道,铺设天然气管道需要花费不同的金额,现在要你选择其中一些天然气管道,使得所有城市可以互相联通且花费最小。 2.分析 我们把这个问题抽象为一张图,每个城市是一个顶点,城市与城市之间的管道是

    2024年02月08日
    浏览(51)
  • 二分搜索树(校招数据结构最低要求版)Java

    二分搜索树(Binary Search Tree,BST)是一种常见的数据结构,它能够高效地存储和查找数据。它的特点是每个节点都包含一个值,并且每个节点的左子树的值都小于节点的值,右子树的值都大于节点的值。 通过这种有序的排列方式,我们可以在二分搜索树中进行高效的查找操作

    2024年02月10日
    浏览(42)
  • 【数据结构】队列及其实现

    目录 😎前言 认识队列 队列的初始化 队列判空 数据队尾入队 数据队头出队 取队头数据 取队尾数据 队列数据的个数 队列销毁 总结 上次我们学习了栈及其实现,当然也少不它的好兄弟队列啦,今天我们开始队列的学习 队列的性质是 先进先出 ,就比如车辆进出隧道一般,它

    2024年02月09日
    浏览(43)
  • 【数据结构】栈及其实现

    目录 🤠前言 什么是栈? 栈的定义及初始化 栈的定义 栈的初始化 栈的判空 栈顶压栈 栈顶出栈 栈的数据个数 栈的销毁 完整代码 总结 学了相当长一段时间的链表,总算是跨过了一个阶段。从今天开始我们将进入栈和队列的学习,相比于链表可以说是有手就行的难度,所以

    2024年02月06日
    浏览(62)
  • 数据结构及其简单实现

    栈 先进后出 栈顶操作(栈顶进,栈顶出) 含有min函数的栈 辅助栈实现 Math.min方法实现 每日温度 力扣题目 739. 每日温度 队列 先进先出 队首出,队尾入 基于对象 双端队列 队列的最大值 滑动窗口问题 力扣题目 239. 滑动窗口最大值 链表 操作上和数组很像,为什么不用数组?

    2024年01月18日
    浏览(36)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包