《数据结构》第七章 图

7.1 已知如右图所示的有向图,请给出该图的
(1)每个顶点的入/出度;
(2)邻接矩阵;
(3)邻接表;
(4)逆邻接表;
(5)强连通分量。

 

7.2 已知有向图的邻接矩阵为AnXn,试问每一个A_{nXn}^{k}(k=1,2,…,n)各具有何种实际含义?

a_{ij}^{k}=A_{nXn}^{k},则a_{ij}^{k}为由i到j的长度为k的路径数。

7.3 画出左图所示的无向图的邻接多重表,使得其中的每个无向边结点中第一个顶点号小于第二个顶点号,且每个顶点的各邻接边的链接顺序,为它所邻接到的顶点序号由小到大的顺序。列出深度优先和广度优先搜索遍历该图所得顶点序列和边的序列。
 

 

7.4 试对教科书7.1节中图7.3(a)所示的无向图,画出其广度优先生成森林。

 

 

7.6 试证明教科书7.4.2节中求强连通分量的算法的正确性。

7.7 请对下页图7.7图的无向带权图,
(1)写出它的邻接矩阵,并按普里姆算法求其最小生成树。
(2)写出它的邻接表,并按克鲁斯卡尔算法求其最小生成树。
 

 

7.8 试对教科书7.3节中图7.13(a)所示无向图执行求关节点的算法,分别求出每个顶点的visited[i]和low[i]值,i=1,2,…,vexnum。

7.9 试列出题7.9图中全部可能的拓扑有序序列,并指出应用7.5.1节中算法Topological Sort求得的是哪一个序列(注意:应先确定其存储结构)。

 

7.11 试利用Dijkstra算法求题7.11图中从顶点a到其他各顶点间的最短路径,写出执行算法过程中各步的状态。

7.12 试证明求最短路径的Dijkstra算法的正确性。

7.13 试利用Floyd算法求题7.13图所示有向图中各对顶点之间的最短路径。

7.14 编写算法,由依次输入的顶点数目、弧的数目、各顶点的信息和各条弧的信息建立有向图的邻接表。

Status Build_AdjList(ALGraph &G){
	//输入有向图的顶点数,边数,顶点信息和边的信息尽力邻接表
	InitALGraph(G);
	cin>>v;
	if(v<0)
		return ERROR;
	G.vexnum=v;
	cin>>a;
	if(a<0)
		return ERROR;
	G.arcnum=a;
	for(m=0;m<v;m++){
		G.vertices[m].data=getchar();
	}
	for(m=1;m<=a;m++){
		t=getchar();
		h=getchar();
		if((i=LocateVex(G,t))<0)
			return ERROR;
		if((j=LocateVex(G,h))<0)
			return ERROR;
		if(!G.vertices[i].firstarc)
			G.vertices[i].firstarc=p;
		else{
			for(q=G.vertices[i].firstarc;q->nextarc;q=q->nextarc);
			q->nextarc=p;
		}
		p->adjvex=j;
		p->nextarc=NULL;
	}
	return OK;
}

7.15 试在邻接矩阵存储结构上实现图的基本操作:InsertVex(G,v),InsertArc(G,v,w),DeleteVex(G,v)和DeleteArc(G,v,w)。

Status Insert_Vex(MGraph &G,char v){
	//邻接矩阵表示的图G中插入v
	if((G.vexnum+1)>MAX_VERTEX_NUM)
		return INFEASIBLE;
	G.vexx[++G.vexnum]=v;
	return OK;
}
Status Insert_Arc(MGraph &G,char v,char w){
	//邻接矩阵表示的图G中插入边(v,w)
	if((i=LocateVex(G,v))<0)
		return ERROR;
	if((j=LocateVex(G,w))<0)
		return ERROR;
	if(i==j)
		return ERROR;
	if(!G.arcs[i][j].adj){
		G.arcs[i][j].adj=1;
		G.arcnum++;
	}
	return OK;
}
Status Delete_Vex(MGraph &G,char v){
	//邻接矩阵表示的图G中删除顶点v
	n=G.vexnum;
	if((m=LocateVex(G,v))<0)
		return ERROR;
	G.vexs[m]<>G.vexs[n];//将待删除顶点交换到最后一个顶点
	for(i=0;i<n;i++){
		G.arcs[i][m]=G.arcs[i][n];
		G.arcs[m][i]=G.arcs[n][i];
	}
	G.arcs[m][m].adj=0;
	G.vexnum--;
	return OK;
}
Status Delete_Arc(MGraph &G,char v,char w){
	//邻接矩阵表示的图G上删除边(v,w)
	if((i=LocateVex(G,v))<0)
		return ERROR;
	if((j=LocateVex(G,w))<0)
		return ERROR;
	if(G.arcs[i][j].adj){
		G.arcs[i][j].adj=0;
		G.arcnum--;
	}
	return OK;
}

