一、圖的定義和基本術語(Graph)

（一）圖的定義

圖（Graph)是由一個頂點集V和一個邊集E構成的資料結構，
G=(V,E)
V:頂點（資料元素）的又窮非空集合
E:邊的又窮集合
無向圖：每條邊都是沒有方向的
有向圖：每條邊都是有方向的，邊也稱作弧

（二）圖的基本術語

設n表示圖中頂點的數目，e表示邊的數目
完全圖：任意兩個點都有一條邊相連

稀疏圖：如果邊或者弧的個數滿足e<n*log2n,則稱作稀疏圖，否則稱作稠密圖

對無向圖來說：
鄰接點：若頂點v和頂點w之間存在一條邊a,則稱頂點v和w互為鄰接點，邊a與頂點v和w相關聯，
度：與頂點v關聯的邊的數目，記為TD(v)

對有向圖來說：
1、<x,y>為有向邊（弧），x為有向邊的起點（弧尾），y為有向邊的終點（弧頭）
2、頂點v的入度是以v為終點的有向邊的條數，記作ID(v)
3、頂點v的出度是以v為始點的有向邊的條數，記作OD(v)

路徑：連續的邊構成的頂點序列
路徑長度：路徑上邊或者弧的數目
簡單路徑：除路徑起點和終點可以相同外，其余頂點均不相同的路徑
簡單回路（簡單環）：除路徑起點和終點相同外，其余頂點均不相同的路徑，

一、圖的存盤結構

圖的存盤表示特點：
1、圖沒有順序存盤結構，但可以借助二維陣列來表示圖的元素之間的關系
2、以頂點為核心，建立鄰接點和弧的關系；

（一）鄰接矩陣（Adjacency Matrix)

1、考慮到圖是由兩個頂點和邊或弧兩部分組成，合在一起比較困難，可以分為兩個結構來存盤
2、頂點因為不區分大小，主次，所以可以用一個一維陣列來存盤，記錄各個頂點的資訊
3、邊或弧是頂點和頂點的關系，用鄰接矩陣來存盤，表示各個頂點之間的鄰接關系，

1、無向圖的鄰接矩陣

2、有向圖的鄰接矩陣

3、網（即有權圖）的鄰接矩陣

4、鄰接矩陣的存盤表示

/*圖的鄰接矩陣存盤表示法*/
//用兩個陣列分別存盤頂點表和鄰接矩陣
#define MaxInt 32767  //表示極大值，即無窮
#define MVNum 100  //最大頂點數
typedef char VerTexType;  //假設頂點的資料型別為字符型
typedef int ArcType;	//假設邊的權值型別為整型
typedef struct
{
	VerTexType vexs[MVNum];	//頂點表
	ArcType arcs[MVNum][MVNum];	//鄰接矩陣
	int vexnum, arcnum;	//圖的當前頂點數和邊數
}AMGraph;

5、采用鄰接矩陣表示法創建無向網

【演算法步驟】
1、輸入總頂點數和邊數
2、依次輸入點的資訊存入到頂點表中
3、初始化鄰接矩陣，使每個權值初始化為極大值
4、構造鄰接矩陣

注意：
1、無向圖需要為arcs[i][j]和arcs[j][i]賦值
2、有向圖僅需為arcs[i][j]賦值

演算法描述：

