《数据结构习题集（李冬梅 第2版）C语言版源程序习题源代码习题集-算法6-2.docx》由会员分享，可在线阅读，更多相关《数据结构习题集（李冬梅 第2版）C语言版源程序习题源代码习题集-算法6-2.docx（2页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、/邻接表存储图#include using namespace std;/定义最大顶点数 #define MVNum 128 /定义状态类型 #define Status int /函数结果状态代码 #define OK 1 #define ERROR 0 #define INFEASIBLE 0 #define EXISTED 2typedef struct ArcNode /定义边结点int adjvex; struct ArcNode *nextarc;ArcNode;typedef struct VexNode /定义顶点结点int data;struct ArcNode *first
2、arc; VexNode;typedef struct ALGraph /定义图的结构体类型VexNode verticesMVNum + 1;int vexnum, arcnum; /图当前的顶点数和边数 ALGraph;bool visitedMVNum = 0 ;/定义顺序栈的结构类型typedef struct SqStack int top;int vexticsMVNum + 1;SqStack;/栈初始化函数void InitStack(SqStack &s) s.top = -1;/元素入栈Status Push(SqStack &s, int v) if (s. top =
3、MVNum) return ERROR;/栈已满，无法放入s.vextics+s.top = v;return OK;)/元素出栈Status Pop(SqStack &s, int &k) if (s. top = -1) return ERROR; /z 栈已空 k = s.vexticss.top-;return OK;)/判断栈是否为空bool StackEmpty(SqStack s) return s.top = -1; )/对于每个顶点，它的边采用头插法插入void insertArcNode (VexNode & vnode z int adj vex) /向邻接表顶点中插入一
4、条边结点ArcNode *arcnode = new ArcNode;arcnode-adjvex = adjvex;arcnode-nextarc = vnode.firstarc;vnode.firstarc = arcnode;/采用邻接矩阵表示法，创立无向图graphStatus createUDN(ALGraph &graph, int vexnum, int arcnum) graph, vexnum = vexnum;/初始化图的总顶点数graph. arcnum = arcnum;/初始化图的总边数for (int i = 0; i = graph.vexnum; i+) /初
5、始图中的顶点信息graph.verticesi.data = i;graph.verticesi.firstarc = NULL;)int vex_one, vex_two;/一条边依附的两个顶点 vex_one 和 vex_twofor (int i = 0; i vex_one vex_two;insertArcNode(graph.verticesvex_one, vex_two); insertArcNode(graph.verticesvex_two, vex_one); return OK; /创立成功，返回成功代码/定义打印无向图函数void printUDN(ALGraph g
6、raph) for (int i = 1; i = graph. vexnum; i+) /输出边的信息(每行第一个数字为顶点)(注意0号顶点不输出)cout graph.verticesi.data nextarc) /开始输出每个顶点上所链接的边信息cout adjvex ” n;) cout endl;)/输出结束)/构造一个空栈/顶点v进栈/栈非空/栈顶元素k出栈/访问第k个顶点/P指向k的边链表的第一个边结点/表示w是k的邻接点/如果w未访问，w进栈/P指向下一个边结点/从第v个顶点出发非递归实现深度优先遍历图G void DFS(ALGraph G, int v) SqStack
7、S;InitStack(S);Push(S, v);while (!StackEmpty(S) int k;Pop (Sz k);if (!visitedk) cout adjvex;if (!visitedw) Push(Sz w); p = p-nextarc;/end if/end while cout n m; /输入n和m的值ALGraph G;cout请依次输入m条边所依附的两端顶点：n”；createUDN(Gz n, m);/连通图构建完毕并打印图的信息 printUDN(G);cout ”请输入深度遍历开始顶点编号：b” endl; int v;cin v;DFS(Gz v);system(pause);return 0;/程序运行结束测试用例展示(以程序一次运行周期为例) 输入数据： 4 3 1 22 31 4 输出结果： 14 2 2 3 1 3 2 4 1输入数据：1输出结果：1234