今天给大家介绍一种比较复杂的数据类型，也是最近我一直研究的数据类型，它就是图。
图的应用非常广泛，物理学、生物学、社会学和信息科学中可以使用图结构来建立研究模型，用来刻画客观的世界。比如在计算机科学中，图可以用来表示网络的通讯：网站的链接结构可以用有向图来表示，顶点代表网页，边代表链接关系。在社会学中，kevinbacon的“六度分隔理论”或者谣言传播理论的研究都可以使用图结构来建立模型。在我们常用的电子地图中，最常用的导航就是利用的图的结构，来规划路径、搜索道路等。
闲话少叙，让我们进入正题吧！
图是一种多对多的抽象数据类型，它由有限个顶点和有限条边组成。
顶点：是图的数据点，如u、v，w，y点等。
边：是数据点的关系，如（u，v）、（v，u）等。
有向图
在有向图中（u，v）和（v，u）是两个不同的边，这里我们称为弧，并且要使用尖括号。比如u,v是表示顶点u指向顶点v的弧，v,u是表示顶点v指向顶点u的弧。并且第一个顶点我们称为弧尾，第二个顶点称为弧头，弧的关系是由弧尾指向弧头。
无向图
在无向图中，（u，v）和（v，u）是相同的边，表示u和v之间连通。注意是”连通“，不是移动手机的那个联通。
图的一般表示方法有邻接矩阵、邻接链表。（另外还有一些表示方法，这里介绍最简单，最常用的表示方法。）
邻接矩阵：
邻接矩阵表示
邻接矩阵是一个二维V*V的矩阵（V是顶点个数），矩阵中一点M[u][v]的值，表示顶点u和顶点v的关系，等于1说明u和v有边，则u和v是连通的；等于0说明u和v没有边连接，则u和v不连通。另外M[u][v]的值可以用来表示权重，表示从顶点u到达顶点v所需要花费的代价。例如u和v表示两个城市，矩阵M表示城市里程图，若M[u][v]=d，则表示城市u和城市v的距离是d。
优点：邻接矩阵表示图的方法，简单、易于理解。查询、添加、删除、修改两顶点x和y的边，只需要O(1)复杂度。
缺点：需要耗费V*V个空间，即使多数点之间没有边，需要的空间还是V*V，很多的位置用来存放0。另外，若增加一个顶点x进入图中，则复杂度为O(V*V)。
邻接链表：
邻接链表
使用链表数组Array[V]来表示顶点的关系，数组的大小为V。每一个数组成员都是一个链表，表示该顶点在图中的连接情况。
Array[i]表示顶点i邻接边的连接关系，如上图，Array[0]表示顶点0与顶点1、顶点4都有边。Array[4]表示顶点4与顶点3、顶点0和顶点1都有边。
代码部分：
1.邻接矩阵
//C/C++代码演示邻接矩阵
#includeiostream
usingnamespacestd;
//顶点类
classNode
{
public:
Node(chardata=0){
m_cdata=data;
}
charm_cdata;
};
//图类
classmMap
{
public:
mMap(intnumber){
m_iNum=number;
m_iIndex=0;
m_pNodeArray=newNode[m_iNum];
m_pMatrix=newint[m_iNum*m_iNum];
for(inti=0;im_iNum*m_iNum;i++)m_pMatrix[i]=0;
}
~mMap(){
delete[]m_pMatrix;
delete[]m_pNodeArray;
};
//添加顶点
booladdNode(Node*pNode){
if(pNode==NULL)returnfalse;
m_pNodeArray[m_iIndex].m_cdata=pNode-m_cdata;
m_iIndex++;
returntrue;
}
//添加无向图的边
booladdudtEdge(introw,intcol,intweight=1){
if(row0
col0
rowm_iNum
colm_iNum)returnfalse;
m_pMatrix[row*m_iNum+col]=weight;
m_pMatrix[col*m_iNum+row]=weight;
returntrue;
}
//添加有向图的边
booladddtEdge(introw,intcol,intweight=1){
if(row0
col0
rowm_iNum
colm_iNum)returnfalse;
m_pMatrix[row*m_iNum+col]=weight;
returntrue;
}
//打印图
voidprint(){
for(inti=0;im_iNum;i++){
for(intj=0;jm_iNum;j++)
coutm_pMatrix[i*m_iNum+j]"";
coutendl;
}
}
private:
intm_iNum;//顶点个数
intm_iIndex;//顶点索引
Node*m_pNodeArray;//顶点数组指针
int*m_pMatrix;//邻接矩阵
};
intmain(){
intnum=8;
mMapmap(num);
char*name="ABCDEFGH";
for(inti=0;inum;i++){
NodetempNode(name[i]);
map.addNode(tempNode);
chartemp=0;
}
coutendl;
map.addudtEdge(0,1);
map.addudtEdge(0,3);
map.addudtEdge(1,2);
map.addudtEdge(1,5);
map.addudtEdge(3,6);
map.addudtEdge(3,7);
map.addudtEdge(6,7);
map.addudtEdge(4,5);
map.print();
return0;
}
输出结果：
2.邻接链表
//C/C++代码演示邻接链表
#includestdio.h
#includestdlib.h
//顶点结构体
structAdjListNode{
intdest;
structAdjListNode*next;
};
//顶点连接关系结构体
structAdjList
{
structAdjListNode*head;//pointertoheadnodeoflist
};
//图
structGraph
{
intv;//sizeofarraywillbeV(numberofverticesingraph)
structAdjList*array;
//AdjListpointerisaarrayofAdjLists
};
//创建一个顶点
structAdjListNode*newAdjListNode(intdest)
{
structAdjListNode*newNode=(structAdjListNode*)malloc(sizeof(structAdjListNode));
newNode-dest=dest;
newNode-next=NULL;
returnnewNode;
}
//创建有V个顶点的图
structGraph*createGraph(intv)
{
structGraph*graph=(structGraph*)malloc(sizeof(structGraph));
graph-v=v;
//createaarrayofadjacencylist,sizeofarraywillbeV;
graph-array=(structAdjList*)malloc(v*sizeof(structAdjList));
//initializeeachadjlistasemptybymakingheadisNULL;
inti;
for(i=0;iv;i++){
graph-array[i].head=NULL;
}
returngraph;
};
//向无向图中添加一条边
voidaddEdge(structGraph*graph,intsrc,intdest){
//addanedgeformsrctodest
//anewnodeisaddedtotheAdjListofsrc.
structAdjListNode*newNode=newAdjListNode(dest);
//wewillmakethenewNodepointtotheNodethatheadpointerpointedfirstly;
newNode-next=graph-array[src].head;
//andlettheheadpointtothenewNodesecondary
graph-array[src].head=newNode;
//UDTalsoneedanedgeformdesttosrc;
newNode=newAdjListNode(src);
newNode-next=graph-array[dest].head;
graph-array[dest].head=newNode;
}
//打印图关系
voidprintGraph(structGraph*graph){
intv;
for(v=0;vgraph-v;++v){
structAdjListNode*pCrawl=graph-array[v].head;
printf("\nAdjListofvertex%d\nhead",v);
while(pCrawl)
{
printf("-%d",pCrawl-dest);
pCrawl=pCrawl-next;
}
printf("\n");
}
}
intmain(){
intv=5;
structGraph*graph=createGraph(v);
addEdge(graph,0,1);
addEdge(graph,0,4);
addEdge(graph,1,2);
addEdge(graph,1,3);
addEdge(graph,1,4);
addEdge(graph,2,3);
addEdge(graph,3,4);
printGraph(graph);
return0;
}
输出结果：
谢谢观看！欢迎在评论区交流学习！