鄰接表實現Dijkstra算法以及DFS與BFS算法，dijkstrabfs
//============================================================================
// Name : ListDijkstra.cpp
// Author : fffff
// Version :
// Copyright : Your copyright notice
// Description : Hello World in C++, Ansi-style
//============================================================================
#include<iostream>
#include<cstdlib>
#include<queue>
using namespace std;
#define MAXSIZE 100
#define INF (~(0x1<<31)) //最大值 0x7FFFFFFF
class ListUDG{
/*
* 內部類
*/
private:
/*
* 鄰接表中的邊節點
* ivex:下一個節點的編號
* nextEdge:指向下一個邊節點的指針
*/
class Enode{
public:
int ivex;
int weight;
Enode *nextEdge;
};
/*
* 鄰接表中的頂點節點
* data:頂點節點的數據
* firstEdge:頂點節點的第一條邊
*/
class Vnode{
public:
char data;
Enode *firstEdge;
};
private:
int mVexNum;//頂點個數
int mEdgNum;//邊的條數
Vnode mVexs[MAXSIZE];
bool visited[MAXSIZE];
public:
ListUDG();
ListUDG(char vexs[],int vlen,char edge[][2],int elen,int weigh[]);
~ListUDG();
char rChar();
int getPost(char ch);
int getmVexNum();
int getmEdgNum();
Vnode getVexs(int i){
return mVexs[i];
};
int getWeight(int v,int u);
void print();
void BFS();
void DFS();
void DFSK(int k);
void Dijkstra(ListUDG *listudg,int v,int pre[],int dist[]);
void trace(ListUDG *listudg,int v,int u,int pre[]);
private:
char readChar();
int getPosition(char ch);
void LinkLast(Enode *list,Enode *node);
};
ListUDG::ListUDG(char vexs[],int vlen,char edge[][2],int elen,int weigh[]){
/*
* 初始化頂點數與邊的條數
*/
mVexNum = vlen;
mEdgNum = elen;
/*
* 初始化鄰接表中的頂點節點
*/
for(int i=0;i<mVexNum;i++){
mVexs[i].data = vexs[i];
mVexs[i].firstEdge = NULL;
}
/*
* 初始化鄰接表中的邊節點
*/
for(int i=0;i<mEdgNum;i++){
char first = edge[i][0];
char second = edge[i][1];
int start = getPosition(first);
int end = getPosition(second);
Enode *enode1 = new Enode;
enode1->ivex = end;
enode1->weight = weigh[i];
enode1->nextEdge = NULL;
if(mVexs[start].firstEdge==NULL)
mVexs[start].firstEdge = enode1;
else
LinkLast(mVexs[start].firstEdge,enode1);
Enode *enode2 = new Enode;
enode2->ivex = start;
enode2->weight = weigh[i];
enode2->nextEdge = NULL;
if(mVexs[end].firstEdge==NULL)
mVexs[end].firstEdge=enode2;
else
LinkLast(mVexs[end].firstEdge,enode2);
}
};
ListUDG::ListUDG(){
/*
* 初始化頂點數與邊的條數
*/
cout<<"input num of Vexs and Edges : ";
cin>>mVexNum>>mEdgNum;
/*
* 初始化鄰接表中的頂點節點
*/
for(int i=0;i<mVexNum;i++){
cout<<"input data of "<<i<<" Vex:";
mVexs[i].data = readChar();
mVexs[i].firstEdge = NULL;
}
/*
* 初始化鄰接表中的邊節點
*/
for(int i=0;i<mEdgNum;i++){
cout<<"input edge("<<i<<"):";
char first = readChar();
char second = readChar();
int start = getPosition(first);
int end = getPosition(second);
cout<<"input weight of the edge:";
int weight;
cin>>weight;
Enode *enode1 = new Enode;
enode1->ivex = end;
enode1->weight = weight;
/********************-----ERROR-----********************
* 兩個構造方法都忘掉此句,導致出錯,
* 出錯地方在調用方法LinkLast的時候無法判斷nextEdge是否為空
* 因為nextEdge沒有被賦值
*******************************************************/
enode1->nextEdge = NULL;
if(mVexs[start].firstEdge==NULL)
mVexs[start].firstEdge = enode1;
else
LinkLast(mVexs[start].firstEdge,enode1);
Enode *enode2 = new Enode;
enode2->ivex = start;
enode2->weight = weight;
enode2->nextEdge = NULL;
if(mVexs[end].firstEdge==NULL)
mVexs[end].firstEdge = enode2;
else
LinkLast(mVexs[end].firstEdge,enode2);
}
};
ListUDG::~ListUDG(){
};
char ListUDG::rChar(){
return readChar();
};
int ListUDG::getPost(char ch){
return getPosition(ch);
};
int ListUDG::getmVexNum(){
return mVexNum;
};
int ListUDG::getmEdgNum(){
return mEdgNum;
};
int ListUDG::getWeight(int v,int u){
Enode *enode;
if(v==u)
return 0;
else{
enode = mVexs[v].firstEdge;
while(enode){
if(enode->ivex==u)
return enode->weight;
else
enode = enode->nextEdge;
}
return INF;
}
};
void ListUDG::print(){
cout<<"ListUDG"<<endl;
for(int i=0;i<mVexNum;i++){
cout<<i<<" ("<<mVexs[i].data<<"): ";
Enode *p = mVexs[i].firstEdge;
while(p){
cout<<p->ivex<<"("<<mVexs[p->ivex].data<<")["<<p->weight<<"] ";
p = p->nextEdge;
}
cout<<endl;
}
return ;
};
char ListUDG::readChar(){
char cha;
cin>>cha;
while(!((cha>='a'&&cha<='z')||(cha>='A'&&cha<='Z'))){
cin>>cha;
}
return cha;
};
int ListUDG::getPosition(char ch){
for(int i = 0;i<mVexNum;i++){
if(mVexs[i].data==ch)
return i;
}
return -1;
}
void ListUDG::LinkLast(Enode*list,Enode *node){
Enode *p = list;
while(p->nextEdge)
p = p->nextEdge;
p->nextEdge = node;
return;
};
/*
* Dijkstra 算法----最短路徑
*/
void ListUDG::Dijkstra(ListUDG *listudg,int v,int pre[],int dist[]){
bool s[MAXSIZE];
/*
* 第一步:初始化S集合以及距離dist
*/
for(int i=0;i<listudg->getmVexNum();i++){
s[i] = false;
dist[i] = listudg->getWeight(v,i);
if(dist[i]==INF)
pre[i] = -1;
else
pre[i] = v;
}
s[v] = true;
dist[v] = 0;
/*
* 第二步:尋找dist中的最小值加入到S集合中
*/
for(int i=1;i<listudg->getmVexNum();i++){
int min = INF;
int u = v;
for(int j=0;j<listudg->getmVexNum();j++){
if(s[j]==false&&dist[j]<min){
min = dist[j];
u = j;
}
}
s[u] = true;//將頂點u加入到集合S中
/*
* 第三步:更新dist
*/
for(int j=0;j<listudg->mVexNum;j++){
if(s[j]==false&&listudg->getWeight(u,j)<INF){
int newdist = dist[u] + listudg->getWeight(u,j);
if(newdist<dist[j]){
dist[j] = newdist;
pre[j] = u;
}
}
}
}
};
void ListUDG::trace(ListUDG *listudg,int v,int u,int pre[]){
int start = v;
int end = u;
while(start!=end){
cout<<listudg->mVexs[end].data<<"<---";
end = pre[end];
}
cout<<listudg->mVexs[start].data<<endl;
};
/*
* 廣度優先搜索鄰接表
*/
void ListUDG::BFS(){
for(int i=0;i<MAXSIZE;i++)
visited[i] = false;
queue<int>que;
que.push(0);
visited[0] = true;
int out;
Enode *outNext;
while(!que.empty()){
out = que.front();
outNext = mVexs[out].firstEdge;
que.pop();
cout<<mVexs[out].data<<" ";
/****************-----ERROR-----*****************
* 此處剛開始將判斷條件visited[outNext->ivex]==false
* 寫入while循環的判斷語句中,導致某一個頂點的邊鏈表沒有
* 訪問完就結束了循環(可能某邊之前已經訪問過),丟掉了後面
* 的節點
************************************************/
while(outNext!=NULL){
if(visited[outNext->ivex]==false){
que.push(outNext->ivex);
visited[outNext->ivex] = true;
outNext = outNext->nextEdge;
}else
outNext = outNext->nextEdge;
}
}
cout<<endl;
};
void ListUDG::DFS(){
for(int i=0;i<MAXSIZE;i++)
visited[i] = false;
for(int i=0;i<mVexNum;i++)
if(visited[i]==false)
DFSK(i);
cout<<endl;
};
void ListUDG::DFSK(int k){
visited[k]=true;
cout<<mVexs[k].data<<" ";
Enode *enode = mVexs[k].firstEdge;
while(enode){
if(visited[enode->ivex]==false){
DFSK(enode->ivex);
enode = enode->nextEdge;
}
else
/************-----ERROR-----*************
*開始時候忘掉了寫此句,導致頂點的邊鏈表沒有訪問完
*而到時enode沒有向後移動,從而導致循環無法結束,因此
*程序死循環
****************************************/
enode = enode->nextEdge;
}
return ;
}
int main(){
char vexs[]={'a','b','c','d','e','f','g'};
char edges[][2]={
{'a','b'},
{'a','d'},
{'a','g'},
{'b','f'},
{'c','d'},
{'c','g'},
{'d','f'},
{'e','g'},
{'f','g'}
};
int pre[MAXSIZE];
int dist[MAXSIZE];
int weight[]={1,3,2,2,6,4,3,7,1};
int vlen = sizeof(vexs)/sizeof(vexs[0]);
int elen = sizeof(edges)/sizeof(edges[0]);
ListUDG *listudg1 = new ListUDG(vexs,vlen,edges,elen,weight);
listudg1->print();
listudg1->BFS();
listudg1->DFS();
listudg1->Dijkstra(listudg1,0,pre,dist);
listudg1->trace(listudg1,0,2,pre);
return 0;
}
運行結果如下
ListUDG
0 (a): 1(b)[1] 3(d)[3] 6(g)[2]
1 (b): 0(a)[1] 5(f)[2]
2 (c): 3(d)[6] 6(g)[4]
3 (d): 0(a)[3] 2(c)[6] 5(f)[3]
4 (e): 6(g)[7]
5 (f): 1(b)[2] 3(d)[3] 6(g)[1]
6 (g): 0(a)[2] 2(c)[4] 4(e)[7] 5(f)[1]
a b d g f c e
a b f d c g e
c<---g<---a
