图的三种创建

每一个不曾起舞的日子都是对生命的一种辜负

• 前言
• 1、邻接矩阵
• • 结构体
  • 创建邻接矩阵
  • 效果截图
• 2、邻接表
• • 结构
  • • 特点
    • 结构体
  • 创建邻接表
  • 打印邻接表
  • 效果截图
• 3、十字链表法
• • 结构体定义
  • 创建十字链表
  • 打印十字链表
  • 运行结果
• 代码汇总(可执行)

这里主要写三种创建方式，邻接矩阵，邻接表，十字链表法
英语小课堂
vertex ：顶点
arc :弧
edge：边

邻接矩阵适合存储稠密图，不会造成空间的很大浪费 其实创建图也就是一个填二维数组的过程

#define MaxInt 32767  //表示极大值∞  其实就是一种无穷标志
#define MVNum  100    //表示最大顶点数 
typedef char VerTexType;//假设顶点的数据结构类型为char 
typedef int  ArcType;//假设权值类型为整形
typedef struct{
	 VerTexType vexs[MVNum];//顶点表 
	 ArcType  arcs[MVNum][MVNum];//邻接矩阵 
	 int vexnum;//图的当前顶点数
	 int arcnum;//图的当前边数
}AMGraph;

//创建一个无向图 ，其实就是填充两个数组 
void CreateAdjoin(AMGraph &G){
	cout<<"请输入顶点数和边数"<>G.vexnum>>G.arcnum; 
	cout<<"请输入各个顶点名称"<
		cin>>G.vexs[i]; 
	}
	for(int h=0;h
		char vex1;char vex2;
		cout<<"请输入弧的两个顶点"<>vex1>>vex2; 
		//首先来看是否存在这两个顶点  若是存在则找到这两个点对应的下标
		// 当然创建的时候一种更加简单的方式就是遍历二维数组 一个一个输入
		int i=0;while(G.vexs[i++]!=vex1);
		int j=0;while(G.vexs[j++]!=vex2);
		if(i>G.vexnum||j>G.vexnum){//没有找到 
			cout<<"你输入的结点值不正确"<
			cout<<"请输入此边对应的权重"<>G.arcs[i-1][j-1];
			G.arcs[j-1][i-1]=G.arcs[i-1][j-1];
		}
	}
	PrintAMG(G);
}

当一个图为稀疏图，使用邻接矩阵要浪费大量的存储空间 而图的邻接表法结合了顺序存储和链式存储方式，减少了不必要的浪费
结构：对图G中的每一个顶点建立一个单链表，第i 个单链表中结点表示依附于顶点v的边，这个单链表就称为顶点v的边表，边表的头指针和顶点的数据信息采用顺序存储称为顶点表(当然也可以使用单链表来存储)，所以在邻接表中存在两种结点，顶点表结点和边表结点 结构如下图

顶点表(称为表头结点如上图的V0,V1)结构分为两部分，数据域和指针域。数据域用于存储顶点数据信息，指针域用于链接下一个节点，跟之前的单链表是一样的

那么除了表头节点我们还有由表头节点引出来的链表，称为边表，若边表的节点存储的是图不是网，那么任仍然可以使用上边图示的存储结构，但是如果存储的是网，那么就可以使用下面的存储结构（adjvex存储与表头节点有关系的顶点的下标，next是连接的链表，info表示的是权重等信息：所以也就需要多带一个信息

若是G为无向图 则需要的存储空间为O(|V|+2|E|) 若是G为有向图，则所需的存储空间为O(|V|+|E|)
对于稀疏图 采用邻接矩阵表示将极大的节省存储空间
在无向图的邻接表中 给定一个顶点 能很快的找到它的所有领边，因为只需要读取它的邻接表即可
**在有向图的邻接表表示中，求一个给定顶点的出度只需要计算其中邻接表中的结点个数 **
求其顶点的出度：
1、遍历整个邻接表中的节点，统计数据域与该顶点所在数组位置下标相同的节点数量，即为该顶点的入度；
2、建立一个逆邻接表，该表中的各顶点链表专门用于存储以此顶点为弧头的所有顶点在数组中的位置下标。
图的邻接表表示并不唯一 因为邻接表表示中，各边表结点的链接次序取决于建立邻接表的算法，以及边的输入次序