/*采用鄰接矩陣表示法創建無向網*/
Status CreateUDN(AMGraph& G)
{
	cin >> G.vexnum >> G.arcnum;//輸入總頂點數和總邊數
	for (int i = 0;i < G.vexnum;++i)
		cin >> G.vexs[i];//依次輸入頂點的資訊
	for (int i = 0;i < G.vexnum;++i)//初始化鄰接矩陣，邊的權值均置為極大值
		for (int j = 0;j < G.vexnum;++j)
			G.arcs[i][j] = MaxInt;
	for (int k = 0;k < G.arcnum;++k)
	{
		cin >> v1 >> v2 >> w;//輸入一條邊依附的頂點和權值
		i = LocateVex(G, v1);j = LocateVex(G, v2);//確定兩個頂點v1和v2在G中的位置
		G.arcs[i][j] = w;//邊<v1,v2>的權值置為w
		G.arcs[j][i] = G.arcs[i][j];//置邊<v1,v2>的對稱點<v2,v1>的權值也為w
	}
	return OK;
}
/*在圖中查找頂點的位置LocateVex()函式*/
int LocateVex(AMGraph G, VertexType u)
{//若在圖中找到這個元素，則回傳它的下標i,否則回傳-1
	int i;
	for (i = 0;i < G.vexnum;++i)
		if (u == G.vexs[i])
			return i;
	return -1;
}

