《数据结构教程(李春葆主编 第五版)》第八章源代码—图(Part I)
图的基本运算算法(graph.cpp)#include <stdio.h>#include <malloc.h>//图的两种存储结构#define INF 32767//定义∞#defineMAXV 100//最大顶点个数typedef char InfoType;//以下定义邻接矩阵类型typedef struct{int no;//顶点编号InfoType info;/
·
图的基本运算算法(graph.cpp)
#include <stdio.h>
#include <malloc.h>
//图的两种存储结构
#define INF 32767 //定义∞
#define MAXV 100 //最大顶点个数
typedef char InfoType;
//以下定义邻接矩阵类型
typedef struct
{ int no; //顶点编号
InfoType info; //顶点其他信息
} VertexType; //顶点类型
typedef struct
{ int edges[MAXV][MAXV]; //邻接矩阵数组
int n,e; //顶点数，边数
VertexType vexs[MAXV]; //存放顶点信息
} MatGraph; //完整的图邻接矩阵类型
//以下定义邻接表类型
typedef struct ANode
{ int adjvex; //该边的邻接点编号
struct ANode *nextarc; //指向下一条边的指针
int weight; //该边的相关信息，如权值（用整型表示）
} ArcNode; //边结点类型
typedef struct Vnode
{ InfoType info; //顶点其他信息
int count; //存放顶点入度,仅仅用于拓扑排序
ArcNode *firstarc; //指向第一条边
} VNode; //邻接表头结点类型
typedef struct
{ VNode adjlist[MAXV]; //邻接表头结点数组
int n,e; //图中顶点数n和边数e
} AdjGraph; //完整的图邻接表类型
//----邻接矩阵的基本运算算法----------------------------------
void CreateMat(MatGraph &g,int A[MAXV][MAXV],int n,int e) //创建图的邻接矩阵
{
int i,j;
g.n=n; g.e=e;
for (i=0;i<g.n;i++)
for (j=0;j<g.n;j++)
g.edges[i][j]=A[i][j];
}
void DispMat(MatGraph g) //输出邻接矩阵g
{
int i,j;
for (i=0;i<g.n;i++)
{
for (j=0;j<g.n;j++)
if (g.edges[i][j]!=INF)
printf("%4d",g.edges[i][j]);
else
printf("%4s","∞");
printf("\n");
}
}
//----邻接表的基本运算算法------------------------------------
void CreateAdj(AdjGraph *&G,int A[MAXV][MAXV],int n,int e) //创建图的邻接表
{
int i,j;
ArcNode *p;
G=(AdjGraph *)malloc(sizeof(AdjGraph));
for (i=0;i<n;i++) //给邻接表中所有头结点的指针域置初值
G->adjlist[i].firstarc=NULL;
for (i=0;i<n;i++) //检查邻接矩阵中每个元素
for (j=n-1;j>=0;j--)
if (A[i][j]!=0 && A[i][j]!=INF) //存在一条边
{ p=(ArcNode *)malloc(sizeof(ArcNode)); //创建一个结点p
p->adjvex=j;
p->weight=A[i][j];
p->nextarc=G->adjlist[i].firstarc; //采用头插法插入结点p
G->adjlist[i].firstarc=p;
}
G->n=n; G->e=n;
}
void DispAdj(AdjGraph *G) //输出邻接表G
{
int i;
ArcNode *p;
for (i=0;i<G->n;i++)
{
p=G->adjlist[i].firstarc;
printf("%3d: ",i);
while (p!=NULL)
{
printf("%3d[%d]→",p->adjvex,p->weight);
p=p->nextarc;
}
printf("∧\n");
}
}
void DestroyAdj(AdjGraph *&G) //销毁图的邻接表
{ int i;
ArcNode *pre,*p;
for (i=0;i<G->n;i++) //扫描所有的单链表
{ pre=G->adjlist[i].firstarc; //p指向第i个单链表的首结点
if (pre!=NULL)
{ p=pre->nextarc;
while (p!=NULL) //释放第i个单链表的所有边结点
{ free(pre);
pre=p; p=p->nextarc;
}
free(pre);
}
}
free(G); //释放头结点数组
}
广度优先遍历算法
//广度优先遍历算法
#include "graph.cpp"
#define MaxSize 100
//--广度优先遍历中使用队列的基本运算算法-------------------
typedef int ElemType;
typedef struct
{
ElemType data[MaxSize];
int front,rear; //队首和队尾指针
} SqQueue;
void InitQueue(SqQueue *&q)
{ q=(SqQueue *)malloc (sizeof(SqQueue));
q->front=q->rear=0;
}
void DestroyQueue(SqQueue *&q)
{
free(q);
}
bool QueueEmpty(SqQueue *q)
{
return(q->front==q->rear);
}
bool enQueue(SqQueue *&q,ElemType e)
{ if ((q->rear+1)%MaxSize==q->front) //队满上溢出
return false;
q->rear=(q->rear+1)%MaxSize;
q->data[q->rear]=e;
return true;
}
bool deQueue(SqQueue *&q,ElemType &e)
{ if (q->front==q->rear) //队空下溢出
return false;
q->front=(q->front+1)%MaxSize;
e=q->data[q->front];
return true;
}
//---------------------------------------------------------
void BFS(AdjGraph *G,int v)
{
int w,i;
ArcNode *p;
SqQueue *qu; //定义环形队列指针
InitQueue(qu); //初始化队列
int visited[MAXV]; //定义顶点访问标志数组
for (i=0;i<G->n;i++) visited[i]=0; //访问标志数组初始化
printf("%2d",v); //输出被访问顶点的编号
visited[v]=1; //置已访问标记
enQueue(qu,v);
while (!QueueEmpty(qu)) //队不空循环
{
deQueue(qu,w); //出队一个顶点w
p=G->adjlist[w].firstarc; //指向w的第一个邻接点
while (p!=NULL) //查找w的所有邻接点
{
if (visited[p->adjvex]==0) //若当前邻接点未被访问
{
printf("%2d",p->adjvex); //访问该邻接点
visited[p->adjvex]=1; //置已访问标记
enQueue(qu,p->adjvex); //该顶点进队
}
p=p->nextarc; //找下一个邻接点
}
}
printf("\n");
}
int main()
{
AdjGraph *G;
int A[MAXV][MAXV]={{0,1,0,1,1},{1,0,1,1,0},
{0,1,0,1,1},{1,1,1,0,1},{1,0,1,1,0}};
int n=5, e=8;
CreateAdj(G,A,n,e); //建立《教程》中图8.1(a)的邻接表
printf("图G的邻接表:\n");
DispAdj(G); //输出邻接表G
printf("广度优先序列:");BFS(G,2);printf("\n");
DestroyAdj(G); //销毁邻接表
return 1;
}
深度优先遍历算法
#include "graph.cpp"
int visited[MAXV]={0};
void DFS(AdjGraph *G,int v)
{
ArcNode *p;
visited[v]=1; //置已访问标记
printf("%d ",v); //输出被访问顶点的编号
p=G->adjlist[v].firstarc; //p指向顶点v的第一条弧的弧头结点
while (p!=NULL)
{
if (visited[p->adjvex]==0) //若p->adjvex顶点未访问,递归访问它
DFS(G,p->adjvex);
p=p->nextarc; //p指向顶点v的下一条弧的弧头结点
}
}
int main()
{
AdjGraph *G;
int A[MAXV][MAXV]={{0,1,0,1,1},{1,0,1,1,0},
{0,1,0,1,1},{1,1,1,0,1},{1,0,1,1,0}};
int n=5, e=8;
CreateAdj(G,A,n,e); //建立《教程》中图8.1(a)的邻接表
printf("图G的邻接表:\n");
DispAdj(G); //输出邻接表G
printf("深度优先序列(递归):");DFS(G,2);printf("\n");
DestroyAdj(G); //销毁邻接表
return 1;
}
判断从顶点v出发能否找到环
#include "graph.cpp"
int visited[MAXV]; //全局变量
void hasCycle(AdjGraph *G,int v,bool &has)
//判断从顶点v出发能否找到环
{
ArcNode *p;
int w;
visited[v]=1; //置已访问标记
p=G->adjlist[v].firstarc; //p指向顶点v的第一个邻接点
while (p!=NULL)
{ w=p->adjvex;
if (visited[w]==0) //若顶点w未访问，递归访问它
hasCycle(G,w,has);
else //又找到了已访问过的顶点说明有回路
has=true;
p=p->nextarc; //找下一个邻接点
}
visited[v]=0;
}
bool Cycle(AdjGraph *G) //判断有向图G中是否存在环
{
bool has=false;
for (int i=0;i<G->n;i++)
{
hasCycle(G,i,has);
if (has) return true;
}
return false;
}
int main()
{
/* int n=7, e=12;
int A[MAXV][MAXV]={
{0, 2, 5, 3, INF,INF,INF},
{INF,0, 2, INF,INF,8, INF},
{INF,INF,0, 1, 3, 5, INF},
{INF,INF,INF,0, 5, INF,INF},
{INF,INF,INF,INF,0, 3, 9},
{INF,INF,INF,INF,INF,0, 5},
{INF,INF,INF,INF,INF,INF,0}
};
*/
int n=4, e=4;
int A[MAXV][MAXV]={
{0, 1, 1,INF},
{INF, 0, INF,INF},
{INF,1, 0,1},
{INF,INF,INF,0}
};
AdjGraph *G;
CreateAdj(G,A,n,e); ////建立图8.19的邻接表
for (int i=0;i<n;i++) //visited数组置初值
visited[i]=0;
printf("图G:\n");DispAdj(G);//输出邻接表
bool has=false;
printf("has=%d\n",Cycle(G));
DestroyAdj(G); //销毁邻接表
return 1;
}
Prim(普利姆)算法
#include "graph.cpp"
void Prim(MatGraph g,int v)
{
int lowcost[MAXV]; //顶点i是否在U中
int min;
int closest[MAXV],i,j,k;
for (i=0;i<g.n;i++) //给lowcost[]和closest[]置初值
{
lowcost[i]=g.edges[v][i];
closest[i]=v;
}
for (i=1;i<g.n;i++) //找出n-1个顶点
{
min=INF;
for (j=0;j<g.n;j++) //在(V-U)中找出离U最近的顶点k
if (lowcost[j]!=0 && lowcost[j]<min)
{
min=lowcost[j];
k=j; //k记录最近顶点的编号
}
printf(" 边(%d,%d)权为:%d\n",closest[k],k,min);
lowcost[k]=0; //标记k已经加入U
for (j=0;j<g.n;j++) //修改数组lowcost和closest
if (g.edges[k][j]!=0 && g.edges[k][j]<lowcost[j])
{
lowcost[j]=g.edges[k][j];
closest[j]=k;
}
}
}
int main()
{
MatGraph g;
int A[MAXV][MAXV]={
{0,28,INF,INF,INF,10,INF},
{28,0,16,INF,INF,INF,14},
{INF,16,0,12,INF,INF,INF},
{INF,INF,12,0,22,INF,18},
{INF,INF,INF,22,0,25,24},
{10,INF,INF,INF,25,0,INF},
{INF,14,INF,18,24,INF,0}};
int n=7, e=9;
CreateMat(g,A,n,e); //建立《教程》中图8.27的邻接矩阵
printf("图G的邻接矩阵:\n");
DispMat(g); //输出邻接矩阵
int v=0;
printf("Prim算法结果(起始点为%d)\n",v);
Prim(g,v);
return 1;
}
Floyd(弗洛伊德)算法
#include "graph.cpp"
void Dispath(MatGraph g,int A[][MAXV],int path[][MAXV])
{ int i,j,k,s;
int apath[MAXV],d; //存放一条最短路径中间顶点(反向)及其顶点个数
for (i=0;i<g.n;i++)
for (j=0;j<g.n;j++)
{ if (A[i][j]!=INF && i!=j) //若顶点i和j之间存在路径
{ printf(" 从%d到%d的路径为:",i,j);
k=path[i][j];
d=0; apath[d]=j; //路径上添加终点
while (k!=-1 && k!=i) //路径上添加中间点
{ d++; apath[d]=k;
k=path[i][k];
}
d++; apath[d]=i; //路径上添加起点
printf("%d",apath[d]); //输出起点
for (s=d-1;s>=0;s--) //输出路径上的中间顶点
printf(",%d",apath[s]);
printf("\t路径长度为:%d\n",A[i][j]);
}
}
}
void Floyd(MatGraph g) //Floyd算法
{ int A[MAXV][MAXV],path[MAXV][MAXV];
int i,j,k;
for (i=0;i<g.n;i++)
for (j=0;j<g.n;j++)
{ A[i][j]=g.edges[i][j];
if (i!=j && g.edges[i][j]<INF)
path[i][j]=i; //顶点i到j有边时
else
path[i][j]=-1; //顶点i到j没有边时
}
for (k=0;k<g.n;k++) //依次考察所有顶点
{ for (i=0;i<g.n;i++)
for (j=0;j<g.n;j++)
if (A[i][j]>A[i][k]+A[k][j])
{ A[i][j]=A[i][k]+A[k][j]; //修改最短路径长度
path[i][j]=path[k][j]; //修改最短路径
}
}
Dispath(g,A,path); //输出最短路径
}
/*
int main()
{
MatGraph g;
int A[MAXV][MAXV]={
{0, 5,INF,7},
{INF,0, 4,2},
{3, 3, 0,2},
{INF,INF,1,0}};
int n=4, e=8;
CreateMat(g,A,n,e); //建立《教程》中图8.41的邻接矩阵
printf("图G的邻接矩阵:\n");
DispMat(g); //输出邻接矩阵
printf("各顶点对的最短路径:\n");
Floyd(g);
return 1;
}
*/
int main()
{
MatGraph g;
int A[MAXV][MAXV]={
{0, 6, INF,INF,2},
{INF,0, INF,INF,INF},
{INF,1, 0, 3, INF},
{2, INF,INF,0, INF},
{INF,3, 1, 3, 0}
};
int n=5, e=8;
CreateMat(g,A,n,e); //建立图的邻接矩阵
printf("图G的邻接矩阵:\n");
DispMat(g); //输出邻接矩阵
printf("各顶点对的最短路径:\n");
Floyd(g);
return 1;
}
魔乐社区（Modelers.cn) 是一个中立、公益的人工智能社区，提供人工智能工具、模型、数据的托管、展示与应用协同服务，为人工智能开发及爱好者搭建开放的学习交流平台。社区通过理事会方式运作，由全产业链共同建设、共同运营、共同享有，推动国产AI生态繁荣发展。
更多推荐
7
0- 0
已为社区贡献11条内容
所有评论(0)