NO IMAGE

轉自:http://lingyibin.javaeye.com/blog/849828

 

我想大部分人都用Floyd或者Dijstra演算法,甚至dfs算過最短路吧。

其實BFS也可以計算最短路。(補充:本文只針對無權圖,有權圖很難用BFS)

當我們用BFS找端對端最短路時,從出發點開始,第一次遍歷到終點時過的那條路徑就是最短的路徑。(讀者可以思考一下為什麼!)

下面就用鄰接表來實現一下BFS最短路,並把路徑打出來。

 

Cpp程式碼
  1. #include<iostream>   
  2. #include<fstream>   
  3. #include<queue>   
  4. using namespace std;   
  5.   
  6. const int MAX = 50;   
  7.   
  8. struct link   
  9. {   
  10.  int data;   
  11.  link *next;   
  12. };   
  13. struct Node   
  14. {   
  15.  int v;     //頂點相關的資訊   
  16.  link *next;   
  17. };   
  18. struct Graph   
  19. {   
  20.   Node node[MAX 1]; //所有的結點   
  21.   int nodeCnt; //用來記錄圖中結點的數目,這裡假設用的是連通圖。假設不連通,稍微改一下本程式就行了,具體操作留給讀者思考!   
  22. };   
  23.   
  24. int visited[MAX 1]; //標誌陣列   
  25. int pa[MAX 1];   
  26.   
  27. /* 讀取檔案中的資料,構造一個鄰接表來表示圖 */    
  28. Graph readGraph()   
  29. {   
  30.     ifstream cin(“c://graph.txt”);   
  31.   
  32.     //表的初始化   
  33.     Graph graph;   
  34.     int i ;   
  35.     for(i = 1; i < MAX; i  )   
  36.     {   
  37.         graph.node[i].v = i;   
  38.         graph.node[i].next = NULL;   
  39.     }   
  40.   
  41.     int n1 = 0,n2 = 0;   
  42.     link *s;   
  43.     graph.nodeCnt = 1;//把結點數初始化為1   
  44.     while(cin>>n1>>n2)   
  45.     {   
  46.         if(graph.nodeCnt < n1) graph.nodeCnt=n1;   
  47.         if(graph.nodeCnt < n2) graph.nodeCnt=n2;   
  48.         s = new link;   
  49.         s->data = n2;   
  50.         s->next=graph.node[n1].next;   
  51.         graph.node[n1].next=s; //從尾部插入   
  52.         //delete(s);   
  53.   
  54.         s=new link;   
  55.         s->data = n1;   
  56.         s->next=graph.node[n2].next;   
  57.         graph.node[n2].next=s; //反過來也賦值,說明本程式測試的是無向圖,如果是有向圖的話讀者應該知道怎麼改了吧!   
  58.         //delete(s);   
  59.     }   
  60.     return graph;   
  61. }   
  62.   
  63. /* 列印鄰接表 */    
  64. void printGraph(Graph graph)   
  65. {   
  66.   link *p;   
  67.   for(int i = 1; i <= graph.nodeCnt; i  )   
  68.   {   
  69.       cout<<graph.node[i].v<<” — “;   
  70.   
  71.       p=graph.node[i].next;   
  72.       while(p!=NULL)   
  73.       {   
  74.           cout<<p->data;   
  75.           p=p->next;   
  76.           if(p != NULL)    
  77.               cout<<“,”;   
  78.       }   
  79.       cout<<endl;   
  80.   }   
  81. }   
  82.   
  83. /* 用BFS求最短路徑 */    
  84. void shortestPath(Graph graph, int s, int d)   
  85. {   
  86.     cout<<“從”<<s<<“到”<<d<<“的bfs最短路求解過程如下:”<<endl;   
  87.     queue<int> que ;   
  88.     link * p = NULL;   
  89.     //int cnt = 0;   
  90.     int parents = s;   
  91.     memset(visited,0,sizeof(visited));   
  92.     memset(pa,0,sizeof(pa));   
  93.     visited[s] = 1;   
  94.     pa[s] = -1;   
  95.     que.push(s);   
  96.     while(!que.empty()){   
  97.         p = graph.node[que.front()].next;   
  98.         parents = que.front();   
  99.         que.pop();   
  100.         //cnt  ;   
  101.         while(p != NULL)   
  102.         {   
  103.             if(!visited[p->data])   
  104.             {   
  105.                 visited[p->data] = 1;   
  106.                 pa[p->data] = parents;   
  107.                 cout<<“訪問:”<<p->data<<endl;   
  108.                 if(p->data == d) //找到了目標結點   
  109.                 {   
  110.                     //cout<<“在第”<<cnt<<“層找到目標結點!(出發點算第一層)”<<endl;   
  111.                     break;   
  112.                 }   
  113.                 que.push(p->data);   
  114.             }   
  115.             p = p->next;   
  116.         }   
  117.     }   
  118.     cout<<“路徑如下:”<<endl;   
  119.     parents = d;   
  120.     //cout<<parents<<” <- “;   
  121.     while(pa[parents] != -1)   
  122.     {   
  123.         cout<<parents<<” <- “;   
  124.         parents = pa[parents];   
  125.     }   
  126.     cout<<parents<<endl;   
  127. }   
  128.   
  129. int main()   
  130. {   
  131.     int s,d;   
  132.     Graph graph = readGraph();   
  133.     printGraph(graph);   
  134.     while(true)   
  135.     {   
  136.         cout<<“請輸入起點和終點:”<<endl;   
  137.         cin>>s>>d;   
  138.         shortestPath(graph, s , d);   
  139.     }   
  140.     return 0;   
  141. }  
#include<iostream>
#include<fstream>
#include<queue>
using namespace std;
const int MAX = 50;
struct link
{
int data;
link *next;
};
struct Node
{
int v;     //頂點相關的資訊
link *next;
};
struct Graph
{
Node node[MAX 1]; //所有的結點
int nodeCnt; //用來記錄圖中結點的數目,這裡假設用的是連通圖。假設不連通,稍微改一下本程式就行了,具體操作留給讀者思考!
};
int visited[MAX 1]; //標誌陣列
int pa[MAX 1];
/* 讀取檔案中的資料,構造一個鄰接表來表示圖 */ 
Graph readGraph()
{
ifstream cin("c://graph.txt");
//表的初始化
Graph graph;
int i ;
for(i = 1; i < MAX; i   )
{
graph.node[i].v = i;
graph.node[i].next = NULL;
}
int n1 = 0,n2 = 0;
link *s;
graph.nodeCnt = 1;//把結點數初始化為1
while(cin>>n1>>n2)
{
if(graph.nodeCnt < n1) graph.nodeCnt=n1;
if(graph.nodeCnt < n2) graph.nodeCnt=n2;
s = new link;
s->data = n2;
s->next=graph.node[n1].next;
graph.node[n1].next=s; //從尾部插入
//delete(s);
s=new link;
s->data = n1;
s->next=graph.node[n2].next;
graph.node[n2].next=s; //反過來也賦值,說明本程式測試的是無向圖,如果是有向圖的話讀者應該知道怎麼改了吧!
//delete(s);
}
return graph;
}
/* 列印鄰接表 */ 
void printGraph(Graph graph)
{
link *p;
for(int i = 1; i <= graph.nodeCnt; i   )
{
cout<<graph.node[i].v<<" -- ";
p=graph.node[i].next;
while(p!=NULL)
{
cout<<p->data;
p=p->next;
if(p != NULL) 
cout<<",";
}
cout<<endl;
}
}
/* 用BFS求最短路徑 */ 
void shortestPath(Graph graph, int s, int d)
{
cout<<"從"<<s<<"到"<<d<<"的bfs最短路求解過程如下:"<<endl;
queue<int> que ;
link * p = NULL;
//int cnt = 0;
int parents = s;
memset(visited,0,sizeof(visited));
memset(pa,0,sizeof(pa));
visited[s] = 1;
pa[s] = -1;
que.push(s);
while(!que.empty()){
p = graph.node[que.front()].next;
parents = que.front();
que.pop();
//cnt   ;
while(p != NULL)
{
if(!visited[p->data])
{
visited[p->data] = 1;
pa[p->data] = parents;
cout<<"訪問:"<<p->data<<endl;
if(p->data == d) //找到了目標結點
{
//cout<<"在第"<<cnt<<"層找到目標結點!(出發點算第一層)"<<endl;
break;
}
que.push(p->data);
}
p = p->next;
}
}
cout<<"路徑如下:"<<endl;
parents = d;
//cout<<parents<<" <- ";
while(pa[parents] != -1)
{
cout<<parents<<" <- ";
parents = pa[parents];
}
cout<<parents<<endl;
}
int main()
{
int s,d;
Graph graph = readGraph();
printGraph(graph);
while(true)
{
cout<<"請輸入起點和終點:"<<endl;
cin>>s>>d;
shortestPath(graph, s , d);
}
return 0;
}

 

 

輸入檔案graph.txt裡資料格式如下:

 

Txt程式碼
  1. 1 2    
  2. 1 3    
  3. 1 4    
  4. 2 4