求无向图中求两点间的所有简单路径实验报告解读(2)

{

delete []mark;

for(int i=0;i

for(i=0;i

int next(int v1,int v2) //获得v1的邻居v2 { int i;

for(i=v2+1;i

void setEdge(int v1,int v2) //设置有向图的边 {

if(matrix[v1][v2]==0) numEdge++; matrix[v1][v2]=1; }

int getMark(int v) //获取顶点标记的值 { return mark[v];}

int setMark(int v,int val) //设置访问的标记 { mark[v]=val;} }

③DFS的实现：

void DFS（Graph * G,int v） {

PreVisit(G,v);

G->setMark(v,1);

for(int w=G->first(v);wn();w=G->next(v,w)) if(G->getMark(w)==0) DFS(G,w); PostVisit(G,v); }

算法具体步骤

根据用户的输入，构建一个无向图，并使用一个临接矩阵存储该图。对该图进行深度优先搜索，并通过相应的设置标志的方式使最终能不重复地走遍所有的简单路径。得到所有路径后，输出这些路径即可。

函数调用关系 输入

建图与存图 临接矩阵存储

主程序 DFS搜索

输出

算法时空分析

在表的存储中，临接矩阵的时间代价是Θ（|V2|）,而在无向图中，DFS从两个方向处理每条边，每个顶点都必须被访问，且只能被访问一次，因此时间代价是Θ（|V|+|E|）。所以该算法总时间代价是Θ（|V|2）。

输入输出格式

输入：

cin>>cityNum;

for(int i=0;i

cin>>city[i]; cin>>roadNum;

for(i=0;i

cin>>roadName; }

请输入城市总数： 3

请依次输入城市编号：001 002 003 有几对城市间有高速公路？3

请输入第一对连接城市的高速公路：001 002 请输入第二对连接城市的高速公路：002 003 请输入第三对连接城市的高速公路：001 003 请输入要查询路径的两座城市编号：001 003

输出：

001到003的所有路径如下： 001->003

001->002->003

所有路径已存入文件中。

四． 调试分析

在实际编程中，程序曾陷入过死循环，尝试了一些方法仍然没有解决，

最后使用了goto语句才解决了这个问题

五． 测试结果

六． 用户使用说明

1. 该程序可以通过构建一个有向图来实现查找两城市间的所有简单路径

的功能；

2. 使用该程序时，首先按照要求输入各类参数，若输入有误，系统提示

输入有误，并重新输入；

3. 最后的结果将直接输出在DOS界面。

七． 实验心得

通过该实验，我掌握了图的深度优先搜索的方法

代码： graph.h文件：

#include #include #include

using namespace std; bool visited[100]; int path[100]; class ArcNode {

public: int adjvex; ArcNode *nextarc; };

class VexNode {

public: string data; ArcNode *firstarc; };

class Graph {

private: VexNode vertices[100]; int vexnum; int arcnum; public:

Graph() { vexnum = 0; arcnum = 0; }

~Graph(){ delete[]vertices; } int getArcnum() { return arcnum; }

int GetVexNum() { return vexnum; }

int Position(string v) { for (int i = 0; i

void Build_Graph() { //构造无向图 string v1,v2; int i,j,k; cout << \输入城市个数：\ cin >> vexnum; cout << \请输入高速公路的条数：\ cin>> arcnum; cout << \输入城市名称：\ for (i = 0; i> vertices[i].data; vertices[i].firstarc = NULL; } for (k = 0; k> v1 >> v2; i = Position(v1); j = Position(v2); while (i == -1 || j == -1) { cout << \输入有误，请重新输入：\ cin >> v1 >> v2; i = Position(v1); j = Position(v2);