景区旅游信息管理系统(2)

}

pGraph->Arcs[i][j]=INF;

//输入弧的信息

printf(\

printf(\初始化的弧的信息......\\n\

printf(\请输入弧的信息(注：从0开始)：\\n\for(i=0;iArcNum;i++) {

int Stav,Endv,Weight;

printf(\请输入第%d条弧(格式：Vi Vj Weight)：\scanf(\pGraph->Arcs[Endv][Stav]=Weight; pGraph->Arcs[Stav][Endv]=Weight; }

printf(\创建景区景点分布图成功！！！\\n\printf(\按任意键回主菜单！！！\getch();

return SUCCESS;

输出景区景点分布图

流程图：

景区景点名称i=0iVexNumprintf(\t\>Vexs[i]);i++景区景点信息i=0iVexNum终止j=0i++jVexNumif(pGraph->Arcs[i][j]==INF)printf(\t\>Arcs[i][j]);j++printf(\∞\\t\ 程序：

//输出景区景点分布图

STATUS PrintGraph(const PGRAPH pGraph) { printf(\

printf(\显示景区景点分布图\\t$\\n\

printf(\//

printf(\景区景点名称......\\n\\t\for(int i=0;iVexNum;i++) printf(\printf(\景区景点信息......\\n\

}

for(i=0;iVexNum;i++) {

printf(\for(int j=0;jVexNum;j++) if(pGraph->Arcs[i][j]==INF) printf(\∞\\t\ else

printf(\printf(\}

printf(\printf(\按任意键回主菜单！！！\getch();

return SUCCESS;

输出景区导游线路图

图的遍历

从图中某一顶点出发访遍图中所有的顶点，且使每个顶点仅被访问一次，这一过程就叫做图的遍历 (Traversing Graph)。 图中可能存在回路，且图的任一顶点都可能与其它顶点相通，在访问完某个顶点之后可能会沿着某些边又回到了曾经访问过的顶点。

为了避免重复访问，可设置一个标志顶点是否被访问过的辅助数组 visited [ ]。

辅助数组 visited [ ] 的初始状态为 0, 在图的遍历过程中, 一旦某一个顶点 i 被访问, 就立即让 visited [i] 为 1, 防止它被多次访问。 两种图的遍历方法: 深度优先搜索

DFS (Depth First Search) 广度优先搜索

BFS (Breadth First Search)

广度优先搜索遍历图(BFS)

对连通图，从起始点V到其余各顶点必定存在路径。 其中，V->w1, V->w2, V->w8 的路径长度为1; V->w7, V->w3, V->w5 的路径长度为2; V->w6, V->w4 的路径长度为3

从图中的某个顶点V0出发，并在访问此顶点之后依次访问V0的所有未被访问过的邻接点，之后按这些顶点被访问的先后次序依次访问它们的邻接点，直至图中所有和V0有路径相通的顶点都被访问到。

若此时图中尚有顶点未被访问,则另选图中一个未曾被访问的顶点作起始点，重复上述过程，直至图中所有顶点都被访问到为止。 流程图：

定义访问标志数组初始化访问标志数组为false定义队列、并初始化队列if(InitQueue(&Queue,pGraph->VexNum)==FAILURE)否出队DeQueue(&Queue,&Vertex);while(QueueLen(&Queue));if(!Visit[Vertex])printf(\景点......\\n\>Vexs[Vertex]);标志访问过Visit[Vertex]=true;i=0iVexNum是if(Visit[i]==false&&pGraph->Arcs[Vertex][i]!=INF)是否i++EnQueue(&Queue,i);终止程序：

//输出景区导游线路图(注：广度优先遍历) STATUS TraverseGraph(const PGRAPH pGraph) { printf(\ printf(\输出景区导游线路图\\t$\\n\ printf(\ //定义访问标志数组 bool* Visit=(bool*)malloc(pGraph->VexNum*sizeof(bool)); //初始化访问标志数组为false for(int i=0;iVexNum;i++)