C语言如何实现图的搜索算法示例-创新互联
这篇文章给大家分享的是有关C语言如何实现图的搜索算法示例的内容。小编觉得挺实用的,因此分享给大家做个参考,一起跟随小编过来看看吧。
成都创新互联专注为客户提供全方位的互联网综合服务,包含不限于成都做网站、成都网站设计、新兴网络推广、重庆小程序开发公司、新兴网络营销、新兴企业策划、新兴品牌公关、搜索引擎seo、人物专访、企业宣传片、企业代运营等,从售前售中售后,我们都将竭诚为您服务,您的肯定,是我们大的嘉奖;成都创新互联为所有大学生创业者提供新兴建站搭建服务,24小时服务热线:028-86922220,官方网址:www.cdcxhl.com在游戏中,常常遇到路径规划问题,用到图的相关算法,我们以简单图来学习。
图通常有两种表示方式,矩阵和邻接表。矩阵表示简单,运算快,但当矩阵是稀疏矩阵的时候就存在空间浪费的问题,并且效率也会下降,而邻接表节约空间,并且由于边是连续访问,时间效率也比较高。在本文中,我们将以邻接表来表示图。
#include#include 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 pE[i].vIndex = i; pMap->pE[i].tag = 0; SE* p = &pMap->pE[i]; for (int j = 0; j 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 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 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 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语言如何实现图的搜索算法示例”这篇文章就分享到这里了,希望以上内容可以对大家有一定的帮助,让大家可以学到更多知识,如果觉得文章不错,可以把它分享出去让更多的人看到吧!
另外有需要云服务器可以了解下创新互联建站www.cdcxhl.com,海内外云服务器15元起步,三天无理由+7*72小时售后在线,公司持有idc许可证,提供“云服务器、裸金属服务器、高防服务器、香港服务器、美国服务器、虚拟主机、免备案服务器”等云主机租用服务以及企业上云的综合解决方案,具有“安全稳定、简单易用、服务可用性高、性价比高”等特点与优势,专为企业上云打造定制,能够满足用户丰富、多元化的应用场景需求。
本文题目:C语言如何实现图的搜索算法示例-创新互联
当前链接:http://pwwzsj.com/article/dejoop.html