7.16 试对邻接表存储结构重做7.15题。

7.17 试对十字链表存储结构重做7.15题。

7.18 试对邻接多重表存储结构重做7.15题。

7.19 编写算法,由依次输入的顶点数目、边的数目、各顶点的信息和各条边的信息建立无向图的邻接多重表。

Status Build_AjdMulist(AMLGraph &G){
	//输入有向图的顶点数,边数,顶点信息和边的信息建立邻接多重表
	InitAMLGraph(G);
	cin>>v;
	if(v<0)
		return ERROR;
	G.vexnum=v;
	cin>>a;
	if(a<0)
		return ERROR;
	G.arcnum=a;
	for(m=0;m<v;m++)
		G.adjmulist[m].data=getchar();
	for(m=1;m<a;m++){
		t=getchar();
		h=getchar();
		if((i=LocateVex(G,t))<0)
			return ERROR;
		if((j=LocateVex(G,h))<0)
			return ERROR;
		p=(EBox*)malloc(sizeof(EBox));
		p->ivex=i;
		p->jvex=j;
		p->ilink=NULL;
		p->jlink=NULL;
		if(!G.adjmulist[i].firstedge)
			G.adjmulist[i].firstedge=p;
		else{
			q=G.adjmulist[i].firstedge;
			while(q){
				r=q;
				if(q->ivex==i)
					q=q->ilink;
				else
					q=q->jlink;
			}
			if(r->ivex==i)
				r->ilink=p;
			else
				r->jlink=p;
		}
		if(!G.adjmulist[j].firstedge)
			G.adjmulist[j].firstedge=p;
		else{
			q=G.adjmulist[i].firstedge;
			while(q){
				r=q;
				if(q->jvex==j)
					q=q->jlink;
				else
					q=q->ilink;
			}
			if(r->jvex==j)
				r->jlink=p;
			else 
				r->ilink=p;
		}

	}
	return OK;
}

 

int Pass_MGraph(MGraph G){
	//判断邻接矩阵存储的有向图是否可传递
	for(x=0;x<G.vexnum;x++)
		for(y=0;y<G.vexnum;y++)
			if(G.arcs[x][y]){
				for(z=0;z<G.vexnum;z++)
					if(z!=x && G.arcs[y][z] && !G.arcs[x][z])
						return 0;
			}
	return 1;
}

7.21 试对邻接表存储结构重做7.20题。

int Pass_ALGraph(ALGraph G){
	//邻接表存储的有向图是否可传递
	for(x=0;x<G.vexnum;x++)
		for(p=G.vertices[x].firstarc;p;p=p->nextarc){
			y=p->adjvex;
			for(q=G.vertices[y].firstarc;q;q=q->nextarc){
				z=q->adjvex;
				if(z!=x && !is_adj(G,x,z))
					return 0
			}
		}
}
int is_adj(ALGraph G,int m,int n){
	//判断有向图G中是否存在边(m,n)
	for(p=G.vertices[m].firstarc;p;p=p->nextarc)
		if(p->adjvex==n)
			return 1;
	return 0;
}

7.22 试基于图的深度优先搜索策略写一算法,判别以邻接表方式存储的有向图中是否存在由顶点vi到顶点vj的路径(i!=j)。注意:算法中涉及的图的基本操作必须在此存储结构上实现。

int visited[MAXSIZE]; 
int exist_path_DFS(ALGraph G,int i,int j){
	//深度优先判断有向图G 中顶点i 到顶点j 是否有路径,是则返回1,否则返回0
	if(i==j) 
		return 1; 
	else{
		visited[i]=1;
		for(p=G.vertices[i].firstarc;p;p=p->nextarc){
			k=p->adjvex;
			if(!visited[k]&&exist_path(k,j)) 
				return 1;
		}
	}
}

