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

1、/邻接矩阵存储无向图 include 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 ; /顶点集因为顶

2、点存储序号范围为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;)

3、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(

4、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; /顶点数超过最大

5、允许范围，返回错误代码。(注意数组下标从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 vex_one vex_two;graph.ar

6、cs 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+) /输出边的信息(每行第一个数字为顶点)(注意

7、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)

8、 DeQueue(Q, v);int degree = 0; /记录当前顶点的度数for (int w = 0; w 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 (oddCount2)return 0

9、; /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