#define MVNum  100  //表示最大顶点数 
typedef  int VerTexType//顶点数据的数据类型
typedef struct ArcNode{//边结构
  int adjvex;//该边所指向的顶点的位置
  struct ArcNode *nextarc;//指向下一条边的指针 
  int info; //和边相关的信息如权重等  若是没有权值也可以省略 省略之后就可以于点结构相统一
}ArcNode; 
typedef struct VNode{//顶点结构
	VerTexType  data;
	ArcNode *firstarc;	//指向第一条依附该顶点的边的指针 
}VNode; 
//相当于多个链表 将首结点存放于一个数组中  就像单链表中存放长度一样 这里存放的是点与边的个数  
typedef struct{//邻接表 
	ArcNode vertices[MVNum];
	int vexnum;//图当前的顶点数 
	int arcnum;//图当前的边数 
}; 

会了链表的插入 相信这里也难不倒聪明的你的

//创建一个邻接表  其实也就是填充其中的顶点表和边表
//依然是同样的数据 只不过添加的存储的方式不一样 
void CreateAdjoinChart(AdjoinChart &G){
	cout<<"请输入顶点数以及边的个数"<>G.vexnum>>G.arcnum;
	cout<<"请输入顶点名称"<
		cin>>G.vertices[i].data;
	}
	//输入一个边有点类似于单链表的插入
	for(int h=0;h
		cout<<"请一个弧的两个边，类如从A指向B则 输入A B"<>vex1>>vex2;
		//依然需要判断输入的结点是否存在;
		int i=0;while(G.vertices[i++].data!=vex1);
		int j=0;while(G.vertices[j++].data!=vex2);
		if(i>G.vexnum||j>G.vexnum){
			cout<<"你输入的位置不正确"<//这里使用头插插入一个弧 
			ArcNode* NewAcr=(ArcNode*)malloc(sizeof(ArcNode));
			NewAcr->nextarc=G.vertices[i-1].firstarc;
			G.vertices[i-1].firstarc=NewAcr;
			cout<<"请输入此边对应的权值"<>NewAcr->info;
			NewAcr->adjvex=j-1;
		}
	}
	PrintAdjoinChart(G);
}

其实就是链表的打印

//打印邻接表  每打印一个顶点 需要打印出相对应的链表 
void PrintAdjoinChart(AdjoinChart G){
	for(int i=0;i
		ArcNode* cur=G.vertices[i].firstarc;
		while(cur){
			cout<"<adjvex].data<<" ";
			cur=cur->nextarc;
		}
		cout< 
效果截图 
 
3、十字链表法 
与邻接表不同，十字链表法仅适用于存储有向图和有向网。不仅如此，十字链表法还改善了邻接表计算图中顶点入度的问题
 十字链表存储有向图（网）的方式与邻接表有一些相同，都以图（网）中各顶点为首元节点建立多条链表，同时为了便于管理，还将所有链表的首元节点存储到同一数组（或链表）中。
 在十字链表中，对应于有向图中每一个弧有一个结点，对应的每一个顶点也有一个结点 时间复杂度O(|V|+|E|)
 
 从上图 可以看出，首元节点中有一个数据域和两个指针域（分别用 firstin 和 firstout 表示）：
 firstin 指针用于连接以当前顶点为弧头的其他顶点构成的链表；
 firstout 指针用于连接以当前顶点为弧尾的其他顶点构成的链表；
 data 用于存储该顶点中的数据；
 由此可以看出，十字链表实质上就是为每个顶点建立两个链表，分别存储以该顶点为弧头的所有顶点和以该顶点为弧尾的所有顶点。也可以理解是邻接表于逆邻接表的结合
 弧结点与结构：
 尾域tailvex：弧尾
 头域headvex：弧头
 链域hlink：指向弧头相同的下一个弧
 链域tlink 指向弧尾相同的下一个弧
 info域：指向该弧的相关信息
 
 其实相当于是两个链表，相信若是你第一次看一定是一头雾水 我们来分析一下，首先来看图 中的V0,它是有两个入弧(入度) 分别是 v2和v3 我们来看顶点表中V0中入弧指向的是20 20 的弧头指针指向的是30 也就是对应的 V2 V3 V0的出弧指向的是01 01指向的是02 02 的指向为NULL
 或者说一些不算特点的特点：
 你看有右边去掉头是不是对应七个 其实也就是七个边， 你连着读一下弧头弧尾的数字，比如 01 指的即是从0 指向1 比如02 就是从0指向2 所以01 弧尾指向的就是 02 因为他们同弧尾，比如01 和31 他们弧头相同 所以01弧头指针指向的就是 31
 
结构体定义 
#define  MAX_VERTEX_NUM 20
#define  InfoType int//图中弧包含信息的数据类型
#define  VertexType int
typedef struct ArcBox{
    int tailvex,headvex;//弧尾、弧头对应顶点在数组中的位置下标
    struct ArcBox *hlik,*tlink;//分别指向弧头相同和弧尾相同的下一个弧
    InfoType *info;//存储弧相关信息的指针
}ArcBox;
typedef struct VexNode{
    VertexType data;//顶点的数据域
    ArcBox *firstin,*firstout;//指向以该顶点为弧头和弧尾的链表首个结点
}VexNode;
typedef struct {
    VexNode xlist[MAX_VERTEX_NUM];//存储顶点的一维数组
    int vexnum,arcnum;//记录图的顶点数和弧数
}OLGraph;
 
创建十字链表 
//创建一个十字链表 其实就是一个邻接表 一个逆邻接表
 
void CreateTenList(TenListGraph &G){
	cout<<"请输入顶点数以及边的个数"<>G.vexnum>>G.arcnum;
	cout<<"请输入顶点名称"<
		cin>>G.xlist[i].data;
	}
	for(int h=0;h
		cout<<"请一个弧的两个边，类如从A指向B则 输入A B"<>vex1>>vex2;
		//依然需要判断输入的结点是否存在;
		int i=0;while(G.xlist[i++].data!=vex1);
		int j=0;while(G.xlist[j++].data!=vex2);
		if(i>G.vexnum||j>G.vexnum){
			cout<<"你输入的位置不正确"<//因为相当于是一个邻接表 一个逆邻接表 使用其实是要影响两个
			//这里与上述邻接表类似 使用头插入
			ArcBox* NewArc=(ArcBox*)malloc(sizeof(ArcBox));
			cout<<"请输入此时边对应的权值"<>NewArc->info;
			NewArc->tailvex=i-1;
			NewArc->headvex=j-1;
			NewArc->tlink=G.xlist[i-1].firstout;
			G.xlist[i-1].firstout=NewArc;
			//上面这两句跟之前的邻接表是一样的 下面是逆邻接表的
			NewArc->hlink=G.xlist[j-1].firstin;
			G.xlist[j-1].firstin=NewArc;
		}
	}
	PrintTenList(G);
}
 
打印十字链表 
void PrintTenList(TenListGraph G){
	//遍历每一个顶点的时候都需要两个指针
	for(int i=0;i
		cout<<"邻接表为"<
			cout<"<headvex].data<<" ";
			cur1=cur1->tlink;
		}
		cout<
			cout<tailvex].data<<"->"<hlink;
		}
		cout< 
