本篇文章主要介绍了"邻接矩阵实现Dijkstra算法以及BFS与DFS算法"，主要涉及到方面的内容，对于C/C++jrs看球网直播吧_低调看直播体育app软件下载_低调看体育直播感兴趣的同学可以参考一下：
//============================================================================//...
//============================================================================
// Name : MatrixUDG.cpp
// Author : fffff
// Version :
// Copyright : Your copyright notice
// Description : Hello World in C++, Ansi-style
//============================================================================#include#include#include
#define maxsize 100
#define far 10000
usingnamespace 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<>)
for(int j=0;j<>)
mMatrix[i][j] = far;
for(int i=0;i<>){
mVerxs[i] = vexs[i];
}
for(int i=0;i<>){
int start = getPosition(edge[i][0]);
int end = getPosition(edge[i][1]);
int weight;
cout<<"input weight of ("<<>0]<<","<<>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<>){
mVerxs[i] = readChar();
}
for(int i=0;i<>){
cout<<"edge("<<>") : ";
char startChar = readChar();
char endChar = readChar();
int start = getPosition(startChar);
int end = getPosition(endChar);
int weight;
cout<<"input weight of ("<<>","<<>") : ";
cin>>weight;
mMatrix[start][end]=weight;
mMatrix[end][start]=weight;
}
};
MatrixUDG::~MatrixUDG(){
};
void MatrixUDG::print(){
for(int i=0;i<>){
for(int j=0;j<>){
cout<<>"";
}
cout<<endl;
}
}
int MatrixUDG::getPosition(char ch){
for(int i=0;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<>){
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<>){
int temp = far;
int u = v;
for(int j=0;j<>){
if(!s[j]&&dist[j]<temp){
temp = dist[j];
u = j;
}
}
s[u] = true;
/* * 第三步:更新dist
*/for(int j=0;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<<>"<--";
end = pre[end];
}
cout<getChar(start)<<endl;
}
bool visited[maxsize];
void Dfsk(MatrixUDG *PG,int k){
visited[k] = true;
cout<getChar(k)<<"";
for(int i=0;imVerNum;i++)
if(PG->mMatrix[k][i]!=far&&visited[i]==false)
Dfsk(PG,i);
}
void Dfs(MatrixUDG *PG){
for(int i=0;imVerNum;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<getChar(place)<<"";
for(int i=0;imVerNum;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<>){
visited[i] = false;
}
Dfs(PG);
for(int i=0;i<>){
visited[i] = false;
}
Bfs(PG);
return0;
}
以上就介绍了邻接矩阵实现Dijkstra算法以及BFS与DFS算法，包括了方面的内容，希望对C/C++jrs看球网直播吧_低调看直播体育app软件下载_低调看体育直播有兴趣的朋友有所帮助。
本文网址链接：http://www.codes51.com/article/detail_352252.html