7.23 同7.22题要求,试基于图的广度优先搜索策略写一算法。

int exist_path_BFS(ALGraph G,int i,int j){
	//基于广度优先搜索判断图G中顶点i到顶点j是否存在路径,存在返回1,否则返回0
	int visited[MAXSIZE];
	InitQueue(Q);
	EnQueue(Q,i);
	while(!QueueEmpty(Q)){
		DeQueue(Q,u);
		visited[u]=1;
		for(p=G.vertices[i].firstarc;p;p=p->nextarc){
			k=p->adjvex;
			if(k==j)
				return 1;
			if(!visited[k])
				EnQueue(Q,k);
		}
	}
	return 0;
}

7.24 试利用栈的基本操作编写,按深度优先搜索策略遍历一个强连通图的非递归形式的算法。算法中不规定具体的存储结构,而将图Graph看成是一种抽象的数据类型。

void STraverse_Nonrecursive(Graph G){
	//非递归遍历强连通图G
	int visited[MAXSIZE];
	InitStack(S);
	Push(S,GetVex(G,1));
	visit(1);
	visited=1;
	while(!StackEmpty(S)){
		while(Gettop(S,i) && i){
			j=FirstAdjVex(G,i);
			if(j&&!visited[j]){
				visit(j);
				visited[j]=1;
				Push(S,j);
			}
		}
		if(!StackEmpty(S)){
			Pop(S,j);
			Gettop(S,i);
			k=NextAdjVex(G,i,j);
			if(k&&!visited[k]){
				visit(k);
				visited[k]=1;
				Push(S,k);
			}
		}
	}
}

7.25 假设有向图中n个顶点进行自然编号,并以三个数组s[1..max],fst[1..n],lst[1..n]表示之。其中数组s存放每个顶点的后继顶点的信息,第i个顶点的后继顶点存放在s中下标从fst[i]到lst[i]的分量重(i=1,2,…,n)。若fst[i]>lst[i],则第i个顶点无后继顶点。试编写判别该有向图中是否存在回路的算法。

void PathDFS(Graph &G,vexindex v){
	//深度优先进行路径遍历
	if(!OnCurrentPath[v]){
		OnCurrentPath[v]=TRUE;
		EnCurrentPath(v,CurrentPath);
		if(P(v)&&Q(CurrentPath))
			print(CurrentPath);
		else{
			w=FirstAdjVex(G,v);
			while(w){
				PathDFS(G,w);
				w=NextAdjVex(G,v,w);
			}
		}
		OnCurrentPath[v]=FALSE;
		DeCurrentPath(v,Current);
	}
}

7.26 试证明,对有向图中顶点适当地编号,可使其邻接矩阵为下三角且主对角线为全零的充要条件是:该有向图不含回路。然后写一算法对无环有向图的顶点重新编号,使其邻接矩阵变为下三角,并输出新旧编号对照表。

Status TopoNo(ALGraph G){
	//对无环有向图的顶点进行编号,使其邻接矩阵为下三角
	int new[MAXSIZE],indegree[MAXSIZE];
	n=G.vexnum;
	FindInDegree(G,indegree);
	InitStack(S);
	for(i=1;i<G.vexnum;i++)
		if(!indegree[i])
			Push(S,i);
	count=0;
	while(!StackEmpty(S)){
		Pop(S,i);
		new[i]=n--;
		count++;
		for(p=G.vertices[i].firstarc;p;p=p->nextarc){
			k=p->adjvex;
			if(!(--indegree[k]))
				Push(S,k);
		}
	}
	if(count<G.vexnum)
		return ERROR;
	for(i=1;i<=n;i+++)
		cout<<"Old No:"<<i<<" "<<"New No:"<<new[i]<<endl;
	return OK;
}

7.27 采用邻接表存储结构,编写一个判别有向图中任意给定的两个顶点之间是否存在一条长度为k的简单路径的的算法。

int visited[MAXSIZE];
int exist_len_path(ALGraph G,int i,int j,int k){
	//判断以邻接表方式存储的有向图G的顶点i到j是否存在长度为k的简单路径
	if(i==j && k==0)
		return 1;
	else if(k>0){
		visited[i]=1;
		for(p=G.vertices[i].firstarc;p;p=p->nextarc){
			l=p->adjvex;
			if(!visited[l])
				if(exist_len_path(G,l,j,k-1))
					return 1;
		}
		visited[i]=0;
	}
	return 0;
}

