数据结构--DFS和BFS

专题--深度优先搜索与广度优先搜索

知识点：

　　邻接矩阵结构；

　　DFS深度优先搜索；

　　BFS广度优先搜索;

　　Dijkstra算法。

 1 #include <iostream>
 2 #include <queue>
 3 using namespace std;
 4 
 5 typedef char VertexType;
 6 typedef int EdgeType;
 7 const int MAXVEX=100;
 8 const int INFINITY=65535;
 9 
10 struct MGraph
11 {
12     VertexType vexs[MAXVEX];      //顶点表
13     EdgeType arc[MAXVEX][MAXVEX]; //邻接矩阵，可看做边表
14     int numVertexes,numEdges;     //图中当前的顶点数和边数
15 };
16 
17 //深度优先
18 void DFS(MGraph,int);  //函数前置声明
19 bool visited[MAXVEX];
20 void DFSTraverse(MGraph G)
21 {
22     for(int i=0;i<G.numVertexes;++i)
23         visited[i]=false;
24     for(int i=0;i<G.numVertexes;++i)
25         if(!visited[i])
26             DFS(G,i);   //若是连通图，只会执行一次
27 }
28 void DFS(MGraph G,int i)
29 {
30     visited[i]=true;
31     cout<<G.vexs[i]<<endl;
32 
33     for(int j=0;j<G.numVertexes;++j)
34         if(G.arc[i][j]==1&&!visited[j])  //有连接且还未访问
35             DFS(G,j);    //递归调用
36 }
37 //广度优先
38 void BFSTraverse(MGraph G)
39 {
40     for(int i=0;i<G.numVertexes;++i)
41         visited[i]=false;
42     queue<int> Q;  //申请一个辅助队列
43     for(int i=0;i<G.numVertexes;++i)
44     {
45         visited[i]=true;
46         cout<<G.vexs[i]<<endl;
47 
48         Q.push(i); //入队列
49         while(!Q.empty())
50         {
51             i=Q.front(); //取出首元素
52             Q.pop();   //删除队列首元素
53             for(int j=0;j<G.numVertexes;++j)
54             {
55                 if(G.arc[i][j]==1&&!visited[j])
56                 {
57                     visited[j]=true;
                       cout<<G.vexs[j]<<endl;
58                     Q.push(j);   //入队列
59                 }
60             }
61         }
62     }
63 
64 }

迪杰斯特拉算法求最短路径：

 1 //迪杰斯特拉算法
 2 typedef int PathArc[MAXVEX];
 3 typedef int ShortPathTable[MAXVEX];
 4 //int P[MAXVEX];
 5 //int D[MAXVEX];
 6 void DijkstraShortPath(MGraph G,int s,PathArc *P,ShortPathTable *D)
 7 {
 8     int final[MAXVEX];
 9     for(int i=0;i<G.numVertexes;++i)
10     {//注意初始化
11         final[i]=0;  //final[i]=1表示求得顶点s至顶点i的最短路径
12         (*P)[i]=s;
13         (*D)[i]=G.arc[s][i];
14     }
15 
16     (*D)[s]=0;
17     final[s]=1;
18 
19     int min;
20     for(int i=0;i<G.numVertexes;++i)
21     {
22         min=INFINITY;
23         int k;
24         for(int j=0;j<G.numVertexes;++j)
25         {
26             if(!final[j]&&(*D)[j]<min)   //!final[j]能保证找到的最近点不是自己
27             {
28                 min=(*D)[j];
29                 k=j;
30             }
31         }
32         final[k]=1;
33 
34         for(int j=0;j<G.numVertexes;++j)
35         {
36             if(!final[j]&&(min+G.arc[k][j]<(*D)[j]))
37             {
38                 (*D)[j]=min+G.arc[k][j];
39                 (*P)[j]=k;
40             }
41         }
42     }
43 }