（二）鄰接表（鏈式）表示法(Adjacency List）

是圖的鏈式存盤結構，基本思想就是只存盤圖中存在的邊的資訊，對不相鄰的頂點則不保留資訊
對圖中每個頂點vi建立一個帶頭結點的單鏈表，把與vi相鄰接的頂點放在這個鏈表中，一個單鏈表對應鄰接矩陣中的一行，稱為邊鏈表，

1、無向圖的鄰接表表示

2、有向圖的鄰接表表示

3、圖的鄰接表的存盤定義

分三部分：
1、圖的結構定義
2、頂點的頭結點結構
3、弧（邊）的結點結構

/*圖的鄰接表的存盤定義*/
//弧的結點結構
#define MVNum 100	//最大的頂點數
typedef struct ArcNode
{
	int adjvex;	//該邊所指的頂點的位置
	struct ArcNode* nextarc;	//指向下一條邊的指標
	OtherInfo info;	//和邊相關的資訊
}ArcNode;
//頂點的結點結構
typedef struct VNode
{
	VertexType data;//頂點資訊
	ArcNode* firstarc;//指向第一條依附該頂點的邊
}VNode,AdjList[MVNum];//AdjList表示鄰接表型別
//AdjList v相當于VNode v[MVNum]

//圖的結構定義（鄰接表）
typedef struct
{
	AdjList vertices;//vertices是vertex的復數
	int vexnum, arcnum;//圖的當前頂點數和邊數
}ALGraph;

/*說明*/
ALGraph G;//定義了鄰接表表示的圖G
G.vexnum = 5;G.arcnum = 6;//圖G包含了5個頂點和6條邊
G.vertices[1].data = 'v2';//圖G中第2個頂點是v2
p = G.vertices[1].firstarc;//指標p指向頂點v2的第一個邊結點
p->adjvex = 4;//p指標所指邊結點是到下標為4的結點的邊

4、采用鄰接表表示法創建無向圖

【演算法步驟】
1、輸入總頂點數和總邊數
2、建立頂點表

1、依次輸入點的資訊存入頂點表中
2、使每個表頭結點的指標域初始化為NULL

3、創建鄰接表

1、依次輸入每條邊依附的兩個頂點
2、確定這兩個頂點的序號i和j
3、將此邊結點分別插入vi和vj對應的兩個邊鏈表的頭部

/*采用鄰接表表示法創建無向圖*/
Status CreateUDG(ALGraph& G)
{//采用鄰接表表示法，創建無向圖G
	cin >> G.vexnum >> G.arcnum;//輸入頂點數和弧數
	for (int i = 0;i < G.vexnum;++i)
	{
		cin >> G.vertices[i].data;//輸入頂點值
		G.vertices[i].firstarc = NULL;//初始化表頭結點的指標域為NULL
	}
	for (int k = 0;k < G.arcnum;++k)//輸入各邊，構造鄰接表，頭插法
	{
		cin >> v1 >> v2;//輸入一條邊依附的兩個頂點
		i = LocateVex(G, v1);j = LocateVex(G.v2);
		p1 = new ArcNode;//生成一個新的邊結點*p1
		p1->adjvex = j;//鄰結點序號為j
		p1->nextarc = G.vertices[i].firstarc;//firstarc為空，所以nextarc也指向空，即最后的一個結點
		G.vertices[i].firstarc = p1;//將新結點*p1插入到頂點vi的邊表頭部
		p2 = new ArcNode;//生成一個新的邊結點*p2
		p2->adjvex = i;
		p2->nextarc = G.vertices[j].firstarc;//插入弧結點到單鏈表
		G.vertices[j].firstarc = p2;//將新結點*p2插入到頂點vi的邊表頭部
	}//頭插法
		return OK;
}

5、鄰接矩陣與鄰接表的比較

練習：畫出有向圖G的鄰接矩陣、鄰接表、逆鄰接表

（三）十字鏈表(Orthogonal List)

十字鏈表是有向圖的另一種鏈式存盤結構，可以看成是將有向圖的鄰接表和逆鄰接表結合起來得到的一種鏈表

1、弧結點的結構

Tailvex:指示弧尾結點在圖中的位置
headtex:指示弧頭頂點在圖中的位置
hlink:是指向弧頭相同的下一潭訓的指標
tlink：是指向弧尾相同的下一潭訓的指標
Info:指向該弧的相關資訊

/*弧結點的結構*/
typedef struct ArcBox
{
	int tailvex, headvex;//該弧的尾和頭頂點的位置
	struct ArcBox* hlink, * tlink;//分別為弧頭相同和弧尾相同的弧的指標域
	InfoType* info;//該弧相關資訊的指標
}ArcBox;

2、頂點結點的結構

每個頂點有一個結點，它相當于出邊表和入邊表的表頭結點，資料成員data存放與該頂點的相關資訊，鏈域firstin指示以該頂點為弧頭的第一個弧結點，鏈域firstout指示以該結點為弧尾的第一個弧結點，

/*頂點結點的結構*/
typedef struct VexNode
{
	VertexType data;
	ArcBox* firstin, * firstout;//分別指向該頂點第一條入弧和出弧
}VexNode;
//ArcBox為弧結點變數

3、圖的結構定義

/*圖的結構定義*/
typedef struct
{
	VexNode xlist[MAX_VERTEX_NUM];//表頭向量
	int vexnum, arcnum;//有向圖的當前頂點數和弧數
}OLGraph;

4、實體

5、有向圖G的十字鏈表

（四）鄰接多重表(Adjacent MultiList)

鄰接多重表是無向圖的另一種鏈式存盤結構，由于用鄰接表存盤無向圖時，雖然容易求出頂點和邊的各種資訊，但在鄰接表中每一條邊有兩個結點，分別在第i和j個鏈表中，給圖的某些操作帶來不便，在鄰接多重表中，每一條邊只有一個邊結點，為有關的處理提供了方便，

1、邊結點的結構

mark：為標志域，可用以標記該條邊是否被搜索過
ivex和jvex為該邊依附的兩個頂點在圖中的位置
ilink:指向下一條依附于頂點的ivex的邊
jlink:指向下一條依附于頂點jvex的邊
info:為指向和邊相關的各種資訊個指標域

/*邊結點結構*/
typedef struct EBox
{
	VisitIf mark;//訪問標志域
	int ivex, jvex;//該邊依附的兩個頂點在表頭陣列中的位置
	struct Ebox* ilink, * jlink;//分別指向依附于ivex和jvex的下一條邊
	InfoType* info;
}EBox;

2、頂點結點的結構

/*頂點結點的結構*/
typedef struct VexBox
{
	VertexType data;//存與頂點相關的資訊
	EBox* firstedge;//指向第一條依附于該頂點的邊
}VexBox;

3、圖的結構定義

/*圖的結構定義*/
typedef struct
{
	VexBox adjmulist[MAX_VERTEX_NUM];//表頭向量
	int vexnum, edgenum;//無向圖的當前頂點數和弧數
}OLGraph;
//VexNode為頂點結點變數

4、實體

4、練習：畫出無向圖G的鄰接多重表