7.28 已知有向图和图中两个顶点u和v,试编写算法求有向图中从u到v的所有简单路径,并以右图为例手工执行你的算法,画出相应的搜索过程图。
 

int path[MAXSIZE],visited[MAXSIZE];
int Find_All_Path(ALGrach G,int u,int v,int k=0){
	//求有向图G中顶点u到v之间的所有简单路径
	path[k]=u;
	visited[u]=1;
	if(u==v){
		cout<<"找到一条路径"<<endl;
		for(i=1;path[i];i++)
			cout<<path[i];
	}else{
		for(p=G.vertices[u].firstarc;p;p=p->nextarc){
			l=p->adjvex;
			if(!visited[l])
				Find_All_Path(G,l,v,k+1);
		}
		visited[u]=0;
		path[k]=0;
	}
}

7.29 试写一个算法,在以邻接矩阵方式存储的有向图G中求顶点i到顶点j的不含回路的、长度为k的路径数。

int GetPathNum_Len(ALGraph G,int i,int j,int len){
	//求邻接矩阵方式存储的有向图G的顶点i到顶点j之间的长度为len的简单路径数目
	if(i==j &&  len==0)
		return 1;
	else if(len>0){
		sum=0;
		visited[i]=1;
		for(p=G.vertices[i].firstarc;p;p=p->nextarc){
			l=p->adjvex;
			if(!visited[l])
				sum+=GetPathNum_Len(G,l,j,len-1)
		}
		visited[i]=0;
	}
	return sum;
}

7.30 试写一个求有向图G中所有简单回路的算法。

int visited[MAXSIZE];
int path[MAXSIZE];
int cycles[MAXSIZE][MAXSIZE];
int thiscycle[MAXSIZE];
int cycount=0;
void GetAllCycle(ALGraph G){
	//求有向图中所有的简单回路
	for(v=0;v<G.vexnum;v++)
		visited[v]=0;
	for(v=0;v<G.vexnum;v++)
		if(!visited[v])
			DFS(G,v,0);
}
vodi DFS(ALGraph G,int v,int k){
	visited[v]=1;
	path[k]=v;
	for(p=G.verticws[v].firstarc;p;p=p->nextarc){
		w=p->adjvex;
		if(!visited[w])
			DFS(G,w.k+1);
		else{
			for(i=0;path[i]!=w;i++);
			for(j=0;path[i+j;i++])
				thiscycle[j]=path[i+j];
			if(!exist_cycle())
				cycles[cycount++]=thiscycle;
			for(i=0;i<G.vexnum;i++)
				thiscycle[i]=0;
		}
	}
	path[k]=0;
	visited[k]=0;
}
int exist_cycle(){
	//判断thiscycle数组中记录的回路在cycles的记录中是否已经存在
	int temp[MAXSIZE];
	for(i=0;i<cycount;i++){ 
		j=0;c=thiscycle&#0;; 
		for(k=0;cycles[i][k]!=c&&cycles[i][k]!=0;k++);
		if(cycles[i][k]){
			for(m=0;cycles[i][k+m];m++)
				temp[m]=cycles[i][k+m];
			for(n=0;n<k;n++,m++)
				temp[m]=cycles[i][n]; 
			if(!StrCompare(temp,thiscycle)) 
				return 1; 
			for(m=0;m<G.vexnum;m++) temp[m]=0; 
		}
	}
	return 0; 
}

7.31 试完成求有向图的强连通分量的算法,并分析算法的时间复杂度。

int visited[MAXSIZE];
int finished[MAXSIZE];
int count;
void Get_SGraph(OLGraph G){
	//求以十字链表存储的有向图G的强连通分量
	count=0;
	for(v=0;v<G.vexnum;v++)
		visited[v]=0;
	for(v=0;v<G.vexnum;v++)
		if(!visited[v])
			DFS1(G,v);
	for(v=0;v<G.vexnum;v++)
		visited[v]=0;
	for(i=G.vexnum-1;i>=0;i--){
		v=finished(i);
		if(!visited[v]){
			cout<<endl;
			DFS2(G,v);
		}
	}
}
void DFS1(OLGraph G,int v){
	//第一次深度优先遍历
	visited[v]=1;
	for(p=G.xlist[v].firstout;p;p=p->tlink){
		w=p->headvex;
		if(!visited[w])
			DFS1(G,w);
	}
	finished[++count] = v;
}
void DFS2(OLGraph G,int v){
	//第二次逆向深度优先遍历算法
	visited[v]=1;
	cout<<v;
	for(p=G.xlist[v].firstin;p;p=p->hlink){
		w=p->tailvex;
		if(!visited[w])
			DFS2(G,w);
	}
}

