数据结构习题集（李冬梅 第2版）C语言版源程序习题源代码习题集-算法6-6.docx

/邻接矩阵存储无向图 include <iostream> using namespace std;/定义最大顶点数 define MVNum 128 /定义状态类型#define Status int /函数结果状态代码#define#define#define#define#define#define#define#define#define#define#define#defineOK 1ERROR 0INFEASIBLE 0EXISTED 2 VerTexType int ArcType int/定义图的结构体类型 typedef struct VerTexType vexs MVNum ; /顶点集因为顶点存储序号范围为lMVNumArcType arcs MVNum MVNum ;/邻接矩阵int vexnum, arcnum; /图当前的顶点数和边数 AMGraph;/定义队列的结构体类型typedef struct int head, tail;int sign;/sign标签用于区分当head与tail相等时，是队空状态还是队满状态int dateMVNum; Queue;int oddCount = 0;/度为奇数的顶点个数int visitedMVNum = 0 ;void InitQueue(Queue &q) q.head = q.tail = 1; q.sign = 0;) bool isFull(Queue q) if (q.head = q.tail && q,sign) return true;else return false;)bool isEmpty(Queue q) if (q.head = q.tail && !q.sign)return true; elsereturn false;Status EnQueue(Queue &q, int v) if (isFull(q)return ERROR; q.dateq.tail = v;q.tail = q.tail+%MVNum;q.sign = 1;return OK;)Status DeQueue(Queue &q, int &v) if (isEmpty(q)return ERROR; v = q.dateq.head;q.head = q.head+%MVNum; q.sign = 0;return OK;)/采用邻接矩阵表示法，创立无向图graphStatus createUDN(AMGraph &graph, int vexnum, int arcnum) graph. vexnum = vexnum;/初始化图的总顶点数graph. arcnum = arcnum;/初始化图的总边数if (graph.vexnum >= MVNum) return ERROR; /顶点数超过最大允许范围，返回错误代码。(注意数组下标从0开始) for (int i = 0; i < graph.vexnum; i + + ) /依次输入顶点信息 graph.vexsi = i;)for (int i = 0; i < graph.vexnum; i + + ) /初始化所有边的权值为0,表示边不存在for (int j = 0; j < graph.vexnum; j+) graph.arcsij = 0;) ) int vex_onez vex_two;/一条边依附的两个顶点 vex_one 和 vex_twofor (int i = 0; i < graph.arcnum; i+) /循环输入 arcnum 条边的信息 cin >> vex_one >> vex_two;graph.arcs vex_one - 1 vex_two - 1 = 1;/表权值为 1,表示边存在graph.arcsvex_two - 1vex_one - 1 = 1; " return OK; /创立成功，返回成功代码。 )/定义打印无向图函数void printUDN(AMGraph graph) cout << 0 << ” n;for (int i = 0; i < graph.vexnum; i+) /在第一行打印顶点信息 cout << graph.vexsi + 1 << n n;)cout << endl;for (int i = 0; i < graph.vexnum; i+) /输出边的信息(每行第一个数字为顶点)(注意0号顶点不输出) cout « graph.vexs i + 1 « " H;/输出该行对应的顶点for (int j = 0; j < graph.vexnum; j+) /输出该行顶点对应所有边信息 cout << graph.arcsij << " n;) cout << endl;)/输出结束)/从顶点v出发，广度优先遍历图G,判断G是否存在EL路径/访问顶点v/顶点v入队/队头元素出队/访问顶点v/顶点v入队/队头元素出队int IsExistEL(AMGraph G, int v) visitedv = true;Queue Q;InitQueue(Q);EnQueue(Q, v);while (!isEmpty(Q) DeQueue(Q, v);int degree = 0; /记录当前顶点的度数for (int w = 0; w < G.vexnum; w+) /访问顶点v的所有邻接顶点if (G.arcsvw > 0) degree+;if (!visitedw) visitedw = true; EnQueue(Q, w);/存在顶点v到顶点w的边/顶点v的度数加1/w是V尚未访问的邻接顶点/访问顶点W/顶点W入队/end if /end forif (degree % 2 = 1) /顶点v的度数为奇数oddCount+；/度数为奇数的顶点数+1/度数为奇数的顶点数超过2个，一定不存在EL路径/度数为奇数的顶点数超过2个，一定不存在EL路径if (oddCount>2)return 0; /end if/end whileif (oddCount % 2 = 0) return 1;/度数为奇数的顶点数是偶数，存在EL路径else return 0;)int main() int n, m;/n个顶点和m条边cout ”请输入顶点的数量n和边的数量m (空格分隔，下同)：cin >> n » m; /输入n和m的值 AMGraph G;cout « ”请依次输入m条边所依附的起点和终点：n”； createUDN(Gz n, m);/打印图的信息 printUDN(G); cout « ”请输入出发顶点：bH; int v;cin >> v;int result = IsExistEL(G, v); if (result) cout << ”存在 EL 路径” << endl; else cout << "不存在 EL 路径” << endl; )system("pause"); return 0;)测试用例展示(以程序一次运行周期为例) 输入数据： 4 3 1 2 2 3 1 4输出结果： 0 12 3 4 10 10 1 2 10 10 3 0 10 04 10 0 0输入数据： 1输出结果：存在EL路径测试用例展示（以程序一次运行周期为例） 输入数据：5 421 31 41 5输出结果：0 1 2 3 4 510 10 112 10100010003 1000010000输入数据：输出结果：不存在EL路径