C語言實現圖的搜索算法示例。本站提示廣大學習愛好者:(C語言實現圖的搜索算法示例)文章只能為提供參考,不一定能成為您想要的結果。以下是C語言實現圖的搜索算法示例正文
作者:typ2004
這篇文章主要介紹了C語言實現圖的搜索算法,結合具體實例形式分析了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語言程序設計有所幫助。