时间复杂度:O\left ( n+e \right )

7.32 试修改普里姆算法,使之能在邻接表存储结构上实现求图的最小生成森林,并分析其时间复杂度(森林的存储结构为孩子-兄弟链表)。

void Forest_Prim(ALGraph G,int k,CSTree &T){
	//从顶点k起,构造邻接表结构的最小生成森林T,用孩子兄弟链表存储
	for(j=0;j<G.vexnum;j++){
		if(j1=k){
			closedge[j]={k,Max_int};
			for(p=G.vertices[j].firstarc;p=p->nextarc)
				if(p->adjvex==k)
					closedge[j].lowcost=p->cost;
		}
		closedge[k].lowcost=0;
		for(i=1;i<G.vexnum;i++){
			k=minimum(closedge);
			if(closedge[k].lowcost<Max_int){
				Addto_Forest(T,closedge[k].adjvex,k);
				closedge[k].lowcost=0;
				for(p=G.vertices[k].firstarc;p;p=p->nextarc)
					if(p->cost<closedge[p->adjvex].lowcost)
						closedge[p->adjvex]={k,p->cost};
			}
			else
				Forest_Prime(G,k);
		}
	}
}
void Addto_Forest(CSTree &T,int i,int j){
	//添加边(i,j)添加到孩子兄弟链表表示的树T
	p=Locate(T,i);
	q=(CSTNode *) malloc(sizeof(CSTNode));
	q->data=j;
	if(!p){
		p=(CSTNode *) malloc (sizeof(CSTNode));
		p->data=i;
		for(r=T;r->nextsib;r=r->nextsib);
		r->nextsib=p;
		p->firstchild=q;
	}else if(!p->firstchild){
		p->firstchild=q;
	}else{
		for(r=p->firstchild;r->nextsib;r=r->nextsib);
		r->nextsib=q;
	}
}

时间复杂度:O\left ( n^{2} \right )

 

typedef struct{
	int vex;//结点序号
	int ecno;//结点所属的连通分量号
}VexInfo;
VexInfo vexs[MAXSIZE];//结点所属连通分量号的数组
void Init_VexInfo(VexInfo &vexs[],int vexnum){
	//初始化
	for(i=0;i<vexnum;i++)
		vexs[i]={i,i};
}
int is_ec(VexInfo vexs[],int i,int j){
	//判断顶点i和顶点j是否属于同一个连通分量
	if(vexs[i].ecno == vexs[j].ecno)
		return 1;
	else
		return 0;
}
void merge_ec(VexInfo &vexs[],int ec1,int ec2){
	//合并连通分量ec1和ec2
	for(i=0;vexs[i].vex;i++)
		if(vexs[i].ecno==ec2)
			vexs[i].ecno==ec1;
}
void MinSpanTree_Kruscal(Graph G,EdgeSetType &EdgeSet,CSTree &T){
	//克鲁斯卡尔求图的最小生成树算法
	Init_VexInfo(vexs,G.vexnum);
	ecnum=G.vexnum;
	while(ecnum>1){
		GetMinEdge(EdgeSet,u,v);
		if(!is_ec(vexs,u,v)){
			Addto_CSTree(T,u,v);
			merge_ec(vexs,vexs[u].ecno,vexs[v].ecno);
			ecnum--;
		}
		DelMinEdge(EdgeSet,u,v);
	}
}
void Addto_CSTree(CSTree &T,int i,int j){
	//把边(i,j)添加到孩子兄弟链表的树T中
	p=Locate(T,i);
	q=(CSTNode *)malloc(sizeof(CSTNode));
	q->data=j;
	if(!p->firstchild)
		p->firstchild=q;
	else{
		for(r=p->firstchild;r->nextsib;r=r->nextsib);
		r->nextsib=q;
	}
}

