一、邻接矩阵
有向图的邻接矩阵：
无向图的邻接矩阵：
网的邻接矩阵：
#include <iostream>
using namespace std;
#define INFINITY 65535 /* 表示权值的无穷*/
typedef int EdgeType;//边上的权值类型
typedef char VertexType;//顶点类型
const int MaxSize=100;//图中最多顶点个数
class MGraph
{
public:
MGraph(){vertexNum=0;edgeNum=0;}
MGraph(VertexType a[],int n);//构造函数，初始化具有n个顶点的零图
void InsertEdge(int i,int j);//插入顶点为i和j的一条边
int W(int i,int j);//取得边(i,j)上的值(对赋权图)
VertexType vex(int i);//返回顶点i的信息
void CreateMGraph(MGraph *Gp);//建立无向网图的邻接矩阵
public:
int vertexNum,edgeNum;//顶点数和边数
EdgeType adj[MaxSize][MaxSize];//邻接矩阵
VertexType vertex[MaxSize];//顶点表
};
//构造函数，初始化具有n个顶点的零图
MGraph::MGraph(VertexType a[],int n)
{
vertexNum=n;edgeNum=0;
for(int i=0;i<n;i++) vertex[i]=a[i];
for(int i=0;i<n;i++)
for(int j=0;j<n;j++)
adj[i][j]=0;
}
//插入顶点为i和j的一条边
void MGraph::InsertEdge(int i,int j)
{
if(i<0||i>=vertexNum||j<0||j>=vertexNum)
throw "位置出错";
adj[i][j]=1;//顶点i到顶点j的边存在
edgeNum++;//边数目加1
}
//取得边(i,j)上的值(对赋权图)
int MGraph::W(int i,int j)
{//对非赋权图，则取得邻接矩阵上的邻接信息，1表示邻接，0表示不邻接
if(i<0||i>=vertexNum||j<0||j>=vertexNum)
throw "位置出错";
return adj[i][j];
}
//返回顶点i的信息
VertexType MGraph::vex(int i)
{
if(i>=0&&i<vertexNum)
return vertex[i];//返回顶点i
else throw "位置出错";
}
/* 建立无向网图的邻接矩阵表示 */
void MGraph::CreateMGraph(MGraph *Gp)
{
int i, j, k, w;
cout << "请输入顶点数和边数（空格分隔）：" << endl;
cin >> Gp->vertexNum >> Gp->edgeNum;
cout << "请输入顶点信息（空格分隔）：" << endl;
for (i = 0; i < Gp->vertexNum; i++)
cin >> Gp->vertex[i];
for (i = 0; i < Gp->vertexNum; i++)
{
for (j = 0; j < Gp->vertexNum; j++)
{
if (i == j)
Gp->adj[i][j] = 0;/* 顶点没有到自己的边*/
else
Gp->adj[i][j] = INFINITY;/* 邻接矩阵初始化 */
}
}
for (k = 0; k < Gp->edgeNum; k++)
{
cout << "请输入边（vi, vj)的上标i，下标j和权值w（空格分隔）:" << endl;
cin >> i >> j >> w;
Gp->adj[i][j] = w;
Gp->adj[j][i] = Gp->adj[i][j];/* 因为是无向图，矩阵对称 */
}
}
int main()
{
MGraph grph;
grph.CreateMGraph(&grph);
for(int i=0;i<grph.vertexNum;i++)
{
for(int j=0;j<grph.vertexNum;j++)
{cout<<grph.adj[i][j];cout.width(7);}
cout<<endl;
}
return 0;
}
二、边数组
用一个包括两个端点及其上的权值的三元组(vi,vj,wij)来表示图中的一条边或弧，图的所有边火狐构成的这种三元组的集合都称为图的边集表示。
边集数组由两个一维数组构成：
1.） 一个存储顶点信息。
2.） 一个存储边的信息，这个边数组每个数据元素由一条边的起点下标（begin）、终点下标（end）、和权（weight）组成。
边集数组关注的是边的集合，在边集数组中要查找一个顶点的度需要扫描整个边数组，效率并不高。因此它更适合对边依次进行处理的操作，而不适合对顶点相关的操作。
三、邻接表
1、无向图的邻接表
边表结点：
邻接点域 链域
| adjvex | next |
表头结点：
顶点信息域 始结点针织域
| vertex | firstedge |
#include <iostream>
using namespace std;
typedef char VertexType;//顶点类型
const int MaxSize=100;
//边表结点结构
struct EdgeNode
{
int adjvex;//邻接点域
EdgeNode *next;//指向下一个边结点的指针
};
//表头结点结构
struct VexNode
{
int vertex;//顶点
EdgeNode *firstedge;//边表的头指针
};
class ALGraph
{
public:
ALGraph()//无参构造函数
{
vertexNum=0;
edgeNum=0;
for(int i=0;i<MaxSize;i++)
adjlist[i].firstedge=NULL;
}
ALGraph(VertexType a[],int n);//有参构造函数
private:
VexNode adjlist[MaxSize];//存放顶点表的数组
int vertexNum,edgeNum;//图的顶点数和边数
};
//有参构造函数
ALGraph::ALGraph(VertexType a[],int n)
{
vertexNum=n;
edgeNum=0;
for(int i=0;i<vertexNum;i++)
{
adjlist[i].vertex=a[i];
adjlist[i].firstedge=NULL;
}
}
2、有向图的邻接表
表结点（出弧结点）：
| adjvex | next |
adjvex存放弧头结点的在顶点数组中的位置（一般用下标表示），next指向下一表结点的指针域。
表头结点：
| vertex | firstarc |
vertex存放顶点，firstarc存放指向由出弧结点构成的链表的开始结点的指针（头指针）
计算一个顶点的出度时，只需顺着该顶点结点的指针域遍历一下其所指向的单链表，计算下该链表上的结点数。
//表结点结构
struct ArcNode
{
int adjvex;//邻接点域
ArcNode *next;//指向下一个边结点的指针
};
//表头结点结构
struct VexNode
{
int vertex;//顶点
ArcNode *firstarc;//指向第一个结点的指针，即出弧表的头指针
};
3、有向图的逆邻接表
四、十字链表 1、弧结点
| tailvex | headvex | hlink | tlink |
i----->j
tailvex：存放i，表示i为该弧引出，i为弧尾； headvex：存放j，表示该弧进入j，j为弧头； hlink：指向下一条进入顶点j的弧的弧结点； tlink：指向下一条从i引出的弧的弧结点；
struct ArcNode//弧结点结构
{
int tailvex,headvex;
ArcNode *hlink,*tlink;
};
2、顶点结点
| data | firstin | firstout |
data：存储和顶点相关的信息 firstin：指向以该顶点为弧头的第一个弧结点的指针 firstout：指向以该顶点为弧尾的第一个弧结点的指针
struct VexNode
{
int data;
ArcNode *firstin,*firstout;
};
五、邻接多重表 针对无向图的链式存储结构。 边结点结构：
| mark | ivex | ilink | jvex | jlink | info |
mark：标志域，标记该边是否被搜多过，0未被访问，1已被访问 ivex，jvex：该边依附的两个顶点在图中的位置 ilink：指向下一条依附于顶点ivex的边 jlink：指向下一条依附于顶点jvex的边 info：边上的信息或指向与边相关的信息数据的指针域
顶点结点结构：
| vertex | firstedge |
vertex：存储和该顶点相关的信息 firstedge：指示第一条依附于该顶点的边
邻接多重表建立方法： （1）一条边对应建立一个边结点 （2）由于一个边的两个端点的次序可随意，因此，每建立一个边结点，都要按其中的两个端点的序号，分别将该边结点链入两个不同的链表中