| 严蔚敏数据结构习题第七章 | 您所在的位置：网站首页 › 数据结构严蔚敏第二版课后答案解析 › 严蔚敏数据结构习题第七章 |
严蔚敏数据结构习题第七章
|
https://www.cnblogs.com/kangjianwei101/p/5244218.html https://wenku.baidu.com/view/a31a5ba1284ac850ad0242d8.html 1
https://blog.csdn.net/weixin_46072771/article/details/106646721 https://blog.csdn.net/weixin_46072771/article/details/106673063
https://blog.csdn.net/weixin_46072771/article/details/106654848 https://blog.csdn.net/weixin_46072771/article/details/106654848 试基于图的深度优先搜索策略写一算法，判别以邻接表方式存储的有向图中是否存在由顶点vi到顶点vj的路径(i≠j)。注意：算法中涉及的图的基本操作必须在此存储结构上实现。 https://www.codeleading.com/article/32714582577/ https://www.shangmayuan.com/a/4a32db9769b94135ad0f76ae.html ZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2hhbjI5Xw==,size_16,color_FFFFFF,t_70) #include #include #define INFINITY INT_MAX //最大值，正无穷 #define MaxVertexNum 20 //最大顶点数 #define DateType int int visted[MaxVertexNum];//辅助数组 //typedef enum{DG,DN,UDG,UDN}GrapKind; //{有向图，有向网，无向图，无向网} typedef struct ArcNode//边表 { int adjvex;//顶点 ArcNode* nextarc;//下一条弧 int info;//权重 }ArcNode; typedef struct VNode { DateType vertex; ArcNode* firstarc; }VNode,AdiList[MaxVertexNum]; typedef struct { AdiList vertices; int vexnum, arcnum; }ALGraph; int existDFS(ALGraph G, int i, int j) { int k; ArcNode* p; if (i == j) return 1; else { //记得提前初始化visted为0 visted[i] = 1; for (p = G.vertices[i].firstarc; p; p = p->nextarc) { k = p->adjvex; if (!visted[k] && existDFS(G, k, j)) return 1; //为什么还要visited，是因为题目要求DFS } } return 0; }。。。 #include #include //图的邻接表存储 #define MAX_VERTEX 20 typedef struct ArcNode { int adjvex;//该弧所指向的顶点的位置 struct ArcNode* nextarc; int* info; //该弧所相关信息的指针 }; typedef struct VNode { int data;//顶点信息 ArcNode* firstarc; }VNode, AdjList[MAX_VERTEX]; typedef struct { AdjList vertices; int vexnum, arcnum;//图的当前顶点数和弧数 int kind;//图的种类标志 }ALGraph; int visited[MAX_VERTEX];//指示顶点是否在当前道路上 int level = 1;//递归进行的层数 int exist_path_DFS(ALGraph G, int i, int j) { int k; ArcNode* p; if (i == j)//相同返回真 return 1; //不同就标记visited[i] else { visited[i] = 1; for (p = G.vertices[i].firstarc; p != NULL; p = p->nextarc, level--;) { level++; k = p->adjvex; if (!visited[k] && exist_path_DFS(G, k, j)) return 1; } } if (level == 1) return 0; } 23 BFS 深度同7.22题要求。试基于图的广度优先搜索策略写一算法。 #include #include #define INFINITY INT_MAX //最大值，正无穷 #define MaxVertexNum 20 //最大顶点数 #define DateType int int visited[MaxVertexNum];//辅助数组 //typedef enum{DG,DN,UDG,UDN}GrapKind; //{有向图，有向网，无向图，无向网} typedef struct ArcNode//边表 { int adjvex;//顶点 ArcNode* nextarc;//下一条弧 ArcNode* info;//该弧 }ArcNode; typedef struct VNode { DateType vertex; ArcNode* firstarc; }VNode,AdiList[MaxVertexNum]; typedef struct { AdiList vertices; int vexnum, arcnum; }ALGraph; //队列结点的结构 typedef struct Qnode { int data; struct Qnode* next; }Qnode,*QuequePrt; //链表队列结构 typedef struct { QuequePrt front;//队头指针 QuequePrt rear; }LinkQueue; //初始化队列 void InitQueue(LinkQueue& Q) { Q.front = Q.rear = new Qnode;//生成新的结点作为头结点，初始化队头队尾指针 Q.front->next = NULL;//头结点的指针域为空 } bool EnQueue(LinkQueue& Q, int e) { Qnode* p = new Qnode; p->data = e; Q.rear->next = p; Q.rear = p; return 1; } bool DeQueue(LinkQueue& Q, int & e) { Qnode* p = new Qnode;//保存头结点指针，用于释放空间 p = Q.front->next;//指向队头结点 e = p->data;//获取队头结点的元素的值 Q.front->next = p->next;//修改头指针 if (Q.rear == p)//判断删除的元素是否为最后一个元素，避免空指针异常，将队尾指针重新指向队头指针 Q.rear = Q.front; Q.rear->next = Q.front->next;//最后一个结点指向首元结点 delete p; return 1; } void DeleteQueue(LinkQueue& Q) { while (Q.front) { Q.rear = Q.front->next; delete Q.front; Q.front = Q.rear; } } //广度遍历函数 int BFS(ALGraph G, int i,int j) { LinkQueue Q; InitQueue(Q); visited[i] = 1; EnQueue(Q, i); while (Q.front != Q.rear) { int u; DeQueue(Q, u); ArcNode* p = G.vertices[u].firstarc;//获取被访问顶点的边链表的首元结点的指针 while (p) { int w = p->adjvex;//获取v顶点的邻接顶点 if (w == j) return 1; else if (!visited[w])//判断该顶点是否被访问过 { visited[w] = 1; EnQueue(Q, w); } p = p->nextarc;//指向顶点的下一个邻接点 } } return 0; } //操作函数 void BFS_Traverse(ALGraph G) { //访问标志辅助数组初始化 for (int i = 0; i ArcNode *p; Queue Q; int e,k; InitQueue(Q); EnQueue(Q,i); while(!QueueEmpty(Q)){ DeQueue(Q,e); visited[e] = TRUE;//标记被访问过的顶点 p = g.vertices[e].firstarc; for(; p != NULL; p = p -> nextarc){ k = p -> adjvex;//当前弧所指向顶点的位置 if(k == j) return OK; else if(!visited[k])//当前顶点未被访问过 EnQueue(Q,k); } } return ERROR; } 27 邻接表https://www.freesion.com/article/64991243006/ 采用邻接表存储结构，编写一个判别无向图中任意给定的两个顶点之间是否存在一条长度为k的简单路径的算法（一条路径为简单路径指的是其顶点序列中不含有重现的顶点)。 #include #include #define INFINITY INT_MAX //最大值，正无穷 #define MaxVertexNum 20 //最大顶点数 #define DateType int int visited[MaxVertexNum];//辅助数组 //typedef enum{DG,DN,UDG,UDN}GrapKind; //{有向图，有向网，无向图，无向网} typedef struct ArcNode//边表 { int adjvex;//顶点 ArcNode* nextarc;//下一条弧 ArcNode* info;//该弧 }ArcNode; typedef struct VNode { DateType vertex; ArcNode* firstarc; }VNode,AdiList[MaxVertexNum]; typedef struct { AdiList vertices; int vexnum, arcnum; }ALGraph; int exist_path_len(ALGraph G, int i, int j, int k) //判断邻接表方式存储的有向图G的顶点i到j是否存在长度为k的简单路径 { ArcNode *p; int m; if (i == j && k == 0) return 1; //找到了一条路径,且长度符合要求 else if (k > 0) { visited[i] = 1; for (p = G.vertices[i].firstarc; p != NULL; p = p->nextarc) { m = p->adjvex; if (!visited[m]) if (exist_path_len(G, m, j, k - 1)) return 1; //剩余路径长度减一 }//for visited[i] = 0; //本题允许曾经被访问过的结点出现在另一条路径中 //这里需要把已经访问的点重新置为0，因为如果当前不存在长度为k //到达j点，那么这个点还是可以使用的，因为有可能从其他点出发 //可以到达j点并且长度为k }//else return 0; //没找到 }//exist_path_len void judge(ALGraph G) { int i, j, k; //访问标志辅助数组初始化 for (int i = 0; i int adjvex;//顶点 ArcNode* nextarc;//下一条弧 int info;//该弧的权重 }ArcNode; typedef struct VNode { DateType vertex; ArcNode* firstarc; }VNode,AdiList[MaxVertexNum]; typedef struct { AdiList vertices; int vexnum, arcnum; }ALGraph; //栈的顺序存储表示 typedef struct { SElemType* base;//在栈构造之前和销毁之后，base的值为NULL SElemType* top;//栈顶指针 int stacksize;//当前已分配的存储空间，以元素为单位 }SqStack; void InitStack_Sq(SqStack& s) { s.base = (SElemType*)malloc( STACK_SIZE* sizeof(SElemType)); } void Push_Sq(SqStack& s, SElemType e) { } void Pop_Sq(SqStack& s, SElemType& e) { } int StackEmpty_Sq(SqStack& S) { } void FindInDegree(ALGraph G, int indegree[]) //写数组，传的是首地址，所以也不用写[] { int i, m; ArcNode* p; for (i = 1; i indegree[m]++; p = p->nextarc; } } } int T_34(ALGraph G, int T[])//数组Topo存储拓扑序列 { int n = G.vexnum; SqStack S; ArcNode* p; int i, k, count, indegree[MaxVertexNum]; FindInDegree(G, indegree); InitStack_Sq(S); for (i = 0; i Pop_Sq(S, i); T[count] = i; i++; for (p = G.vertices[i].firstarc; p; p = p->nextarc) { k = p->adjvex; if (!(--indegree[k]))//对i号顶点的每个邻接点的入度减一 Push_Sq(S, k); } } if (count DateType vertex; ArcNode* firstarc; }VNode,AdiList[MaxVertexNum]; typedef struct { AdiList vertices; int vexnum, arcnum; }ALGraph; int findMinDist(int dist[], int s[], int n) { int min, k=0; for (int i = 0; i if (k == 0) min = dist[i]; else { min = (min > dist[i]) ? dist[i] : min; } k++; } } return k; } void ShortestPath(ALGraph G, int v0) { int n = G.vexnum;//顶点个数 int dist[MaxVertexNum], path[MaxVertexNum], s[MaxVertexNum]; //初始化上面数组 for (int i = 0; i int v = p->adjvex;//顶点 int w = p->info;//权值 path[v] = v0; dist[v] = w; } int num = 1; int min, m, k; while (num int v = p->adjvex;//顶点 int w = p->info;//权值 int sum = dist[v] + p->info; if ((s[v] == 0) && (dist[v] > sum)) { dist[v] = sum;//用已经找到的最短路径修改对应的dist path[v] = min;//用已经找到的最短路径修改对应的path } } num++; } } |
什么是连通图，（强）连通图详解：http://c.biancheng.net/view/3405.html https://blog.csdn.net/weixin_43843835/article/details/88381828 课本p161 
普利姆p173 顶点–找最小边的点–把顶点加入 克鲁斯卡尔p175 https://blog.csdn.net/a2392008643/article/details/81781766
【本文地址】
公司简介
联系我们
| 今日新闻 |
| 推荐新闻 |
| 专题文章 |