#define t true
#define f false
#include<iostream.h>
struct node//定义一个结构作为节点类型
{
int data
bool sign//标志位,用来标示是否遍历过
node *next
}
node* creategraph()//建立邻接表，完成无向图的输入
{
int l,m,n
bool g
cout<<"请输入节点数: "
cin>>n
node *adjacencylist=new node[n+1]//动态分配节点数组内存
adjacencylist[0].data=n//0地址存放的为节点数
adjacencylist[0].next=NULL
for(int i=1i<=ni++)//给各顶点域赋初值
{
adjacencylist[i].data=0
adjacencylist[i].next=NULL
adjacencylist[i].sign=f//表示未遍历
}
cout<<"请依次输入各条边的始点和尾点:（以0表示结束）"<<endl
cin>>l
if(l!=0)//判断输入边是否结束
g=t
while(g==t)
{
cin>>m
if((l>0)&&(l<=n)&&(m>0)&&(m<=n))//判断输入顶点是否正确
{
node *p,*q,*top
p=(node *)new(node)//分配边的一个顶点内存
p->data=m
p->next=NULL
if(adjacencylist[l].next==NULL)//为每个节点创建邻接链表
adjacencylist[l].next=p
else
{
top=adjacencylist[l].next
while(top->next!=NULL)
top=top->next
top->next=p
}
adjacencylist[l].data++//统计邻接点的个数
q=(node *)new(node)//分配边的另一个顶点内存
q->data=l
q->next=NULL
if(adjacencylist[m].next==NULL)//构建邻接表
adjacencylist[m].next=q
else
{
top=adjacencylist[m].next
while(top->next!=NULL)
top=top->next
top->next=q
}
adjacencylist[m].data++//统计邻接点的个数
}
else
cout<<"边"<<l<<"--"<<m<<"输入错误！"<<endl//错误输入标识
cin>>l
if(l==0)//边的输入结束
g=f
}
return adjacencylist//返回邻接表
}
void DepthFirstSearch(node *list)//深度优先搜索
{
int m,n=list[0].data,k,*a=new int[n]//设置一个数组用于存放节点
node *p
cout<<"采用深度优先搜索："<<endl
cout<<"请输入搜索起始节点："
cin>>k
for(int i=0i<ni++)
{
a[i]=k
list[k].sign=t
if(i==n-1)
break
m=0
while(list[k].sign==t)
{
p=list[k].next
while(p!=NULL)//找出list[k]链表中的未遍历节点
{
k=p->data
p=p->next
if(list[k].sign==f)
break
}
m++
if(list[k].sign!=f)//判断是否是p=NULL跳出while循环的
{
if(i<m)//无节点可回溯
{
cout<<"该图为非连通图!"<<endl
break
}
else
k=a[i-m]//回溯
}
}
}
for(i=1i<=ni++)//恢复原邻接表
list[i].sign=f
cout<<"深度优先搜索遍历顺序为:"
for(i=0i<ni++)//输出遍历结果
cout<<a[i]<<" "
cout<<endl
delete a//释放动态数组内存
}
void BreadthFirstSearth(node *list)//广度优先搜索
{
int m,r,k,n=list[0].data,*a=new int[n+1]//设置数组存放节点
node *p
cout<<"采用广度优先搜索："<<endl
cout<<"请输入搜索起始节点："
cin>>k
a[0]=n
a[1]=k
list[k].sign=t//标识遍历的第一个节点
m=0
r=1
while(m!=r)
{
m++
p=list[a[m]].next
while(p!=NULL)
{
k=p->data
if(list[k].sign==f)
{
r++
a[r]=k//遍历到的节点存入数组
list[k].sign=t//标识已经遍历过的节点
}
p=p->next
}
}
for(int i=1i<=ni++)//恢复原邻接表
list[i].sign=f
cout<<"广度优先搜索遍历顺序为: "
for(i=1i<=ni++)//输出遍历
cout<<a[i]<<" "
cout<<endl
delete a//释放动态数组内存
}
void PathSearth(node *list)//路径搜索
{
int *a,c,d,m,k,n=list[0].data
cout<<"请输入起始点："
cin>>k
cout<<"请输入尾节点："
cin>>c
cout<<"请输入要找的路径长度："
cin>>d
d=d+1
if(d>n)
cout<<"不存在这样的简单路径！"<<endl
else
{
a=new int[d]//动态分配数组内存存放路径上的节点
for(int i=0i<di++)
a[i]=0
a[0]=k
node *p
int x
list[a[0]].sign=t
i=1
while(a[d-1]!=c)
{
while(i<d)
{
x=1
p=list[a[i-1]].next
while(p!=NULL)
{
m=p->data
if(i==d-1&&m==a[0]&&a[0]==c)//路径存在且为回路
{
cout<<"该路径为一条回路！"<<endl
a[i]=m
i++
break
}
if(list[m].sign==f)
{
if(a[i]!=0)
{
if(x==0)//是否为已经判断过的错误路径
{
a[i]=m
list[a[i]].sign=t//标识走过节点
i++
break
}
if(a[i]==m)//设置错误路径标识
x=0
}
else
{
a[i]=m
list[a[i]].sign=t//标识走过节点
i++
break
}
}
p=p->next
}
if(p==NULL)
{
a[i]=0
i--//由此节点往下的路径不存在,回溯
list[a[i]].sign=f //还原标识符
}
if(i==0)//无法回溯,路径不存在,跳出循环
{
cout<<"不存在这样的简单路径！"<<endl
break
}
}
if(i==0)//无法回溯,路径不存在,跳出循环
break
if(a[d-1]!=c)//路径不是所要找的
{
i--//回溯
if(i>=0)
list[a[i]].sign=f//还原标识符
}
}
if(a[d-1]==c)//判断路径是否找到并输出
{
cout<<"从节点"<<k<<"到节点"<<c<<"的一条路径为："
for(i=0i<d-1i++)//输出路径
cout<<a[i]<<"-->"
cout<<a[d-1]<<endl
}
delete a
}
for(int i=1i<=ni++)//恢复原邻接表
list[i].sign=f
}
void AdjacencyListDelete(node *list)//释放邻接表的空间
{
node *p,*q
int n=list[0].data
for(int i=1i<=ni++)
{
p=list[i].next
while(p!=NULL)
{
q=p->next
delete p//释放链表节点空间
p=q
}
}
delete list//释放邻接表空间
}
void main()
{
node *list
list=creategraph()//以邻接表的形式建立一个无向图
char a,b
cout<<"请选择遍历方法：（d:深度优先搜索b:广度优先搜索）"
for(int i=1i<2i++)
{
cin>>a
switch(a)
{
case 'd':
case 'D': DepthFirstSearch(list)
cout<<"是否采用广度优先搜索重新遍历？（y:是n:否）"
cin>>b
if((b=='y')||(b=='Y'))
BreadthFirstSearth(list)
break
case 'b':
case 'B': BreadthFirstSearth(list)
cout<<"是否采用深度优先搜索重新遍历？（y:是n:否）"
cin>>b
if((b=='y')||(b=='Y'))
DepthFirstSearch(list)
break
default: cout<<"输入错误！请重新输入！"<<endl
i--
}
}
while(1)
{
cout<<"是否搜索路径？（y:是n:否）"
cin>>a
if((a=='y')||(a=='Y'))
PathSearth(list)
else if((a=='n')||(a=='N'))
break
else
cout<<"输入错误！"<<endl
}
AdjacencyListDelete(list)//释放邻接表空间
}
楼主你好，下面是源程序！
/*/////////////////////////////////////////////////////////////*/
/* 图的深度优先遍历 */
/*/////////////////////////////////////////////////////////////*/
#include <stdlib.h>
#include <stdio.h>
struct node /* 图顶点结构定义 */
{
int vertex /* 顶点数据信息 */
struct node *nextnode/* 指下一顶点的指标 */
}
typedef struct node *graph /* 图形的结构新型态 */
struct node head[9] /* 图形顶点数组 */
int visited[9] /* 遍历标记数组 */
/********************根据已有的信息建立邻接表********************/
void creategraph(int node[20][2],int num)/*num指的是图的边数*/
{
graph newnode/*指向新节点的指针定义*/
graph ptr
int from /* 边的起点 */
int to /* 边的终点 */
int i
for ( i = 0i <numi++ )/* 读取边线信息，插入邻接表*/
{
from = node[i][0]/*边线的起点*/
to = node[i][1] /* 边线的终点 */
/* 建立新顶点 */
newnode = ( graph ) malloc(sizeof(struct node))
newnode->vertex = to /* 建立顶点内容 */
newnode->nextnode = NULL /* 设定指标初值 */
ptr = &(head[from])/* 顶点位置 */
while ( ptr->nextnode != NULL ) /* 遍历至链表尾 */
ptr = ptr->nextnode/* 下一个顶点 */
ptr->nextnode = newnode /* 插入节点*/
}
}
/********************** 图的深度优先搜寻法********************/
void dfs(int current)
{
graph ptr
visited[current] = 1 /* 记录已遍历过 */
printf("vertex[%d]\n",current) /* 输出遍历顶点值 */
ptr = head[current].nextnode /* 顶点位置 */
while ( ptr != NULL ) /* 遍历至链表尾 */
{
if ( visited[ptr->vertex] == 0 ) /* 如过没遍历过 */
dfs(ptr->vertex) /* 递回遍历呼叫 */
ptr = ptr->nextnode /* 下一个顶点 */
}
}
/****************************** 主程序******************************/
void main()
{
graph ptr
int node[20][2] = { {1, 2}, {2, 1}, /* 边线数组 */
{1, 3}, {3, 1},
{1, 4}, {4, 1},
{2, 5}, {5, 2},
{2, 6}, {6, 2},
{3, 7}, {7, 3},
{4, 7}, {4, 4},
{5, 8}, {8, 5},
{6, 7}, {7, 6},
{7, 8}, {8, 7} }
int i
clrscr()
for ( i = 1i <= 8i++ ) /* 顶点数组初始化 */
{
head[i].vertex = i/*设定顶点值 */
head[i].nextnode = NULL /* 指针为空 */
visited[i] = 0/* 设定遍历初始标志 */
}
creategraph(node,20) /*建立邻接表 */
printf("Content of the gragh's ADlist is:\n")
for ( i = 1i <= 8i++ )
{
printf("vertex%d ->",head[i].vertex)/* 顶点值*/
ptr = head[i].nextnode/* 顶点位置 */
while ( ptr != NULL ) /* 遍历至链表尾 */
{
printf(" %d ",ptr->vertex) /* 印出顶点内容 */
ptr = ptr->nextnode/* 下一个顶点 */
}
printf("\n") /* 换行 */
}
printf("\nThe end of the dfs are:\n")
dfs(1) /* 打印输出遍历过程 */
printf("\n") /* 换行 */
puts(" Press any key to quit...")
getch()
}
/*//////////////////////////////////////////*/
/*图形的广度优先搜寻法 */
/* ///////////////////////////////////////*/
#include <stdlib.h>
#include <stdio.h>
#define MAXQUEUE 10 /* 队列的最大容量 */
struct node /* 图的顶点结构定义 */
{
int vertex
struct node *nextnode
}
typedef struct node *graph /* 图的结构指针*/
struct node head[9] /* 图的顶点数组 */
int visited[9] /* 遍历标记数组 */
int queue[MAXQUEUE] /* 定义序列数组 */
int front = -1 /* 序列前端*/
int rear = -1 /* 序列后端*/
/***********************二维数组向邻接表的转化****************************/
void creategraph(int node[20][2],int num)
{
graph newnode/* 顶点指针 */
graph ptr
int from /* 边起点 */
int to /* 边终点 */
int i
for ( i = 0i <numi++ )/* 第i条边的信息处理*/
{
from = node[i][0] /* 边的起点 */
to = node[i][1] /* 边的终点 */
/* 建立新顶点 */
newnode = ( graph ) malloc(sizeof(struct node))
newnode->vertex = to /*顶点内容 */
newnode->nextnode = NULL /* 设定指针初值 */
ptr = &(head[from]) /* 顶点位置 */
while ( ptr->nextnode != NULL ) /* 遍历至链表尾 */
ptr = ptr->nextnode/* 下一个顶点 */
ptr->nextnode = newnode /* 插入第i个节点的链表尾部 */
}
}
/************************ 数值入队列************************************/
int enqueue(int value)
{
if ( rear >= MAXQUEUE )/* 检查伫列是否全满 */
return -1 /* 无法存入 */
rear++ /* 后端指标往前移 */
queue[rear] = value /* 存入伫列 */
}
/************************* 数值出队列*********************************/
int dequeue()
{
if ( front == rear ) /* 队列是否为空 */
return -1 /* 为空，无法取出 */
front++ /* 前端指标往前移 */
return queue[front] /* 从队列中取出信息 */
}
/*********************** 图形的广度优先遍历************************/
void bfs(int current)
{
graph ptr
/* 处理第一个顶点 */
enqueue(current) /* 将顶点存入队列 */
visited[current] = 1 /* 已遍历过记录标志置疑1*/
printf(" Vertex[%d]\n",current) /* 打印输出遍历顶点值 */
while ( front != rear )/* 队列是否为空 */
{
current = dequeue() /* 将顶点从队列列取出 */
ptr = head[current].nextnode /* 顶点位置 */
while ( ptr != NULL ) /* 遍历至链表尾 */
{
if ( visited[ptr->vertex] == 0 ) /*顶点没有遍历过*/
{
enqueue(ptr->vertex)/* 奖定点放入队列 */
visited[ptr->vertex] = 1/* 置遍历标记为1*/
printf(" Vertex[%d]\n",ptr->vertex)/* 印出遍历顶点值 */
}
ptr = ptr->nextnode/* 下一个顶点 */
}
}
}
/*********************** 主程序 ************************************/
/*********************************************************************/
void main()
{
graph ptr
int node[20][2] = { {1, 2}, {2, 1}, /* 边信息数组 */
{6, 3}, {3, 6},
{2, 4}, {4, 2},
{1, 5}, {5, 1},
{3, 7}, {7, 3},
{1, 7}, {7, 1},
{4, 8}, {8, 4},
{5, 8}, {8, 5},
{2, 8}, {8, 2},
{7, 8}, {8, 7} }
int i
clrscr()
puts("This is an example of Width Preferred Traverse of Gragh.\n")
for ( i = 1i <= 8i++ )/*顶点结构数组初始化*/
{
head[i].vertex = i
head[i].nextnode = NULL
visited[i] = 0
}
creategraph(node,20) /* 图信息转换，邻接表的建立 */
printf("The content of the graph's allist is:\n")
for ( i = 1i <= 8i++ )
{
printf(" vertex%d =>",head[i].vertex)/* 顶点值 */
ptr = head[i].nextnode/* 顶点位置 */
while ( ptr != NULL ) /* 遍历至链表尾 */
{
printf(" %d ",ptr->vertex) /* 打印输出顶点内容 */
ptr = ptr->nextnode/* 下一个顶点 */
}
printf("\n") /* 换行 */
}
printf("The contents of BFS are:\n")
bfs(1) /* 打印输出遍历过程 */
printf("\n") /* 换行 */
puts(" Press any key to quit...")
getch()
}
Status Build_AdjList(ALGraph &G)//输入有向图的顶点数,边数,顶点信息和边的信息建立邻接表{
InitALGraph(G)
scanf("%d",&v)
if(v<0) return ERROR//顶点数不能为负
G.vexnum=v
scanf("%d",&a)
if(a<0) return ERROR//边数不能为负
G.arcnum=a
for(m=0m<vm++)
G.vertices[m].data=getchar()//输入各顶点的符号
for(m=1m<=am++)
{
t=getchar()h=getchar()//t为弧尾,h为弧头
if((i=LocateVex(G,t))<0) return ERROR
if((j=LocateVex(G,h))<0) return ERROR//顶点未找到
p=(ArcNode*)malloc(sizeof(ArcNode))
if(!G.vertices.[i].firstarc) G.vertices[i].firstarc=p
else
{
for(q=G.vertices[i].firstarcq->nextarcq=q->nextarc)
q->nextarc=p
}
p->adjvex=jp->nextarc=NULL
}//while
return OK
}//Build_AdjList
7.15
//本题中的图G均为有向无权图,其余情况容易由此写出
Status Insert_Vex(MGraph &G, char v)//在邻接矩阵表示的图G上插入顶点v
{
if(G.vexnum+1)>MAX_VERTEX_NUM return INFEASIBLE
G.vexs[++G.vexnum]=v
return OK
}//Insert_Vex
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
}//Insert_Arc
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=0i<ni++)
{
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
}//Delete_Vex
分析:如果不把待删除顶点交换到最后一个顶点的话,算法将会比较复杂,而伴随着大量元素的移动,时间复杂度也会大大增加.
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
}//Delete_Arc
7.16
//为节省篇幅,本题只给出Insert_Arc算法.其余算法请自行写出.
Status Insert_Arc(ALGraph &G,char v,char w)//在邻接表表示的图G上插入边(v,w)
{
if((i=LocateVex(G,v))<0) return ERROR
if((j=LocateVex(G,w))<0) return ERROR
p=(ArcNode*)malloc(sizeof(ArcNode))
p->adjvex=jp->nextarc=NULL
if(!G.vertices[i].firstarc) G.vertices[i].firstarc=p
else
{
for(q=G.vertices[i].firstarcq->q->nextarcq=q->nextarc)
if(q->adjvex==j) return ERROR//边已经存在
q->nextarc=p
}
G.arcnum++
return OK
}//Insert_Arc
7.17
//为节省篇幅,本题只给出较为复杂的Delete_Vex算法.其余算法请自行写出.
Status Delete_Vex(OLGraph &G,char v)//在十字链表表示的图G上删除顶点v
{
if((m=LocateVex(G,v))<0) return ERROR
n=G.vexnum
for(i=0i<ni++) //删除所有以v为头的边
{
if(G.xlist[i].firstin->tailvex==m) //如果待删除的边是头链上的第一个结点
{
q=G.xlist[i].firstin
G.xlist[i].firstin=q->hlink
free(q)G.arcnum--
}
else //否则
{
for(p=G.xlist[i].firstinp&&p->hlink->tailvex!=mp=p->hlink)
if(p)
{
q=p->hlink
p->hlink=q->hlink
free(q)G.arcnum--
}
}//else
}//for
for(i=0i<ni++) //删除所有以v为尾的边
{
if(G.xlist[i].firstout->headvex==m) //如果待删除的边是尾链上的第一个结点
{
q=G.xlist[i].firstout
G.xlist[i].firstout=q->tlink
free(q)G.arcnum--
}
else //否则
{
for(p=G.xlist[i].firstoutp&&p->tlink->headvex!=mp=p->tlink)
if(p)
{
q=p->tlink
p->tlink=q->tlink
free(q)G.arcnum--
}
}//else
}//for
for(i=mi<ni++) //顺次用结点m之后的顶点取代前一个顶点
{
G.xlist[i]=G.xlist[i+1]//修改表头向量
for(p=G.xlist[i].firstinpp=p->hlink)
p->headvex--
for(p=G.xlist[i].firstoutpp=p->tlink)
p->tailvex--//修改各链中的顶点序号
}
G.vexnum--
return OK
}//Delete_Vex
7.18
//为节省篇幅,本题只给出Delete_Arc算法.其余算法请自行写出.
Status Delete_Arc(AMLGraph &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.adjmulist[i].firstedge->jvex==j)
G.adjmulist[i].firstedge=G.adjmulist[i].firstedge->ilink
else
{
for(p=G.adjmulist[i].firstedgep&&p->ilink->jvex!=jp=p->ilink)
if (!p) return ERROR//未找到
p->ilink=p->ilink->ilink
} //在i链表中删除该边
if(G.adjmulist[j].firstedge->ivex==i)
G.adjmulist[j].firstedge=G.adjmulist[j].firstedge->jlink
else
{
for(p=G.adjmulist[j].firstedgep&&p->jlink->ivex!=ip=p->jlink)
if (!p) return ERROR//未找到
q=p->jlink
p->jlink=q->jlink
free(q)
} //在i链表中删除该边
G.arcnum--
return OK
}//Delete_Arc
7.19
Status Build_AdjMulist(AMLGraph &G)//输入有向图的顶点数,边数,顶点信息和边的信息建立邻接多重表
{
InitAMLGraph(G)
scanf("%d",&v)
if(v<0) return ERROR//顶点数不能为负
G.vexnum=v
scanf(%d",&a)
if(a<0) return ERROR//边数不能为负
G.arcnum=a
for(m=0m<vm++)
G.adjmulist[m].data=getchar()//输入各顶点的符号
for(m=1m<=am++)
{
t=getchar()h=getchar()//t为弧尾,h为弧头
if((i=LocateVex(G,t))<0) return ERROR
if((j=LocateVex(G,h))<0) return ERROR//顶点未找到
p=(EBox*)malloc(sizeof(EBox))
p->ivex=ip->jvex=j
p->ilink=NULLp->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//注意i值既可能出现在边结点的ivex域中,
else r->jlink=p//又可能出现在边结点的jvex域中
}//else //插入i链表尾部
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->ilnk
}
if(r->jvex==j) r->jlink=p
else r->ilink=p
}//else //插入j链表尾部
}//for
return OK
}//Build_AdjList
7.20
int Pass_MGraph(MGraph G)//判断一个邻接矩阵存储的有向图是不是可传递的,是则返回1,否则返回0
{
for(x=0x<G.vexnumx++)
for(y=0y<G.vexnumy++)
if(G.arcs[x][y])
{
for(z=0z<G.vexnumz++)
if(z!=x&&G.arcs[y][z]&&!G.arcs[x][z]) return 0//图不可传递的条件
}//if
return 1
}//Pass_MGraph
分析:本算法的时间复杂度大概是O(n^2*d).
7.21
int Pass_ALGraph(ALGraph G)//判断一个邻接表存储的有向图是不是可传递的,是则返回1,否则返回0
{
for(x=0x<G.vexnumx++)
for(p=G.vertices[x].firstarcpp=p->nextarc)
{
y=p->adjvex
for(q=G.vertices[y].firstarcqq=q->nextarc)
{
z=q->adjvex
if(z!=x&&!is_adj(G,x,z)) return 0
}//for
}//for
}//Pass_ALGraph
int is_adj(ALGraph G,int m,int n)//判断有向图G中是否存在边(m,n),是则返回1,否则返回0
{
for(p=G.vertices[m].firstarcpp=p->nextarc)
if(p->adjvex==n) return 1
return 0
}//is_adj
7.22
int visited[MAXSIZE]//指示顶点是否在当前路径上
int exist_path_DFS(ALGraph G,int i,int j)//深度优先判断有向图G中顶点i到顶点j是否有路径,是则返回1,否则返回0
{
if(i==j) return 1//i就是j
else
{
visited[i]=1
for(p=G.vertices[i].firstarcpp=p->nextarc)
{
k=p->adjvex
if(!visited[k]&&exist_path(k,j)) return 1//i下游的顶点到j有路径
}//for
}//else
}//exist_path_DFS
7.23
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].firstarcpp=p->nextarc)
{
k=p->adjvex
if(k==j) return 1
if(!visited[k]) EnQueue(Q,k)
}//for
}//while
return 0
}//exist_path_BFS
7.24
void STraverse_Nonrecursive(Graph G)//非递归遍历强连通图G
{
int visited[MAXSIZE]
InitStack(S)
Push(S,GetVex(S,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)//向左走到尽头
}
}//while
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)
}
}//if
}//while
}//Straverse_Nonrecursive
分析:本算法的基本思想与二叉树的先序遍历非递归算法相同,请参考6.37.由于是强连通图,所以从第一个结点出发一定能够访问到所有结点.
7.25
见书后解答.
7.26
Status TopoNo(ALGraph G)//按照题目要求顺序重排有向图中的顶点
{
int new[MAXSIZE],indegree[MAXSIZE]//储存结点的新序号
n=G.vexnum
FindInDegree(G,indegree)
InitStack(S)
for(i=1i<G.vexnumi++)
if(!indegree[i]) Push(S,i)//零入度结点入栈
count=0
while(!StackEmpty(S))
{
Pop(S,i)
new[i]=n--//记录结点的拓扑逆序序号
count++
for(p=G.vertices[i].firstarcpp=p->nextarc)
{
k=p->adjvex
if(!(--indegree[k])) Push(S,k)
}//for
}//while
if(count<G.vexnum) return ERROR//图中存在环
for(i=1i<=ni++) printf("Old No:%d New No:%d\n",i,new[i])
return OK
}//TopoNo
分析:只要按拓扑逆序对顶点编号,就可以使邻接矩阵成为下三角矩阵.
7.27
int visited[MAXSIZE]
int exist_path_len(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].firstarcpp=p->nextarc)
{
l=p->adjvex
if(!visited[l])
if(exist_path_len(G,l,j,k-1)) return 1//剩余路径长度减一
}//for
visited[i]=0//本题允许曾经被访问过的结点出现在另一条路径中
}//else
return 0//没找到
}//exist_path_len
7.28
int path[MAXSIZE],visited[MAXSIZE]//暂存遍历过程中的路径
int Find_All_Path(ALGraph G,int u,int v,int k)//求有向图G中顶点u到v之间的所有简单路径,k表示当前路径长度
{
path[k]=u//加入当前路径中
visited[u]=1
if(u==v) //找到了一条简单路径
{
printf("Found one path!\n")
for(i=0path[i]i++) printf("%d",path[i])//打印输出
}
else
for(p=G.vertices[u].firstarcpp=p->nextarc)
{
l=p->adjvex
if(!visited[l]) Find_All_Path(G,l,v,k+1)//继续寻找
}
visited[u]=0
path[k]=0//回溯
}//Find_All_Path
main()
{
...
Find_All_Path(G,u,v,0)//在主函数中初次调用,k值应为0
...
}//main
7.29
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//sum表示通过本结点的路径数
visited[i]=1
for(p=G.vertices[i].firstarcpp=p->nextarc)
{
l=p->adjvex
if(!visited[l])
sum+=GetPathNum_Len(G,l,j,len-1)//剩余路径长度减一
}//for
visited[i]=0//本题允许曾经被访问过的结点出现在另一条路径中
}//else
return sum
}//GetPathNum_Len
7.30
int visited[MAXSIZE]
int path[MAXSIZE]//暂存当前路径
int cycles[MAXSIZE][MAXSIZE]//储存发现的回路所包含的结点
int thiscycle[MAXSIZE]//储存当前发现的一个回路
int cycount=0//已发现的回路个数
void GetAllCycle(ALGraph G)//求有向图中所有的简单回路
{
for(v=0v<G.vexnumv++) visited[v]=0
for(v=0v<G.vexnumv++)
if(!visited[v]) DFS(G,v,0)//深度优先遍历
}//DFSTraverse
void DFS(ALGraph G,int v,int k)//k表示当前结点在路径上的序号
{
visited[v]=1
path[k]=v//记录当前路径
for(p=G.vertices[v].firstarcpp=p->nextarc)
{
w=p->adjvex
if(!visited[w]) DFS(G,w,k+1)
else //发现了一条回路
{
for(i=0path[i]!=wi++)//找到回路的起点
for(j=0path[i+j]i++) thiscycle[j]=path[i+j]//把回路复制下来
if(!exist_cycle()) cycles[cycount++]=thiscycle//如果该回路尚未被记录过,就添加到记录中
for(i=0i<G.vexnumi++) thiscycle[i]=0//清空目前回路数组
}//else
}//for
path[k]=0
visited[k]=0//注意只有当前路径上的结点visited为真.因此一旦遍历中发现当前结点visited为真,即表示发现了一条回路
}//DFS
int exist_cycle()//判断thiscycle数组中记录的回路在cycles的记录中是否已经存在
{
int temp[MAXSIZE]
for(i=0i<cycounti++) //判断已有的回路与thiscycle是否相同
{ //也就是,所有结点和它们的顺序都相同
j=0c=thiscycle//例如,142857和857142是相同的回路
for(k=0cycles[i][k]!=c&&cycles[i][k]!=0k++)//在cycles的一个行向量中寻找等于thiscycle第一个结点的元素
if(cycles[i][k]) //有与之相同的一个元素
{
for(m=0cycles[i][k+m]m++)
temp[m]=cycles[i][k+m]
for(n=0n<kn++,m++)
temp[m]=cycles[i][n]//调整cycles中的当前记录的循环相位并放入temp数组中
if(!StrCompare(temp,thiscycle)) //与thiscycle比较
return 1//完全相等
for(m=0m<G.vexnumm++) temp[m]=0//清空这个数组
}
}//for
return 0//所有现存回路都不与thiscycle完全相等
}//exist_cycle
分析:这个算法的思想是,在遍历中暂存当前路径,当遇到一个结点已经在路径之中时就表明存在一条回路扫描路径向量path可以获得这条回路上的所有结点.把结点序列(例如,142857)存入thiscycle中由于这种算法中,一条回路会被发现好几次,所以必须先判断该回路是否已经在cycles中被记录过,如果没有才能存入cycles的一个行向量中.把cycles的每一个行向量取出来与之比较.由于一条回路可能有多种存储顺序,比如142857等同于285714和571428,所以还要调整行向量的次序,并存入temp数组,例如,thiscycle为142857第一个结点为1,cycles的当前向量为857142,则找到后者中的1,把1后部分提到1前部分前面,最终在temp中得到142857,与thiscycle比较,发现相同,因此142857和857142是同一条回路,不予存储.这个算法太复杂,很难保证细节的准确性,大家理解思路便可.希望有人给出更加简捷的算法.
7.31
int visited[MAXSIZE]
int finished[MAXSIZE]
int count//count在第一次深度优先遍历中用于指示finished数组的填充位置
void Get_SGraph(OLGraph G)//求十字链表结构储存的有向图G的强连通分量
{
count=0
for(v=0v<G.vexnumv++) visited[v]=0
for(v=0v<G.vexnumv++) //第一次深度优先遍历建立finished数组
if(!visited[v]) DFS1(G,v)
for(v=0v<G.vexnumv++) visited[v]=0//清空visited数组
for(i=G.vexnum-1i>=0i--) //第二次逆向的深度优先遍历
{
v=finished(i)
if(!visited[v])
{
printf("\n")//不同的强连通分量在不同的行输出
DFS2(G,v)
}
}//for
}//Get_SGraph
void DFS1(OLGraph G,int v)//第一次深度优先遍历的算法
{
visited[v]=1
for(p=G.xlist[v].firstoutpp=p->tlink)
{
w=p->headvex
if(!visited[w]) DFS1(G,w)
}//for
finished[++count]=v//在第一次遍历中建立finished数组
}//DFS1
void DFS2(OLGraph G,int v)//第二次逆向的深度优先遍历的算法
{
visited[v]=1
printf("%d",v)//在第二次遍历中输出结点序号
for(p=G.xlist[v].firstinpp=p->hlink)
{
w=p->tailvex
if(!visited[w]) DFS2(G,w)
}//for
}//DFS2
分析:求有向图的强连通分量的算法的时间复杂度和深度优先遍历相同,也为O(n+e).
7.32
void Forest_Prim(ALGraph G,int k,CSTree &T)//从顶点k出发,构造邻接表结构的有向图G的最小生成森林T,用孩子兄弟链表存储
{
for(j=0j<G.vexnumj++) //以下在Prim算法基础上稍作改动
if(j!=k)
{
closedge[j]={k,Max_int}
for(p=G.vertices[j].firstarcpp=p->nextarc)
if(p->adjvex==k) closedge[j].lowcost=p->cost
}//if
closedge[k].lowcost=0
for(i=1i<G.vexnumi++)
{
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].firstarcpp=p->nextarc)
if(p->cost<closedge[p->adjvex].lowcost)
closedge[p->adjvex]={k,p->cost}
}//if
else Forest_Prim(G,k)//对另外一个连通分量执行算法
}//for
}//Forest_Prim
void Addto_Forest(CSTree &T,int i,int j)//把边(i,j)添加到孩子兄弟链表表示的树T中
{
p=Locate(T,i)//找到结点i对应的指针p,过程略
q=(CSTNode*)malloc(sizeof(CSTNode))
q->data=j
if(!p) //起始顶点不属于森林中已有的任何一棵树
{
p=(CSTNode*)malloc(sizeof(CSTNode))
p->data=i
for(r=Tr->nextsibr=r->nextsib)
r->nextsib=p
p->firstchild=q
} //作为新树插入到最右侧
else if(!p->firstchild) //双亲还没有孩子
p->firstchild=q//作为双亲的第一个孩子
else //双亲已经有了孩子
{
for(r=p->firstchildr->nextsibr=r->nextsib)
r->nextsib=q//作为双亲最后一个孩子的兄弟
}
}//Addto_Forest
main()
{
...
T=(CSTNode*)malloc(sizeof(CSTNode))//建立树根
T->data=1
Forest_Prim(G,1,T)
...
}//main
分析:这个算法是在Prim算法的基础上添加了非连通图支持和孩子兄弟链表构建模块而得到的,其时间复杂度为O(n^2).
7.33
typedef struct {
int vex//结点序号
int ecno//结点所属的连通分量号
} VexInfo
VexInfo vexs[MAXSIZE]//记录结点所属连通分量号的数组
void Init_VexInfo(VexInfo &vexs[ ],int vexnum)//初始化
{
for(i=0i<vexnumi++)
vexs[i]={i,i}//初始状态:每一个结点都属于不同的连通分量
}//Init_VexInfo
int is_ec(VexInfo vexs[ ],int i,int j)//判断顶点i和顶点j是否属于同一个连通分量
{
if(vexs[i].ecno==vexs[j].ecno) return 1
欢迎分享，转载请注明来源：内存溢出
微信扫一扫
支付宝扫一扫
评论列表（0条）