C語言實(shí)現(xiàn)圖的搜索算法示例
更新時(shí)間：2017年06月08日 11:09:21 作者：typ2004
這篇文章主要介紹了C語言實(shí)現(xiàn)圖的搜索算法,結(jié)合具體實(shí)例形式分析了C語言實(shí)現(xiàn)圖的定義及搜索相關(guān)操作技巧,需要的朋友可以參考下
本文實(shí)例講述了C語言實(shí)現(xiàn)圖的搜索算法。分享給大家供大家參考，具體如下：
在游戲中，常常遇到路徑規(guī)劃問題，用到圖的相關(guān)算法，我們以簡單圖來學(xué)習(xí)。
圖通常有兩種表示方式，矩陣和鄰接表。矩陣表示簡單，運(yùn)算快，但當(dāng)矩陣是稀疏矩陣的時(shí)候就存在空間浪費(fèi)的問題，并且效率也會下降，而鄰接表節(jié)約空間，并且由于邊是連續(xù)訪問，時(shí)間效率也比較高。在本文中，我們將以鄰接表來表示圖。
#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語言程序設(shè)計(jì)有所幫助。
相關(guān)文章
這篇文章主要介紹了C++變量和基本類型,,一定要注意局部變量與全局變量的作用范圍,需要的朋友可以參考下,希望能夠給你帶來幫助2021-10-10
今天就跟大家聊聊有關(guān)C++中replace()函數(shù)的作用是什么,可能很多人都不太了解,為了讓大家更加了解,這篇文章主要給大家介紹了關(guān)于C++中replace()?函數(shù)的基本用法,需要的朋友可以參考下2021-11-11
解讀堆排序算法及用C++實(shí)現(xiàn)基于最大堆的堆排序示例
把待排序的數(shù)組構(gòu)造出最大堆是進(jìn)行堆排序操作的基本方法,這里將帶大家來解讀堆排序算法及用C++實(shí)現(xiàn)基于最大堆的堆排序示例,首先從堆排序的概念開始:2016-06-06
這篇文章主要為大家介紹了C語言中雙指針?biāo)惴ǖ氖纠斀?，有需要的朋友可以借鑒參考下，希望能夠有所幫助2022-02-02
C++ 風(fēng)靡一時(shí)的連連看游戲的實(shí)現(xiàn)流程詳解
游戲“連連看”是源自臺灣的桌面小游戲，自從流入大陸以來風(fēng)靡一時(shí)，也吸引眾多程序員開發(fā)出多種版本的“連連看”。這其中，顧芳編寫的“阿達(dá)連連看”以其精良的制作廣受好評，這也成為顧方“阿達(dá)系列軟件”的核心產(chǎn)品。并于2004年，取得國家版權(quán)局的計(jì)算機(jī)軟件登記證書2021-11-11
本篇文章是C語言編程篇，主要為大家介紹C語言編程中數(shù)據(jù)在內(nèi)存中存儲解析，有需要的朋友可以借鑒參考下，希望可以有所幫助2021-09-09
C語言非遞歸算法解決快速排序與歸并排序產(chǎn)生的棧溢出
上期我們講完了排序算法下，不知道小伙伴們有沒有發(fā)現(xiàn)一個問題，快速排序和歸并排序我們都是用遞歸來實(shí)現(xiàn)的，可能有小伙伴會問，如果說數(shù)據(jù)量很多話，棧區(qū)空間會不會不夠用呢？這期我們就來解決使用遞歸實(shí)現(xiàn)的排序?qū)е聴Ｒ绯鋈绾谓鉀Q2022-04-04
函數(shù)的返回值是指函數(shù)被調(diào)用之后,執(zhí)行函數(shù)體中的程序段所取得的并返回給主調(diào)函數(shù)的值,下面這篇文章主要給大家介紹了關(guān)于C語言函數(shù)返回值的相關(guān)資料,需要的朋友可以參考下2022-01-01
C++ boost 時(shí)間與日期處理詳細(xì)介紹
這篇文章主要介紹了C++ boost 時(shí)間與日期處理詳細(xì)介紹的相關(guān)資料,這里提供實(shí)例代碼，及實(shí)現(xiàn)效果，需要的朋友可以參考下2016-11-11
這篇文章主要介紹了C++ 中的this指針詳解及實(shí)例的相關(guān)資料,this指針是類的一個自動生成、自動隱蔽的私有成員，它存在于類的非靜態(tài)成員中，指向被調(diào)用函數(shù)所在的對象。需要的朋友可以參考下2017-07-07