7.34 试编写一个算法,给有向无环图G中每个顶点赋以一个整数序号,并满足以下条件:若从顶点i至顶点j有一条弧,则应使i<j。

Status TopoSeq(ALGraph G,int newOrder[]){
	//无环有向图的结点重新编号
	int indegree[MAXSIZE];
	FindIndegree(G,indegree);
	Initstack(S);
	for(i=0;i<G.vexnum;i++)
		if(!indegree[i])
			Push(S,i);
	count=0;
	while(!stackempty(S)){
		Pop(S,i);
		newOrder[i]=++count;
		for(p=G.vertices[i].firstarc;p;p=p->nextarc){
			k=p->adjvex;
			if(!(--indegree[k]))
				Push(S,k);
		}
	}
	if(count<G.vexnum)
		return ERROR;
	return OK;
}

7.35 在DAG图中存在一个顶点r,在r和图中所有其他顶点之间均存在由r出发的有向路径,则称该DAG图有根。试编写求DAG图的根的算法。

int visited[MAXSIZE];
void Get_Root(ALGraph G){
	//求有向无环图的根
	for(v=0;v<G.vexnum;v++){
		for(w=0;w<G.vexnum;w++) visited[w]=0;
		DFS(G,v); 
		for(flag=1,w=0;w<G.vexnum;w++)
			if(!visited[w]) 
				flag=0; 
			if(flag) 
				printf("Found a root vertex:%d\n",v);
	}
}
void DFS(ALGraph G,int v){
	visited[v]=1;
	for(p=G.vertices[v].firstarc;p;p=p->nextarc){
		w=p->adjvex;
		if(!visited[w]) 
			DFS(G,w);
	}
}

7.36 在图的邻接表存储结构中,为每个顶点增加一个MPL域。试写一算法,求有向无环图G的每个顶点出发的最长路径的长度,并存入其MPL域。请给出算法的时间复杂度。

void Fill_MPL(ALGraph &G){
	//为有向无环图G 添加MPL域
	FindIndegree(G,indegree);
	for(i=0;i<G.vexnum;i++)
		if(!indegree[i]) 
			Get_MPL(G,i);
}
int Get_MPL(ALGraph &G,int i){
	//从一个顶点出发构建MPL域并返回其MPL值
	if(!G.vertices[i].firstarc){
		G.vertices[i].MPL=0;
		return 0;
	}
	else{
		max=0;
		for(p=G.vertices[i].firstarc;p;p=p->nextarc){
			j=p->adjvex;
			if(G.vertices[j].MPL==0) 
				k=Get_MPL(G,j);
			if(k>max) max=k; 
		}
		G.vertices[i]=max+1;
		return max+1;
	}
}

7.37 试设计一个求有向无环图中最长路径的算法,并估计其时间复杂度。

int maxlen,path[MAXSIZE]; //数组path 用于存储当前路径
int mlp[MAXSIZE]; //数组mlp 用于存储已发现的最长路径
void Get_Longest_Path(ALGraph G){
	//求一个有向无环图中最长的路径
	maxlen=0;
	FindIndegree(G,indegree);
	for(i=0;i<G.vexnum;i++){
		for(j=0;j<G.vexnum;j++) 
			visited[j]=0;
		if(!indegree[i]) DFS(G,i,0);
	}
	printf("Longest Path:");
	for(i=0;mlp[i];i++) 
		printf("%d",mlp[i]);
}
void DFS(ALGraph G,int i,int len){
	visited[i]=1;
	path[len]=i;
	if(len>maxlen&&!G.vertices[i].firstarc) {
		for(j=0;j<=len;j++) 
			mlp[j]=path[j]; 
		maxlen=len;
	}
	else{
		for(p=G.vertices[i].firstarc;p;p=p->nextarc){
			j=p->adjvex;
			if(!visited[j]) 
				DFS(G,j,len+1);
		}
	}
	path[i]=0;
	visited[i]=0;
}

7.38 一个四则运算算术表达式以有向无环图的邻接表方式存储,每个操作数原子都由单个字母表示。写一个算法输出其逆波兰表达式。

