鄰接矩陣實現Dijkstra算法以及BFS與DFS算法，dijkstrabfs
//============================================================================
// Name : MatrixUDG.cpp
// Author : fffff
// Version :
// Copyright : Your copyright notice
// Description : Hello World in C++, Ansi-style
//============================================================================
#include<iostream>
#include<cstdlib>
#include<queue>
#define maxsize 100
#define far 10000
using namespace std;
class MatrixUDG{
public:
char mVerxs[maxsize];
int mVerNum;
int mEdgeNum;
public:
int mMatrix[maxsize][maxsize];
MatrixUDG();
MatrixUDG(char vexs[],int vlen,char edge[][2],int elen);
~MatrixUDG();
void print();
int getPosition(char ch);
char getChar(int place);
char readChar();
};
MatrixUDG::MatrixUDG(char vexs[],int vlen,char edge[][2],int elen){
this->mVerNum = vlen;
this->mEdgeNum = elen;
for(int i=0;i<mVerNum;i++)
for(int j=0;j<mVerNum;j++)
mMatrix[i][j] = far;
for(int i=0;i<mVerNum;i++){
mVerxs[i] = vexs[i];
}
for(int i=0;i<mEdgeNum;i++){
int start = getPosition(edge[i][0]);
int end = getPosition(edge[i][1]);
int weight;
cout<<"input weight of ("<<edge[i][0]<<","<<edge[i][1]<<") : ";
cin>>weight;
mMatrix[start][end]=weight;
mMatrix[end][start]=weight;
}
};
MatrixUDG::MatrixUDG(){
cout<<"input num of verx and edge:";
cin>>mVerNum>>mEdgeNum;
cout<<"input verxs:";
for(int i=0;i<mVerNum;i++){
mVerxs[i] = readChar();
}
for(int i=0;i<mEdgeNum;i++){
cout<<"edge("<<i<<") : ";
char startChar = readChar();
char endChar = readChar();
int start = getPosition(startChar);
int end = getPosition(endChar);
int weight;
cout<<"input weight of ("<<startChar<<","<<endChar<<") : ";
cin>>weight;
mMatrix[start][end]=weight;
mMatrix[end][start]=weight;
}
};
MatrixUDG::~MatrixUDG(){
};
void MatrixUDG::print(){
for(int i=0;i<mVerNum;i++){
for(int j=0;j<mVerNum;j++){
cout<<mMatrix[i][j]<<" ";
}
cout<<endl;
}
}
int MatrixUDG::getPosition(char ch){
for(int i=0;i<mVerNum;i++){
if(mVerxs[i]==ch)
return i;
}
return -1;
};
char MatrixUDG::getChar(int place){
return mVerxs[place];
};
char MatrixUDG::readChar(){
char cha;
cin>>cha;
while(!((cha>='a'&&cha<='z')||(cha>='A'&&cha<='Z')))
cin>>cha;
return cha;
};
void Dijkstra(int n,int v,int *dist,int *pre,int weight[][maxsize]){
/*
* 第一步:初始化s[n],dist,pre
*/
bool s[n];
for(int i=0;i<n;i++){
dist[i] = weight[v][i];
s[i] = false;
if(dist[i]==far)
pre[i] = -1;
else
pre[i] = v;
}
s[v] = true;
dist[v] = 0;
/*
* 第二步:尋找出dist最小的頂點加入到s中
*/
for(int i=1;i<n;i++){
int temp = far;
int u = v;
for(int j=0;j<n;j++){
if(!s[j]&&dist[j]<temp){
temp = dist[j];
u = j;
}
}
s[u] = true;
/*
* 第三步:更新dist
*/
for(int j=0;j<n;j++){
if(!s[j]&&weight[u][j]<far){
int newdist = dist[u]+weight[u][j];
if(newdist<dist[j]){
dist[j] = newdist;
pre[j] = u;
}
}
}
}
}
void printTrace(MatrixUDG*PG,int *pre,int v,int u){
int start = v;
int end = u;
char cha;
while(end!=start){
cha = PG->getChar(end);
cout<<cha<<"<--";
end = pre[end];
}
cout<<PG->getChar(start)<<endl;
}
bool visited[maxsize];
void Dfsk(MatrixUDG *PG,int k){
visited[k] = true;
cout<<PG->getChar(k)<<" ";
for(int i=0;i<PG->mVerNum;i++)
if(PG->mMatrix[k][i]!=far&&visited[i]==false)
Dfsk(PG,i);
}
void Dfs(MatrixUDG *PG){
for(int i=0;i<PG->mVerNum;i++)
if(!visited[i])
Dfsk(PG,i);
cout<<endl;
}
void Bfs(MatrixUDG *PG){
queue<int>que;
que.push(0);
int place;
while(!que.empty()){
place = que.front();
que.pop();
visited[place] = true;
cout<<PG->getChar(place)<<" ";
for(int i=0;i<PG->mVerNum;i++){
if(PG->mMatrix[place][i]!=far&&visited[i]==false){
que.push(i);
/*
* 開始時掉了visited[i] = true;導致出錯
* 因為有可能在隊列中的頂點還沒有出來,在後面再一次的進入隊列
* 因此必須在進入隊列後將其設為已訪問來防止再次進入而導致的重復訪問
*/
visited[i] = true;
}
}
}
}
int main(){
char verx[] = {'A','B','C','D','E','F','G'};
char edge[][2] = {
{'A','C'},
{'A','E'},
{'B','D'},
{'B','E'},
{'B','G'},
{'C','F'},
{'D','F'},
{'E','G'},
{'F','G'}
};
int vlen = sizeof(verx)/sizeof(verx[0]);
int elen = sizeof(edge)/sizeof(edge[0]);
MatrixUDG *PG = new MatrixUDG(verx,vlen,edge,elen);
int dist[vlen];
int pre[vlen];
int startVex =4;
Dijkstra(vlen,startVex,dist,pre,PG->mMatrix);
PG->print();
printTrace(PG,pre,4,5);
for(int i=0;i<maxsize;i++){
visited[i] = false;
}
Dfs(PG);
for(int i=0;i<maxsize;i++){
visited[i] = false;
}
Bfs(PG);
return 0;
}
