第1关：图的邻接矩阵存储及求邻接点操作

本文主要是介绍第1关：图的邻接矩阵存储及求邻接点操作，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

任务要求
参考答案
评论2

任务描述
相关知识
- 顶点集合
- 边集合
编程要求
测试说明

任务描述

本关任务：要求从文件输入顶点和边数据，包括顶点信息、边、权值等，编写程序实现以下功能。 1）构造无向网G的邻接矩阵和顶点集，即图的存储结构为邻接矩阵。 2）输出无向网G的各顶点和邻接矩阵。 3）输出无向网G中顶点H的所有邻接顶点。

编程要求

根据提示，在右侧编辑器补充代码，要求从文件中输入顶点和边数据，包括顶点信息、边、权值等，编写函数实现图的基本运算：

void CreateGraphF(MGraph &G);// 采用数组(邻接矩阵)表示法，由文件构造无向网G
void Display(MGraph G); // 输出邻接矩阵存储表示的图G
int LocateVex(MGraph G,VertexType u);//若G中存在顶点u，则返回该顶点在图中位置；否则返回-1
VertexType& GetVex(MGraph G,int v); // v是G中某个顶点的序号，返回v的值
int FirstAdjVex(MGraph G,VertexType v);//v是图G中某个顶点，返回v的第一个邻接顶点的序号。若顶点在G中没有邻接顶点，则返回-1
int NextAdjVex(MGraph G,VertexType v,VertexType w);//v是G中某个顶点，w是v的邻接顶点，返回v的(相对于w的)下一个邻接顶点的序号，若w是v的最后一个邻接顶点，则返回-1
void DestroyGraph(MGraph &G); // 销毁图G

测试说明

平台会对你编写的代码进行测试：

测试输入： 3 lt.txt 武汉

输入说明：第一行输入3，表示输入图的类型为无向网。第二行输入文件名，该文件里保存了图的数据信息，内容如下： 6 9 武汉上海长沙南京成都广州武汉长沙 9 武汉成都 2 长沙上海 2 长沙南京 2 上海南京 5 上海广州 4 上海成都 3 南京广州 8 成都广州 6

第1行为图的顶点的个数n；第2行为图的边的条数m；第3行至第n+2行是n个顶点的数据；第n+3行至第n+m+2行是m条边的数据；最后输入一个顶点的数据

预期输出： 无向网 6个顶点9条边。顶点依次是: 武汉上海长沙南京成都广州 图的邻接矩阵: ∞ ∞ 9 ∞ 2 ∞ ∞ ∞ 2 5 ∞ ∞ 9 2 ∞ 2 ∞ ∞ ∞ 5 2 ∞ ∞ ∞ 2 ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ 长沙成都

