C语言实现图的搜索算法示例

本文实例讲述了C语言实现图的搜索算法。分享给大家供大家参考，具体如下：

在游戏中，常常遇到路径规划问题，用到图的相关算法，我们以简单图来学习。

图通常有两种表示方式，矩阵和邻接表。矩阵表示简单，运算快，但当矩阵是稀疏矩阵的时候就存在空间浪费的问题，并且效率也会下降，而邻接表节约空间，并且由于边是连续访问，时间效率也比较高。在本文中，我们将以邻接表来表示图。

#include<queue>
#include<stack>
using namespace std;
struct SE{
  int vIndex;
  int tag;
  SE* next;
};
struct SMap{
  SE* pE;
  int nnode;
};
void visit(SE *se){
  printf("%d\n", se->vIndex);
}
SMap* create_map(int matrix[][6], int n){
  SMap* pMap = new SMap();
  pMap->nnode = n;
  pMap->pE = new SE[n];
  memset(pMap->pE, 0, n*sizeof(SE));
  for (int i = 0; i<n; i++){
    pMap->pE[i].vIndex = i;
    pMap->pE[i].tag = 0;
    SE* p = &pMap->pE[i];
    for (int j = 0; j<n; j++){
      if (matrix[i][j] != 0){
        p->next = new SE();
        p->next->vIndex = j;
        p->next->tag = 0;
        p->next->next = NULL;
        p = p->next;
      }
    }
  }
  return pMap;
}
int BFS(SMap* pMap, int n){
  queue<SE*> q;
  for (int i = 0; i < n; i++){
    if (pMap->pE[i].tag == 0){
      q.push(&pMap->pE[i]);
      while (!q.empty()){
        SE *se = q.front();
        q.pop();
        if (pMap->pE[se->vIndex].tag == 1){
          continue;
        }
        visit(se);
        pMap->pE[se->vIndex].tag = 1;
        SE * p = se;
        while (p->next){
          p = p->next;
          if (pMap->pE[p->vIndex].tag == 0){
            q.push(p);
          }
        }
      }
    }
  }
  return 0;
}
int DFS(SMap* pMap, int n){
  stack<SE*> s;
  for (int i = 0; i < n; i++){
    if (pMap->pE[i].tag == 0){
      s.push(&pMap->pE[i]);
      while (!s.empty()){
        SE *se = s.top();
        s.pop();
        if (pMap->pE[se->vIndex].tag == 1){
          continue;
        }
        visit(se);
        pMap->pE[se->vIndex].tag = 1;
        SE * p = &pMap->pE[se->vIndex];
        stack<SE*> tmp;
        while (p->next){
          p = p->next;
          if (pMap->pE[p->vIndex].tag == 0){
            tmp.push(p);
          }
        }
        while (!tmp.empty()){
          s.push(tmp.top());
          tmp.pop();
        }
      }
    }
  }
  return 0;
}
int main(){
  int map[6][6] = {
    { 0, 1, 0, 1, 0, 0 },
    { 1, 0, 1, 1, 1, 0 },
    { 0, 1, 0, 1, 0, 0 },
    { 1, 1, 1, 0, 1, 0 },
    { 0, 1, 0, 1, 0, 1 },
    { 0, 0, 0, 0, 1, 0 }
  };
  SMap* smap = create_map(map, 6);
// BFS(smap, 6);
  DFS(smap, 6);
  return 0;
}

希望本文所述对大家C语言程序设计有所帮助。

赞 (0)

