《数据结构习题集（李冬梅 第2版）C语言版源程序习题源代码习题集-算法6-4.docx》由会员分享，可在线阅读，更多相关《数据结构习题集（李冬梅 第2版）C语言版源程序习题源代码习题集-算法6-4.docx（2页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、邻接表存储有向图 include using namespace std;定义最大顶点数define MVNum 128定义状态类型#define Status int函数结果状态代码#define OK 1Idefine ERROR 0 fdefine INFEASIBLE 0 #define EXISTED 2typedef struct ArcNode /定义边结点int adjvex;struct ArcNode *nextarc; )ArcNode;typedef struct VexNode (/定义顶点结点int data;struct ArcNode *firstarc; Ve
2、xNode;typedef struct ALGraph (定义图的结构体类型VexNode verticesMVNum + 1;int vexnum, arcnum; /图当前的顶点数和边数 )ALGraph;int visitedMVNum = ( 0 );访问标志数组，其初值为falseint level = 1;/递归进行的层数对于每个顶点，它的边采用头插法插入void insertArcNode (VexNode &vnodez int adj vex) 向邻接表顶点中插入一条边结点ArcNode *arcnode = new ArcNode;arcnode-adjvex = adj
3、vex;arcnode-nextarc = vnode.firstarc; vnode.firstarc = arcnode;)采用邻接矩阵表示法，创立无向图graphStatus createGraph(ALGraph &graphz int vexnum, int arcnum) graph.vexnum - vexnum;/初始化图的总顶点数graph, arcnum = arcnum;/初始化图的总边数for (int i = 0; i = graph.vexnum; i+) /初始图中的顶点信息graph.verticesi.data = i;graph.verticesi.firs
4、tarc = NULL; int vex one, vex two; 一条边依附的两个顶点 vex_one 和 vex_two for (int i = 0; i graph. arcnum; i + + ) 循环输入 arcnum 条边的信息 cin vexone vex_two; insertArcNode(graph.verticesvex_one, vex_two);) return OK; /创立成功，返回成功代码)定义打印邮箱向图函数void printGraph(ALGraph graph) for (int i - 1; i - graph.vexnum; i+) /输出边的信
5、息(每行第一个数字为顶点)(注意。号顶点不输出)cout graph.verticesi.data nextarc) 开始输出每个顶点上所链接的边信息cout p-adjvex ) cout endl;输出结束基于深度优先搜索判断有向图G中顶点i到顶点j是否有路径，是那么返回1,否那么返回0 int PathDFS(ALGraph G, int i, int j) if (i = j) return 1;/递归结束的条件,首尾相遇,存在路径else visitedi = true;顶点 i 访问标志为 truefor (ArcNode *p = G.verticesi.firstarc; p;
6、 p = p-nextarc, level-)( level+;递归层次加1int k = p-adjvex; if (!visitedk & PathDFS(G, k, j) return 1;/i下游的顶点到j有路径)/end for /end else return 0;i到j没有路径int main() int n, m;/n个顶点和m条边cout请输入顶点的数量n和边的数量m (空格分隔，下同)：b;cin n m;输入n和m的值ALGraph G;cout请依次输入m条边所依附的起点和终点：n;createGraph(Gz n, m);打印图的信息printGraph(G);cout ”请输入需遍历路径的起点和终点：b“；int start, destination;cin start destination;int result = PathDFS(Gz start, destination);if (result)cout 有路径 endl;elsecout 没有路径 endl;system(pause);return 0;)测试用例展示（以程序一次运行周期为例） 输入数据：4 321 34输出结果：1 4 232输入数据：13/24输出结果：有路径/无路径