一、鄰接矩陣
有向圖的鄰接矩陣：
無向圖的鄰接矩陣：
網的鄰接矩陣：
#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）由于一個邊的兩個端點的次序可随意，是以，每建立一個邊結點，都要按其中的兩個端點的序号，分别将該邊結點鍊入兩個不同的連結清單中