#include<stdio.h>
#include<stdlib.h>
#include<limits.h>
#include<string.h>
#define MAX_NAME 5//顶点字符串的最大长度+1
#define MAX_INFO 20//相关信息字符串的最大长度+1
typedef int VRType;
typedef char InfoType;
typedef char VertexType[MAX_NAME];
#define INFINITY INT_MAX // 用整型最大值代替∞
#define MAX_VEX_NUM 20
typedef enum{DG,DN,UDG,UDN}GraphKind;
typedef struct
{
VRType adj;//顶点关系类型。对无权图，用1(是)或0(否)表示相邻否;对带权图，c则为权值类型
InfoType *info;//该弧相关信息的指针
}ArcCell,AdjMatrix[MAX_VEX_NUM][MAX_VEX_NUM];
typedef struct
{
VertexType vexs[MAX_VEX_NUM];
AdjMatrix arcs;
int vexnum,arcnum;//当前顶点数和弧数
GraphKind kind;
}MGraph;
/* 初始条件:图G存在,u和G中顶点有相同特征 */
/* 操作结果:若G中存在顶点u,则返回该顶点在图中位置;否则返回-1 */
/*获取定点在定点向量中的位置 如果出错就终止运行*/
int LocateVex(MGraph G,VertexType u)
{
int i;
for(i=0;i<G.vexnum;++i)
if(strcmp(u,G.vexs[i])==0)
return i;
return -1;
}
/* 采用数组(邻接矩阵)表示法,构造有向图G */
int createDG(MGraph *G)
{
int i,j,k,l,IncInfo;
char s[MAX_INFO],*info;
VertexType va,vb;
printf("请输入有向图的顶点数，弧数，弧是否含有其他信息(是:1,否:0):\n");
scanf("%d%d%d",&(*G).vexnum,&(*G).arcnum,&IncInfo);
printf("请输入%d个顶点的值(<%d个字符):\n",(*G).vexnum,MAX_NAME);
for(i=0;i<(*G).vexnum;++i)//构造顶点向量
scanf("%s",(*G).vexs[i]);
for(i=0;i<(*G).vexnum;++i)//初始化邻接矩阵
for(j=0;j<(*G).vexnum;++j)
{
(*G).arcs[i][j].adj=0;
(*G).arcs[i][j].info=NULL;
}
printf("请输入%d条弧的弧尾 弧头(以空格作为间隔):\n",(*G).arcnum);
for(k=0;k<(*G).arcnum;++k)
{
scanf("%s%s%*c",va,vb);// %*c吃掉回车符
i=LocateVex(*G,va);
j=LocateVex(*G,vb);
(*G).arcs[i][j].adj=1;//有向图
if(IncInfo)
{
printf("请输入该弧的相关信息(<%d个字符):\n",MAX_INFO);
gets(s);
l=strlen(s);
if(l)
{
info=(char *)malloc((l+1)*sizeof(char));
strcpy(info,s);
(*G).arcs[i][j].info=info;//有向
}
}
}
(*G).kind=DG;
return 1;
}
/* 采用数组(邻接矩阵)表示法,构造有向网G */
int createDN(MGraph *G)
{
int i,j,k,w,IncInfo;
char s[MAX_INFO],*info;
VertexType va,vb;
printf("请输入有向网G的顶点数，弧数，弧是否含有其他信息(是:1,否:0)\n");
scanf("%d%d%d",&(*G).vexnum,&(*G).arcnum,&IncInfo);
printf("请输入%d个顶点的值(<%d个字符):\n",(*G).vexnum,MAX_NAME);
for(i=0;i<(*G).vexnum;++i)//构造顶点向量
scanf("%s",(*G).vexs[i]);
for(i=0;i<(*G).vexnum;++i)//初始化邻接矩阵
for(j=0;j<(*G).vexnum;++j)
{
(*G).arcs[i][j].adj=INFINITY;//网
(*G).arcs[i][j].info=NULL;
}
printf("请输入%d条弧的弧尾 弧头 权值(以空格作为间隔):\n",(*G).arcnum);
for(k=0;k<(*G).arcnum;++k)
{
scanf("%s%s%d%*c",va,vb,&w);//%*c吃掉回车符
i=LocateVex(*G,va);
j=LocateVex(*G,vb);
(*G).arcs[i][j].adj=w;//有向网
if(IncInfo)
{
printf("请输入该弧的相关信息(<%d个字符):",MAX_INFO);
gets(s);
w=strlen(s);
if(w)
{
info=(char *)malloc((w+1)*sizeof(char));
strcpy(info,s);
(*G).arcs[i][j].info=info;//有向
}
}
}
(*G).kind=DN;
return 1;
}
/* 采用数组(邻接矩阵)表示法,构造无向图G */
int createUDG(MGraph *G)
{
int i,j,k,l,IncInfo;
char s[MAX_INFO],*info;
VertexType va,vb;
printf("请输入无向图G的顶点数，边数，边是否含有其他信息(是:1,否:2):\n");
scanf("%d%d%d",&(*G).vexnum,&(*G).arcnum,&IncInfo);
printf("请输入%d个顶点的值(<%d个字符)\n",(*G).vexnum,MAX_NAME);
for(i=0;i<(*G).vexnum;i++)//构造顶点向量
scanf("%s",(*G).vexs[i]);
for(i=0;i<(*G).vexnum;++i)//初始化邻接矩阵
for(j=0;j<(*G).vexnum;++j)
{
(*G).arcs[i][j].adj=0;
(*G).arcs[i][j].info=NULL;
}
printf("请输入%d条边的顶点1 顶点2(以空格作为间隔):\n",(*G).arcnum);
for(k=0;k<(*G).arcnum;++k)
{
scanf("%s%s%*c",va,vb);//%*c吃掉回车符
i=LocateVex(*G,va);
j=LocateVex(*G,vb);
(*G).arcs[i][j].adj=(*G).arcs[j][i].adj=1;//无向图
if(IncInfo)
{
printf("请输入该边的相关信息(<%d个字符):",MAX_INFO);
gets(s);
l=strlen(s);
if(l)
{
info=(char *)malloc((l+1)*sizeof(char));
strcpy(info,s);
(*G).arcs[i][j].info=(*G).arcs[j][i].info=info;//无向图
}
}
}
(*G).kind=UDG;
return 1;
}
/* 采用数组(邻接矩阵)表示法,构造无向网G。*/
int createUDN(MGraph *G)
{
int i,j,k,w,IncInfo;
char s[MAX_INFO],*info;
VertexType va,vb;
printf("请输入无向网G的顶点数，边数，边是否含有其他信息(是:1,否:0):\n");
scanf("%d%d%d",&(*G).vexnum,&(*G).arcnum,&IncInfo);
printf("请输入%d个顶点的值(<%d个字符):\n",(*G).vexnum,MAX_NAME);
for(i=0;i<(*G).vexnum;++i)//构造顶点向量
scanf("%s",(*G).vexs[i]);
for(i=0;i<(*G).vexnum;++i)//初始化邻接矩阵
for(j=0;j<(*G).vexnum;++j)
{
(*G).arcs[i][j].adj=INFINITY;//网
(*G).arcs[i][j].info=NULL;
}
printf("请输入%d条边的顶点1 顶点2 权值(以空格为间隔):\n",(*G).arcnum);
for(k=0;k<(*G).arcnum;++k)
{
scanf("%s%s%d%*c",va,vb,&w);//%*c吃掉回车符
i=LocateVex(*G,va);
j=LocateVex(*G,vb);
(*G).arcs[i][j].adj=(*G).arcs[j][i].adj=w;//无向
if(IncInfo)
{
printf("请输入该边的相关信息(<%d个字符): ",MAX_INFO);
gets(s);
w=strlen(s);
if(w)
{
info=(char *)malloc((w+1)*sizeof(char));
strcpy(info,s);
(*G).arcs[i][j].info=(*G).arcs[j][i].info=info;//无向
}
}
}
(*G).kind=UDN;
return 1;
}
/* 采用数组(邻接矩阵)表示法,构造图G*/
int createGraph(MGraph *G)
{
printf("请输入G的类型(有向图:0,有向网:1,无向图:2,无向网:3):\n");
scanf("%d",&(*G).kind);
switch((*G).kind)
{
case DG:return createDG(G);
case DN:return createDN(G);
case UDG:return createUDG(G);
case UDN:return createUDN(G);
default:return 0;
}
}
/* 输出邻接矩阵G */
void displayGraph(MGraph G)
{
int i,j;
char s[7],s1[3];
switch(G.kind)
{
case DG:
strcpy(s,"有向图\0");
strcpy(s1,"弧\0");
break;
case DN:
strcpy(s,"有向网\0");
strcpy(s1,"弧\0");
break;
case UDG:
strcpy(s,"无向图\0");
strcpy(s1,"边\0");
break;
case UDN:
strcpy(s,"无向网\0");
strcpy(s1,"边\0");
break;
}
printf("%d个顶点%d条%s的%s\n",G.vexnum,G.arcnum,s1,s);
for(i=0;i<G.vexnum;++i) /* 输出G.vexs */
printf("G.vexs[%d]=%s\n",i,G.vexs[i]);
printf("G.arcs.adj:\n"); /* 输出G.arcs.adj */
for(i=0;i<G.vexnum;i++)
{
for(j=0;j<G.vexnum;j++)
printf("%6d",G.arcs[i][j].adj);
printf("\n");
}
printf("G.arc.info:\n");//输出G.arcs.info
printf("顶点1(弧尾) 顶点2(弧头) 该%s信息：\n",s1);
if(G.kind<2)//有向
for(i=0;i<G.vexnum;i++)
for(j=0;j<G.vexnum;j++)
{
if(G.arcs[i][j].info)
printf("%5s%11s %s\n",G.vexs[i],G.vexs[j],G.arcs[i][j].info);
}
else//无向
{
for(i=0;i<G.vexnum;i++)
for(j=i+1;j<G.vexnum;j++)
if(G.arcs[i][j].info)
printf("%5s %11s %s\n",G.vexs[i],G.vexs[j],G.arcs[i][j].info);
}
}
/*初始化条件:图G存在*/
/*操作结果:销毁图G*/
void destroyGraph(MGraph *G)
{
int i,j;
if((*G).kind<2)//有向
for(i=0;i<(*G).vexnum;i++)//释放相关信息（如果有）
{
for(j=0;j<(*G).vexnum;j++)
if((*G).arcs[i][j].adj==1&&(*G).kind==0||(*G).arcs[i][j].adj!=INFINITY&&(*G).kind==1)//有向图的弧||有向网的弧
if((*G).arcs[i][j].info)//有相关信息
{
free((*G).arcs[i][j].info);
(*G).arcs[i][j].info=NULL;
}
}
else//无向
{
for(i=0;i<(*G).vexnum;i++)//释放相关信息（如果有）
for(j=i+1;j<(*G).vexnum;j++)
if((*G).arcs[i][j].adj==1&&(*G).kind||(*G).arcs[i][j].adj!=INFINITY&&(*G).kind==3)//无向图的边||无向网的边
if((*G).arcs[i][j].info)//有相关信息
{
free((*G).arcs[i][j].info);
(*G).arcs[i][j].info=(*G).arcs[j][i].info=NULL;
}
}
(*G).vexnum=0;
(*G).arcnum=0;
printf("图销毁成功!");
printf("\n\n");
}
int main()
{
int i;
MGraph G;
for(i=0;i<3;i++)
{
createGraph(&G);
displayGraph(G);
destroyGraph(&G);
}
return 0;
}
分享到：
相关推荐
这个是我学数据结构是老师留的上机作业，主要就是图的创建与输出，分四种分别为有向图，无向图，有向网，无向网，通过选择类型来选择图的种类
无向图 有向图 有向网 无向网 深度优先遍历 Ｃ语言 用户操纵界面
这包括构造有向图、有向网、无向图和无向网，以及进行深度优先遍历。首先，我们来理解图和网之间的区别。 **图和网的区别**： 图是由顶点和连接顶点的边构成的数据结构。网则是图的一种特殊形式，它包含了带权值的...
根据网络邻接矩阵画出有向图或无向图 可用于交通、电能等网络的可视化
无向图PageRank算法是Google创始人拉里·佩奇和谢尔盖·布林提出的一种网页排名技术，它在搜索引擎优化（SEO）和链接分析中起着重要作用。这个算法通过模拟随机浏览网络的行为来评估网页的重要性，使得重要的网页...
含代码和报告 ...3. 项目三：任务：建立图的存储结构（图的类型可以是有向图、无向图、有向网、无向网，学生可以任选两种类型），能够输入图的顶点和边的信息，并存储到相应存储结构中，而后输出图的邻接矩阵。
因此，如果一个无向图有n个节点，那么图的总度数将是边数的两倍。计算无向图中各节点的度，可以帮助我们更好地理解图的结构和特性，比如识别出中心节点或者分析网络的连通性。 Python中有一个强大的图论库叫做...
邻接矩阵构造无向图、网，有向图、网，在各版本vs下可运行
在"BA无标题网络创建，无向有圈图"这个主题中，我们关注的是构建一个无向图，其中任何两个节点之间都可能存在边，形成了所谓的“有圈”结构。在无向图中，边没有方向性，即如果节点A与节点B相连，那么节点B也与节点A...
无向图中，两个顶点之间的边没有方向，即A到B的边和B到A的边是同一条边。 无向完全图是指在该图中，任意两个不同的顶点之间都有一条边相连的图。例如，一个有n个顶点的无向完全图，它具有n*(n-1)/2条边，因为每个...
### C语言实现无向图的深度优先遍历 #### 概述 本篇文章将通过一个具体的C语言程序实例，详细解析如何实现无向图的深度优先遍历算法。该算法适用于计算机科学中的图形处理领域，尤其在解决路径寻找、网络分析等...
在无向图中，任何两个顶点之间至多有一条边，这与有向图（每个边都有明确的方向）形成对比。简单图则排除了自环（一个顶点到自身的边）和多重边（同一对顶点之间有多于一条的边）。 C++是这个项目的基础，它是一种...
对任意给定的图（顶点数不小于20，边数不少于30，图的类型可以是有向图、无向图、有向网、无向网），能够输入图的顶点和边（或弧）的信息，并存储到相应存储结构（邻接矩阵、邻接表、十字链表、邻接多重表，任选其中...
本文将深入探讨如何使用NetworkX处理无向图。无向图是图论中的基本概念，其中任意两个节点之间的边没有方向性。 首先，让我们了解什么是无向图。在无向图中，边不具有起点和终点的概念，而是连接两个节点的对等连接...
3. **无向网**：与无向图类似，但边可能带有权重，用于表示距离、成本等。 4. **有向网**：边是有向的，并且可以附加权重，适用于表示如交通网络、通信网络等。 这些数据结构可能包含了创建图和网的函数，例如初始...
对于无向图，矩阵是对称的，即如果节点i到节点j有边，那么节点j到节点i也有边。 2. **深度优先遍历（DFS）**： - DFS是一种递归策略，从起始节点开始，沿着某条路径一直深入，直到到达叶节点（没有未访问过的邻居...
它适用于加权有向图或无向图，但要求边的权重是非负的。其基本思想是通过维护一个优先队列（通常使用二叉堆实现），逐步扩展最短路径树，直到包含所有节点。每次从队列中取出当前最短路径的节点，并更新与之相邻且未...
1. **图的存储结构**：实验要求使用邻接表来存储连通无向图。在邻接表中，每个顶点都有一个链表，链表中的节点代表与该顶点相连的其他顶点。这种结构适合处理稀疏图，即边的数量远小于顶点数量的平方。 2. **深度...
尽管两者都有重要的应用价值，但长期以来，无向图的研究远比有向图更为深入。 #### 三、有向图的特点 有向图是指图形中的边具有方向性的图，即每条边都从一个顶点指向另一个顶点。这种结构使得有向图能够更准确地...