int eNum; /*边的个数 */
int visited[maxnum]; /*标记这个顶点是否被访问过,0表示没有,1表示已经被访问过*/
public:
void graph(int a,int b); /*构造函数 */
int InitGraph(); /*图类的初始化函数*/ void print(); /*输出邻接矩阵 */ void dfs(int i); /*深度优先搜索 */ void DFS();}
4.2 类的成员函数设计
/*构造函数*/
void Graph::graph(int a,int b)
{
cout<<\创建顶点数为\边数\的无向图\ vNum=a; eNum=b; /*为了防止原先存在e[][]中的数据对今后的搜索造成影响,所以对其进行初始化*/ for(int i=0;i< vNum;i++) { for(int j=0;j< vNum;j++) {e[i][j] = 0; } } }
int Graph::InitGraph() {
int i,j,temp,flag=0; for (i=0;i
/*输入各个边的具体情况*/
cout<<\请输入各个边的权值\ for (i=0;i 第 4 页 共 21 页 cin>>temp; e[i][j]=temp; e[j][i]=temp; if(temp)flag++; if(flag==eNum) { cout<<\初始化无向图邻接矩阵完毕\ return 0; } } } return 1; } /*输出邻接矩阵*/ void Graph::print() { cout<<\邻接矩阵为\ int i,j; for (i=0;i /*深度优先搜索*/ void Graph::dfs(int i) { cout< visited[i]=1; /*标记i边已经被访问*/ for(int j=0;j { if((e[i][j]!=0)&&(visited[j]==0)) /*假如j点与i点相连,并且j点还没有被访问 过*/ {dfs(j); } /*递归方法,对j点进行深度优先搜索*/ } } void Graph::DFS() { int i; /*首先把所有点都设置成没有访问过 */ for(i=0;i 第 5 页 共 21 页 visited[i]=0; } /*深度优先搜索*/ for(i=0;i { if(visited[i]==0) { /*假如i点没有被访问过*/ dfs(i); /*对以邻接矩阵表示的图，以序号为i的顶点为出发点进行DFS*/ } } cout< 4.3 主函数设计 int main() { /*以下两个语句用来建立用邻接矩阵表示的图*/ Graph graph(4,3); graph.InitGraph(); /*创建图*/ graph.print(); cout<<\深度优先搜索的结果:\ graph.DFS(); return 0; } 5、基于控制台的应用程序设计 5.1 程序运行结果 程序运行结果如图1所示。 第 6 页 共 21 页 图1程序运行结果 5.2运行结果分析 程序运行后首先创建了图类的对象，调用构造函数，产生一个顶点数为5，边数为 6的无向图，然后初始化这个图，从键盘输入每个顶点的信息（a b c d e）和每条边的权值。在主函数中直接调用邻接矩阵输出函数和深度优先搜索结果。 6、基于MFC的图形界面程序开发 MFC的图形界面程序设计可在上述类设计的基础上进行改造，MFC的图形界面程序与DOS界面程序的主要不同点是：MFC图形界面程序与DOS界面程序的输入输出方式不同，DOS界面程序采用字符交互式实现数据输入输出，主要通过cin，cout等I/O流实现，而MFC的图形程序界面采用标准Windows窗口和控件实现输入输出，因此必须在MFC类的框架下加入上面所设计的图类，并通过图形界面的输入输出改造来完成。 第 7 页 共 21 页