运行结果 
 
代码汇总(可执行) 
#include
using namespace std;
#define MaxInt 32767  //表示极大值∞  其实就是一种无穷标志
#define MVNum  100    //表示最大顶点数 
typedef char VerTexType;//假设顶点的数据结构类型为char 
typedef int  ArcType;//假设权值类型为整形
//下面的是邻接矩阵的 
typedef struct{
	 VerTexType vexs[MVNum];//顶点表 
	 ArcType  arcs[MVNum][MVNum];//邻接矩阵 
	 int vexnum;//图的当前顶点数
	 int arcnum;//图的当前边数
}AMGraph;

//下面的结构体是邻接表的 
typedef struct ArcNode{//边结构
  int adjvex;//该边所指向的顶点的位置
  struct ArcNode *nextarc;//指向下一条边的指针 
  int info; //和边相关的信息如权重等  若是没有权值也可以省略 省略之后就可以于点结构相统一
}ArcNode; 
typedef struct VNode{//顶点结构
	VerTexType  data;
	ArcNode *firstarc;	//指向第一条依附该顶点的边的指针 
}VNode; 
//相当于多个链表 将首结点存放于一个数组中  就像单链表中存放长度一样 这里存放的是点与边的个数  
typedef struct AdjoinChart{//邻接表 
	VNode vertices[MVNum];//因为顶点中已经存在边的信息了 也就不需要在添加了 
	int vexnum;//图当前的顶点数 
	int arcnum;//图当前的边数 
}AdjoinChart; 