void NiBoLan_DAG(ALGraph G){
	//输出由向无环图形式表示的表达式的逆波兰式
	FindIndegree(G,indegree);
	for(i=0;i<G.vexnum;i++)
		if(!indegree[i]) 
			r=i;
	PrintNiBoLan_DAG(G,i);
}
void PrintNiBoLan_DAG(ALGraph G,int i){
	//打印输出以顶点i为根的表达式的逆波兰式
	c=G.vertices[i].data;
	if(!G.vertices[i].firstarc) 
		printf("%c",c);
	else {
		p=G.vertices[i].firstarc;
		PrintNiBoLan_DAG(G,p->adjvex);
		PrintNiBoLan_DAG(G,p->nexarc->adjvex);
		printf("%c",c);
	}
}

7.39 把存储结构改为二叉链表,重做7.38题。

void PrintNiBoLan_Bitree(Bitree T){
	//在二叉链表存储结构上重做上一题
	if(T->lchild) 
		PrintNiBoLan_Bitree(T->lchild);
	if(T->rchild) 
		PrintNiBoLan_Bitree(T->rchild);
	printf("%c",T->data);
}

7.40 若7.38题的运算发和操作数原子分别由字符和整数表示。请设计邻接表的结点类型,并且写一个表达式求值的算法。

int Evaluate_DAG(ALGraph G){
	//给有向无环图表示的表达式求值
	FindIndegree(G,indegree);
	for(i=0;i<G.vexnum;i++)
		if(!indegree[i]) 
			r=i;
		return Evaluate_imp(G,i);
}
int Evaluate_imp(ALGraph G,int i){
	//求子表达式的值
	if(G.vertices[i].tag=NUM) 
		return G.vertices[i].value;
	else{
		p=G.vertices[i].firstarc;
		v1=Evaluate_imp(G,p->adjvex);
		v2=Evaluate_imp(G,p->nextarc->adjvex);
		return calculate(v1,G.vertices[i].optr,v2);
	}
}

7.41 试编写利用深度优先遍历有向图实现求关键路径的算法。

void Critical_Path(ALGraph G){
	//利用深度优先遍历求网的关键路径
	FindIndegree(G,indegree);
	for(i=0;i<G.vexnum;i++)
		if(!indegree[i]) 
			DFS1(G,i);
		for(i=0;i<G.vexnum;i++)
			if(!indegree[i]) 
				DFS2(G,i);
			for(i=0;i<=G.vexnum;i++)
				if(vl[i]==ve[i]) 
					printf("%d",i);
}
void DFS1(ALGraph G,int i){
	if(!indegree[i]) 
		ve[i]=0;
	for(p=G.vertices[i].firstarc;p;p=p->nextarc){
		dut=*p->info;
		if(ve[i]+dut>ve[p->adjvex])
			ve[p->adjvex]=ve[i]+dut;
		DFS1(G,p->adjvex);
	}
}
void DFS2(ALGraph G,int i){
	if(!G.vertices[i].firstarc) 
		vl[i]=ve[i];
	else{
		for(p=G.vertices[i].firstarc;p;p=p->nextarc){
			DFS2(G,p->adjvex);
			dut=*p->info;
			if(vl[p->adjvex]-dutadjvex]-dut;
		}
	}
}

7.42 以邻接表作存储结构实现求从源点到其余各顶点的最短路径的Dijkstra算法。

void ALGraph_DIJ(ALGraph G,int v0,Pathmatrix &P,ShortestPathTable &D){
	//在邻接表存储结构上实现迪杰斯特拉算法
	for(v=0;v<G.vexnum;v++)
		D[v]=INFINITY;
	for(p=G.vertices[v0].firstarc;p;p=p->nextarc)
		D[p->adjvex]=*p->info; 
	for(v=0;v<G.vexnum;v++){
		final[v]=0;
		for(w=0;w<G.vexnum;w++) 
			P[v][w]=0; 
		if(D[v]<INFINITY){
			P[v][v0]=1;
			P[v][v]=1;
		}
	}
	D[v0]=0;final[v0]=1;
	for(i=1;i<G.vexnum;i++){
		min=INFINITY;
		for(w=0;w<G.vexnum;w++)
			if(!final[w])
				if(D[w]<min){
					v=w;
					min=D[w];
				}
				final[v]=1;
				for(p=G.vertices[v].firstarc;p;p=p->nextarc){
					w=p->adjvex;
					if(!final[w]&&(min+(*p->info)