内容发布更新时间 : 2024/12/22 23:37:15星期一 下面是文章的全部内容请认真阅读。
图的邻接表以及相关类型、函数和辅助变量定义如下： Status visited[MAX_VERTEX_NUM];
typedef char StrARR[100][MAX_VERTEX_NUM+1]; typedef char VertexType; typedef struct ArcNode { int adjvex;
struct ArcNode *nextarc; } ArcNode;
typedef struct VNode { VertexType data; ArcNode *firstarc;
} VNode, AdjList[MAX_VERTEX_NUM];
typedef struct {
AdjList vertices; int vexnum, arcnum; } ALGraph;
int LocateVex(Graph g, VertexType v); void inpath(char *path, VertexType v); /* Add vertex 'v' to 'path' */
void depath(char *path, VertexType v); /* Remove vertex 'v' from 'path' */
void AllPath2(ALGraph g, VertexType sv, VertexType tv,
StrARR &path, int &i,int &d,VertexType A[]) { int j,k,l,m,n;
ArcNode *p;
j=LocateVex(g,sv); visited[j]=1; A[d++]=sv;
if(sv==tv) { m=0;
for(n=0;n for(p=g.vertices[j].firstarc;p;p=p->nextarc) { l=p->adjvex; if(!visited[l]) AllPath2(g,g.vertices[l].data,tv,path,i,d,A); } visited[j]=0; d--; } void AllPath(ALGraph g, VertexType sv, VertexType tv, StrARR &path, int &i) /* Get all the paths from vertex sv to tv, save them */ /* into Array path which contains string components. */ /* Return the number of path using i */ { int d=0,j,l; VertexType A[MAX_VERTEX_NUM],B[MAX_VERTEX_NUM]; for(l=0;l<5;l++) { strcpy(B,path[l]); for(j=0;j AllPath2(g,sv,tv,path,i,d,A); } 7.31③ 试完成求有向图的强连通分量的算法，并分析算法的时间复杂度。 实现下列函数： void StronglyConnected(OLGraph dig, StrARR &scc, int &n); /* Get all the strongly connected components in the digraph dig, */ /* and put the ith into scc[i] which is a string. */ 图的十字链表以及相关类型和辅助变量定义如下： Status visited[MAX_VERTEX_NUM]; int finished[MAX_VERTEX_NUM]; typedef char StrARR[MAX_VERTEX_NUM][MAX_VERTEX_NUM+1]; // 记录各强连通分量 typedef struct ArcBox { int tailvex,headvex; struct ArcBox *hlink,*tlink; } ArcBox; typedef struct VexNode { VertexType data; ArcBox *firstin,*firstout; } VexNode; typedef struct { VexNode xlist[MAX_VERTEX_NUM]; int vexnum, arcnum; } OLGraph; int count; void DFS1(OLGraph dig,int v); void DFS2(OLGraph dig,int v,StrARR &scc,int j,int k); void StronglyConnected(OLGraph dig, StrARR &scc, int &n) /* Get all the strongly connected components in the digraph dig, */ /* and put the ith into scc[i] which is a string. */ { int i,k=0,v; count=0; for(v=0;v for(v=0;v for(i=dig.vexnum-1;i>=0;i--) { v=finished[i]; if(!visited[v]) { DFS2(dig,v,scc,n,k); n++; } } } void DFS1(OLGraph dig,int v) { int w; ArcBox *p; visited[v]=1; for(p=dig.xlist[v].firstout;p;p=p->tlink) { w=p->headvex; if(!visited[w]) DFS1(dig,w); } finished[count++]=v; } void DFS2(OLGraph dig,int v,StrARR &scc,int j,int k) { int w; ArcBox *p; visited[v]=1; scc[j][k++]=dig.xlist[v].data; for(p=dig.xlist[v].firstin;p;p=p->hlink) { w=p->tailvex; if(!visited[w]) DFS2(dig,w,scc,j,k); } } 7.29⑤ 试写一个算法，在以邻接矩阵方式存储的 有向图G中求顶点i到顶点j的不含回路的、长度为k 的路径数。 实现下列函数： int SimplePath(MGraph G, int i, int j, int k); /* 求有向图G的顶点i到j之间长度为k的简单路径条数 */ 图的邻接矩阵存储结构的类型定义如下： typedef enum {DG,DN,AG,AN} GraphKind; // 有向图,有向网,无向图,无向网 typedef struct { VRType adj; // 顶点关系类型。对无权图，用1(是)或0(否)表示相邻否； // 对带权图，则为权值类型 InfoType *info; // 该弧相关信息的指针(可无) }ArcCell,AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM]; typedef struct { AdjMatrix arcs; // 邻接矩阵 VertexType vexs[MAX_VERTEX_NUM]; // 顶点向量 int vexnum,arcnum; // 图的当前顶点数和弧数 GraphKind kind; // 图的种类标志 }MGraph; int SimplePath(MGraph G, int i, int j, int k) /* 求有向图G的顶点i到j之间长度为k的简单路径条数 */ { int sum=0,v; if( G.arcs[i][j].adj &&k==1 && !visited[j]) sum=1; else if(k>1) { visited[i]=1; for(v=0;v if(G.arcs[i][v].adj && !visited[v]) sum+=SimplePath(G,v,j,k-1); } visited[i]=0; } return sum; } 实现下列函数： int Search(SSTable s, KeyType k); /* Index the element which key is k */ /* in StaticSearchTable s. */ /* Return 0 if x is not found. */ 静态查找表的类型SSTable定义如下： typedef struct { KeyType key; ... ... // 其他数据域 } ElemType; typedef struct { ElemType *elem; int length; } SSTable; int Search(SSTable a, KeyType k) /* Index the element which key is k */ /* in StaticSearchTable s. */ /* Return 0 if x is not found. */ { int i; for(i=1;i<=a.length;i++) if(a.elem[i].key==k)return i; return 0; }