//下面是十字链表的结构体  相当于是一个邻接表 一个逆邻接表的结合 
typedef struct ArcBox{
    int tailvex,headvex;//弧尾、弧头对应顶点在数组中的位置下标
    struct ArcBox *hlink,*tlink;//分别指向弧头相同和弧尾相同的下一个弧
    int info;//存储弧相关信息的指针  这里放的是权重 
}ArcBox;
typedef struct VexNode{
    char data;//顶点的数据域
    ArcBox *firstin,*firstout;//指向以该顶点为弧头和弧尾的链表首个结点
}VexNode;
typedef struct TenListGraph{
    VexNode xlist[MVNum];//存储顶点的一维数组
    int vexnum,arcnum;//记录图的顶点数和弧数
}TenListGraph; 
//打印邻接矩阵 
void PrintAMG(AMGraph G){
	cout<<" "<<" ";
	for(int i=0;i
		cout<
		cout<
			cout<
	cout<<"请输入顶点数和边数"<>G.vexnum>>G.arcnum; 
	cout<<"请输入各个顶点名称"<
		cin>>G.vexs[i]; 
	}
	for(int h=0;h
		char vex1;char vex2;
		cout<<"请输入弧的两个顶点"<>vex1>>vex2; 
		//首先来看是否存在这两个顶点  若是存在则找到这两个点对应的下标
		// 当然创建的时候一种更加简单的方式就是遍历二维数组 一个一个输入
		int i=0;while(G.vexs[i++]!=vex1);
		int j=0;while(G.vexs[j++]!=vex2);
		if(i>G.vexnum||j>G.vexnum){//没有找到 
			cout<<"你输入的结点值不正确"<
			cout<<"请输入此边对应的权重"<>G.arcs[i-1][j-1];
			G.arcs[j-1][i-1]=G.arcs[i-1][j-1];
		}
	}
	PrintAMG(G);
}
//打印邻接表  每打印一个顶点 需要打印出相对应的链表 
void PrintAdjoinChart(AdjoinChart G){
	for(int i=0;i
		ArcNode* cur=G.vertices[i].firstarc;
		while(cur){
			cout<"<adjvex].data<<" ";
			cur=cur->nextarc;
		}
		cout<
	cout<<"请输入顶点数以及边的个数"<>G.vexnum>>G.arcnum;
	cout<<"请输入顶点名称"<
		cin>>G.vertices[i].data;
	}
	//输入一个边有点类似于单链表的插入
	for(int h=0;h
		cout<<"请一个弧的两个边，类如从A指向B则 输入A B"<>vex1>>vex2;
		//依然需要判断输入的结点是否存在;
		int i=0;while(G.vertices[i++].data!=vex1);
		int j=0;while(G.vertices[j++].data!=vex2);
		if(i>G.vexnum||j>G.vexnum){
			cout<<"你输入的位置不正确"<//这里使用头插插入一个弧 
			ArcNode* NewAcr=(ArcNode*)malloc(sizeof(ArcNode));
			NewAcr->nextarc=G.vertices[i-1].firstarc;
			G.vertices[i-1].firstarc=NewAcr;
			cout<<"请输入此边对应的权值"<>NewAcr->info;
			NewAcr->adjvex=j-1;
		}
	}
	PrintAdjoinChart(G);
}
//打印十字链表
void PrintTenList(TenListGraph G){
	//遍历每一个顶点的时候都需要两个指针
	for(int i=0;i
		cout<<"邻接表为"<
			cout<"<headvex].data<<" ";
			cur1=cur1->tlink;
		}
		cout<
			cout<tailvex].data<<"->"<hlink;
		}
		cout<
	cout<<"请输入顶点数以及边的个数"<>G.vexnum>>G.arcnum;
	cout<<"请输入顶点名称"<
		cin>>G.xlist[i].data;
	}
	for(int h=0;h
		cout<<"请一个弧的两个边，类如从A指向B则 输入A B"<>vex1>>vex2;
		//依然需要判断输入的结点是否存在;
		int i=0;while(G.xlist[i++].data!=vex1);
		int j=0;while(G.xlist[j++].data!=vex2);
		if(i>G.vexnum||j>G.vexnum){
			cout<<"你输入的位置不正确"<//因为相当于是一个邻接表 一个逆邻接表 使用其实是要影响两个
			//这里与上述邻接表类似 使用头插入
			ArcBox* NewArc=(ArcBox*)malloc(sizeof(ArcBox));
			cout<<"请输入此时边对应的权值"<>NewArc->info;
			NewArc->tailvex=i-1;
			NewArc->headvex=j-1;
			NewArc->tlink=G.xlist[i-1].firstout;
			G.xlist[i-1].firstout=NewArc;
			//上面这两句跟之前的邻接表是一样的 下面是逆邻接表的
			NewArc->hlink=G.xlist[j-1].firstin;
			G.xlist[j-1].firstin=NewArc;
		}
	}
	PrintTenList(G);
}
void menu(){
	cout<<"1、邻接矩阵 2、邻接表 3、十字链表法"<
	int choice=0;
	cout<<"请输入你要使用何种方式来创建一个表"<>choice;
	switch(choice){
		case 1:{
			AMGraph G;
			CreateAdjoin(G);
			break;
		}
		case 2:{
			AdjoinChart G;
			CreateAdjoinChart(G);
			break;
		}
		case 3:{
			TenListGraph G;
			CreateTenList(G);
			break;
		}
		default:break;
	}
} 
 
感觉不错给作者一个赞哟 这可是凌晨一点半的作者