#include<stdio.h> 
#include<stdlib.h> 
#include<string.h>
#include<limits.h> typedef int VRType;    // 顶点关系类型 
typedef char VertexType[20]; // 顶点类型 
// 图的数组(邻接矩阵)存储表示 
#define INFINITY INT_MAX // 用整型最大值代替∞ 
#define MAX_VERTEX_NUM 20 // 最大顶点个数 
typedef enum{DG,DN,UDG,UDN}GraphKind; // {有向图,有向网,无向图,无向网} typedef struct
{VRType adj; // 顶点关系类型。对无权图，用1(是)或0(否)表示相邻否；对带权图，则为权值 
}ArcCell,AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM]; // 二维数组 typedef struct      // 图的数组(邻接矩阵)存储 
{VertexType vexs[MAX_VERTEX_NUM]; // 顶点向量 AdjMatrix arcs; // 邻接矩阵 int vexnum,arcnum; // 图的当前顶点数和弧数 GraphKind kind; // 图的种类标志 
}MGraph;  void visit(VertexType i);void CreateGraphF(MGraph &G);// 采用数组(邻接矩阵)表示法，由文件构造无向网G
void Display(MGraph G);    // 输出邻接矩阵存储表示的图G
int LocateVex(MGraph G,VertexType u);//若G中存在顶点u，则返回该顶点在图中位置；否则返回-1 
VertexType* GetVex(MGraph G,int v);    // v是G中某个顶点的序号，返回v的值
int FirstAdjVex(MGraph G,VertexType v);//v是图G中某个顶点，返回v的第一个邻接顶点的序号。若顶点在G中没有邻接顶点，则返回-1 
int NextAdjVex(MGraph G,VertexType v,VertexType w);//v是G中某个顶点，w是v的邻接顶点，返回v的(相对于w的)下一个邻接顶点的序号，若w是v的最后一个邻接顶点，则返回-1 
void DestroyGraph(MGraph &G); // 销毁图G int main()
{MGraph g;VertexType v1,v2;CreateGraphF(g);      // 利用数据文件创建邻接矩阵表示的图	Display(g);           // 输出图  int i,j,k,n;//printf("请输入顶点的值: ");scanf("%s",v1);//printf("输出图G中顶点%s的所有邻接顶点: ",v1);k=FirstAdjVex(g,v1);while(k!=-1){ strcpy(v2, g.vexs[k] );visit(v2);k=NextAdjVex(g,v1,v2);}printf("\n");    return 0;
}void visit(VertexType i)
{printf("%s ",i);
}void CreateGraphF(MGraph &G)
{// 采用数组(邻接矩阵)表示法，由文件构造无向网G/********** Begin **********/int i,j,k,w;char filename[13];VertexType va,vb;FILE * graphlist;scanf("%d",&G.kind);scanf("%s",filename);graphlist=fopen(filename,"r");fscanf(graphlist,"%d",&G.vexnum);fscanf(graphlist,"%d",&G.arcnum);for(i=0;i<G.vexnum;i++)fscanf(graphlist,"%s",G.vexs[i]);for(i=0;i<G.vexnum;++i)for(j=0;j<G.vexnum;++j){if(G.kind%2)G.arcs[i][j].adj=INFINITY;elseG.arcs[i][j].adj=0;}for(k=0;k<G.arcnum;++k){if(G.kind%2)fscanf(graphlist,"%s%s%d",va,vb,&w);elsefscanf(graphlist,"%s%s",va,vb);i=LocateVex(G,va);j=LocateVex(G,vb);if(G.kind==0)G.arcs[i][j].adj=1;else if(G.kind==1)G.arcs[i][j].adj=w;else if(G.kind==2)G.arcs[i][j].adj=G.arcs[j][i].adj=1;elseG.arcs[i][j].adj=G.arcs[j][i].adj=w;}fclose(graphlist);/********** End **********/
}void Display(MGraph G)
{// 输出邻接矩阵存储表示的图G/********** Begin **********/int i,j;switch(G.kind){case DG:printf("有向图\n");break;case DN:printf("有向网\n");break;case UDG:printf("无向图\n");break;case UDN:printf("无向网\n");}printf("%d个顶点%d条边。顶点依次是: ",G.vexnum,G.arcnum);for(i=0;i<G.vexnum;++i)printf("%s ",G.vexs[i]);printf("\n图的邻接矩阵:\n");for(i=0;i<G.vexnum;i++){for(j=0;j<G.vexnum;j++)if(G.kind%2){if(G.arcs[i][j].adj==INFINITY)printf("%s\t","∞");elseprintf("%d\t",G.arcs[i][j].adj);}elseprintf("%d\t",G.arcs[i][j].adj);printf("\n");}/********** End **********/
}int LocateVex(MGraph G,VertexType u)
{//初始条件：图G存在，u和G中顶点有相同特征// 操作结果：若G中存在顶点u，则返回该顶点在图中位置；否则返回-1 /********** Begin **********/int i;for(i=0;i<G.vexnum;++i)if(strcmp(u,G.vexs[i])==0) return i;return -1;  /********** Begin **********/
}VertexType* GetVex(MGraph G,int v)
{ // 初始条件：图G存在，v是G中某个顶点的序号。操作结果：返回v的值/********** Begin **********/if(v>=G.vexnum || v<0)exit(0);return &(G.vexs[v]); /********** End **********/
}int FirstAdjVex(MGraph G,VertexType v)
{// 初始条件：图G存在，v是G中某个顶点 // 操作结果：返回v的第一个邻接顶点的序号。若顶点在G中没有邻接顶点，则返回-1 /********** Begin **********/int i,j,k;if(G.kind%2)j=INFINITY;elsej=0;k=LocateVex(G,v);for(i=0;i<G.vexnum;i++)if(G.arcs[k][i].adj!=j)return i;return -1;/********** End **********/
}int NextAdjVex(MGraph G,VertexType v,VertexType w)
{// 初始条件：图G存在，v是G中某个顶点，w是v的邻接顶点 // 操作结果：返回v的(相对于w的)下一个邻接顶点的序号，若w是v的最后一个邻接顶点，则返回-1 /********** Begin **********/int i,j,k1,k2;if(G.kind%2)j=INFINITY;elsej=0;k1=LocateVex(G,v);k2=LocateVex(G,w);for(i=k2+1;i<G.vexnum;i++)if(G.arcs[k1][i].adj!=j)return i;return -1;/********** End **********/
}void DestroyGraph(MGraph &G)
{ // 初始条件：图G存在。操作结果：销毁图G /********** Begin **********/int i,j,k=0;if(G.kind%2) k=INFINITY; G.vexnum=0; G.arcnum=0; /********** End **********/
}