相关推荐

  • C语言用栈实现十进制转换为二进制的方法示例

    C语言用栈实现十进制转换为二进制的方法示例

    本文实例讲述了C语言用栈实现十进制转换为二进制的方法.分享给大家供大家参考,具体如下: #include<stdio.h> #include<malloc.h> #include<math.h> #include<string.h> #include "process.h" #define SIZE 100 #define STACKINCREMENT 10 #define OK 1 #define ERROR 0 #define TRU

  • C语言数据结构算法之实现快速傅立叶变换

    C语言数据结构算法之实现快速傅立叶变换 本实例将实现二维快速傅立叶变换,同时也将借此实例学习用c语言实现矩阵的基本操作.复数的基本掾作,复习所学过的动态内存分配.文件操作.结构指针的函数调用等内容. 很久以来,傅立叶变换一直是许多领域,如线性系统.光学.概率论.量子物理.天线.数字图像处理和信号分析等的一个基本分析工具,但是即便使用计算速度惊人的计算机计算离散傅立叶变换所花费的时间也常常是难以接受的,因此导致了快速傅立叶变换(FFT)的产生. 本实例将对一个二维数组进行正.反快速傅立叶变换.正傅

  • 详解C语言函数返回值解析

    详解C语言函数返回值解析 程序一: int main() { int *p; int i; int*fun(void); p=fun(); for(i=0;i<3;i++) { printf("%d\n",*p); p++; } return 0; }; int* fun(void) { static int str[]={1,2,3,4,5}; int*q=str; return q; } //不能正确返回 虽然str是在动态变量区,而该动态变量是局部的,函数结束时不保留的.

  • C语言中双向链表和双向循环链表详解

    C语言中双向链表和双向循环链表详解

    双向链表和双向循环链表 和单向链表相比,多了一个前驱结点.如果他为空,那么next和prior都指向自己.而对于双循环链表,只需要最后一个元素的next指向head->next,head->next的prior指向最后一个节点即可. 插入操作 新节点s插入链表,s->next给p结点,s->prior给p->prior,然后,p->prior->next指向s,p->prior再指向s.顺序需要注意 s->next = p; s->prior =

  • C语言数据结构树的双亲表示法实例详解

    C语言数据结构树的双亲表示法实例详解

    1.树的双亲表示法: 树的双亲表示法 2./* bo6-4.c 树的双亲表存储(存储结构由c6-4.h定义)的基本操作(14个) */ Status InitTree(PTree *T) { /* 操作结果: 构造空树T */ (*T).n=0; return OK; } void DestroyTree() { /* 由于PTree是定长类型,无法销毁 */ } typedef struct { int num; TElemType name; }QElemType; /* 定义队列元素类型

  • C语言数据结构之 折半查找实例详解

    C语言数据结构之 折半查找实例详解

    数据结构 折半查找 实例代码: /* 名称:折半查找 语言:数据结构C语言版 编译环境:VC++ 6.0 日期: 2014-3-26 */ #include <stdio.h> #include <malloc.h> #include <windows.h> #define N 11 // 数据元素个数 typedef int KeyType; // 设关键字域为整型 typedef struct // 数据元素类型 { KeyType key; // 关键字域 int

  • C语言实现图的搜索算法示例

    本文实例讲述了C语言实现图的搜索算法.分享给大家供大家参考,具体如下: 在游戏中,常常遇到路径规划问题,用到图的相关算法,我们以简单图来学习. 图通常有两种表示方式,矩阵和邻接表.矩阵表示简单,运算快,但当矩阵是稀疏矩阵的时候就存在空间浪费的问题,并且效率也会下降,而邻接表节约空间,并且由于边是连续访问,时间效率也比较高.在本文中,我们将以邻接表来表示图. #include<queue> #include<stack> using namespace std; struct SE{

  • R语言corrplot相关热图分析美化示例及详细图解

    R语言corrplot相关热图分析美化示例及详细图解

    目录 介绍 1.加载包 2.加载数据 3.绘图 4.个性化设置聚类方法 5.个性化添加矩阵 6.颜色设置 介绍 R corrplot包 提供了一个在相关矩阵上的可视化探索工具,该工具支持自动变量重新排序,以帮助检测变量之间的隐藏模式. corrplot 非常易于使用,并在可视化方法.图形布局.颜色.图例.文本标签等方面提供了丰富的绘图选项.它还提供 p 值和置信区间,以帮助用户确定相关性的统计显著性. corrplot()有大约50个参数,但最常见的参数只有几个.在大多数场景中,我们可以得到一个

  • R语言时间序列TAR阈值自回归模型示例详解

    R语言时间序列TAR阈值自回归模型示例详解

    为了方便起见,这些模型通常简称为TAR模型.这些模型捕获了线性时间序列模型无法捕获的行为,例如周期,幅度相关的频率和跳跃现象.Tong和Lim(1980)使用阈值模型表明,该模型能够发现黑子数据出现的不对称周期性行为. 一阶TAR模型的示例: σ是噪声标准偏差,Yt-1是阈值变量,r是阈值参数, {et}是具有零均值和单位方差的iid随机变量序列. 每个线性子模型都称为一个机制.上面是两个机制的模型. 考虑以下简单的一阶TAR模型: #低机制参数 i1 = 0.3 p1 = 0.5 s1 = 1

  • R语言编程重读微积分泰勒级数示例详解

    R语言编程重读微积分泰勒级数示例详解

    一 理解极限 二 微分学 泰勒级数 如果我是泰勒,我会把思考的起点建立在这样的一个等式上 那么接下来我们直观地感受一下Taylor级数时如何逐渐逼近某个函数的.简单起见,在此选择  sinx作为被拟合的函数. library(ggplot2) library(gganimate) library(av) library(tibble) x = seq(-pi,pi,0.1) n = length(x) xs = rep(x,11) ys = rep(sin(0),n) ts = rep(0,n)

  • R语言实现岭回归的示例代码

    R语言实现岭回归的示例代码

    岭参数的一般选择原则 选择k(或lambda)值,使得: 各回归系数的岭估计基本稳定 用最小二乘估计时符号不合理的回归系数,其岭回归的符号变得合理 回归系数没有不合乎实际意义的绝对值 残差平方和增大的不多 用R语言进行岭回归 这里使用MASS包中的longley数据集,进行岭回归分析(longley数据集中的变量具有显著的多重共线性).从而分析使用岭回归进行多重共线性的解决. 首相将longley数据集中的第一列数据命名为"y",并使用岭回归创建线性模型: 显示当y为因变量,其余各个变

  • C语言实现冒泡排序算法的示例详解

    C语言实现冒泡排序算法的示例详解

    目录 1. 问题描述 2. 问题分析 3. 算法设计 动图演示 4. 程序设计 设计一 设计二 结论 5. 流程框架 6. 代码实现 7. 问题拓展 1. 问题描述 对N个整数(数据由键盘输入)进行升序排列. 2. 问题分析 对于N个数因其类型相同,我们可利用 数组 进行存储. 冒泡排序是在 两个相邻元素之间进行比较交换的过程将一个无序表变成有序表. 冒泡排序的思想:首先,从表头开始往后扫描数组,在扫描过程中逐对比较相邻两个元素的大小. 若相邻两个元素中,前面的元素大于后面的元素,则将它们互换,

  • go语言心跳超时的实现示例

    go语言心跳超时的实现示例

    目录 一.背景 二.心跳超时的实现 2.1 通过select case (设计概念比较多) 2.2 通过time.sleep(简单有效) 三.个人的实现观感 一.背景 本文描述的是客户端接收心跳信息的超时实现.心跳超时,或者接受信息超过限定时间在分布式系统中出现的次数比较多.常见的就有hadoop中节点超时,或者日志中出现timeout的字样. 在学习go语言中,我也根据go语言的机制实现了心跳超时的这个问题.踩过坑,趟过水. 二.心跳超时的实现 2.1 通过select case (设计概念比

  • C语言实现动态链表的示例代码

    C语言实现动态链表的示例代码

    目录 结构体定义已经函数声明 函数实现 创建一个链表 判断链表是否为空 获得链表中节点的个数 在某个特定的位置插入一个元素 获得指定下标的节点的元素 删除一个节点 链表逆序 链表的清空 链表的销毁 链表的遍历 按特定的元素查找节点 按某些特定的条件删除所有符合情况的节点 链表的排序 总结 链表是一种物理存储单元上非连续.非顺序的存储结构,数据元素的逻辑顺序是通过链表中的指针链接次序实现的.链表由一系列结点(链表中每一个元素称为结点)组成,结点可以在运行时动态生成.每个结点包括两个部分:一个是存储

  • 实用的Go语言开发工具及使用示例

    实用的Go语言开发工具及使用示例

    目录 前言 json-to-go yaml-to-go table-to-go 命令行调用 Go 代码调用 前言 孙悟空在花果山称王的时候,特意去了一趟东海,在那里淘到了如意金箍棒.因为身为一个山大王,怎么能没有一件趁手的兵器呢? 作为程序员的我们也一样,除了我们的傍身武器 Ctrl C + V 之外,还要不停的补充我们的武器库.不仅要把 Ctrl C + V 用的高级,更要用的恰到好处. 今天介绍三款小工具,分别可以将 json,yaml 和 table 转成 Go 的 struct.下次再碰

  • 基于C语言实现静态通讯录的示例代码

    基于C语言实现静态通讯录的示例代码

    目录 一.项目要求 二.Contact.h 三.Contact.c 1.静态函数 2.初始化通讯录 3.打印 4.增加联系人信息 5.通过名字查找 6.删除联系人信息 7.修改信息 8.排序通讯录 9.清空通讯录 四.text.c 五.动图展示 一.项目要求 实现一个通讯录 通讯录可以用来存储100个人的信息,每个人的信息包括:姓名.性别.年龄.电话.住址 提供方法: 添加联系人信息 删除指定联系人信息 查找指定联系人信息 修改指定联系人信息 显示所有联系人信息 清空所有联系人 以名字排序所有联

随机推荐