# 一、綜述
圖的表示方法通常有兩種，即鄰接表表示法和鄰接矩陣表示法。這兩種方法都可以表示有向圖和無向圖
### 1.鄰接表表示法
（1）用鄰接表表示無向圖
（2）用鄰接表表示有向圖
（3）鄰接表的優點及適用場合
使用鄰接表表示稀疏圖比較緊湊
### 2.鄰接矩陣表示法
（1）用鄰接矩陣表示無向圖
（2）用鄰接矩陣表示有向圖
（3）鄰接矩陣的優點與適用場合
用鄰接矩陣表示稠密圖可以很快地判別兩個給定頂點是否存在鄰接邊
# 二、代碼
### 1.鄰接表表示法 "Link_Graph.h"
~~~
#include <iostream>
using namespace std;
#define N 100
struct Vertex;
struct Edge
{
int start;
int end;
int value;
Edge *next;
Edge(int s, int e, int v):start(s),end(e),value(v),next(NULL){}
};
struct Vertex
{
Edge *head;
Vertex():head(NULL){};
};
class Link_Graph
{
public:
int n;
Vertex *V;
Link_Graph(int num):n(num)
{
V = new Vertex[n+1];
}
~Link_Graph(){delete []V;}
void AddSingleEdge(int start, int end, int value = 1)
{
Edge *NewEdge = new Edge(start, end, value);
if(V[start].head == NULL || V[start].head->end > end)
{
NewEdge->next = V[start].head;
V[start].head = NewEdge;
}
else
{
Edge *e = V[start].head, *pre = e;
while(e != NULL && e->end < end)
{
pre = e;
e = e->next;
}
if(e && e->end == end)
{
delete NewEdge;
return;
}
NewEdge->next = e;
pre->next = NewEdge;
}
}
void AddDoubleEdge(int a, int b, int value = 1)
{
AddSingleEdge(a, b, value);
AddSingleEdge(b, a, value);
}
void DeleteSingleEdge(int start, int end)
{
Edge *e = V[start].head, *pre = e;
while(e && e->end < end)
{
pre = e;
e = e->next;
}
if(e == NULL || e->end > end) return;
if(e == V[start].head)
V[start].head = e->next;
else
pre->next = e->next;
delete e;
}
void DeleteDoubleEdge(int a, int b)
{
DeleteSingleEdge(a, b);
DeleteSingleEdge(b, a);
}
//22.1-1
void OutDegree();
void InDegree();
//22.1-2
void Print();
//22.1-3
Link_Graph* Reverse();
//22.1-5
Link_Graph* Square();
};
void Link_Graph::OutDegree()
{
int i, cnt = 0;
Edge *e;
for(i = 1; i <= n; i++)
{
cnt = 0;
e = V[i].head;
while(e)
{
cnt++;
e = e->next;
}
cout<<"頂點"<<i<<"的出度為"<<cnt<<endl;
}
}
void Link_Graph::InDegree()
{
int ret[N+1] = {0}, i;
Edge *e;
for(i = 1; i <= n; i++)
{
e = V[i].head;
while(e)
{
ret[e->end]++;
e = e->next;
}
}
for(i = 1; i <= n; i++)
cout<<"頂點"<<i<<"的入度為"<<ret[i]<<endl;
}
void Link_Graph::Print()
{
int i;
Edge *e;
for(i = 1; i <= n; i++)
{
cout<<i;
e = V[i].head;
while(e)
{
cout<<"->"<<e->end;
e = e->next;
}
cout<<endl;
}
}
Link_Graph* Link_Graph::Reverse()
{
Link_Graph *ret = new Link_Graph(n);
int i;
//遍歷圖G中的每一條邊，以終點為起點，以起點為終點，加入到新圖RET中
for(i = 1; i <= n; i++)
{
Edge *e = V[i].head;
while(e)
{
ret->AddSingleEdge(e->end, e->start);
e = e->next;
}
}
return ret;
}
Link_Graph* Link_Graph::Square()
{
int i;
Link_Graph *ret = new Link_Graph(n);
//遍歷圖中每個頂點
for(i = 1; i <= n; i++)
{
//遍歷以該頂點為起點的邊
Edge *e = V[i].head, *e2;
while(e)
{
//把原來有的邊加入到新圖中
ret->AddSingleEdge(e->start, e->end);
//把以E的終點為起點的邊加入新圖中
e2 = V[e->end].head;
while(e2)
{
ret->AddSingleEdge(e->start, e2->end);
e2 = e2->next;
}
e = e->next;
}
}
return ret;
}
~~~
### 2.鄰接矩陣表示法
~~~
#include <iostream>
using namespace std;
#define N 100
class Mat_Graph
{
public:
int n;
int Map[N+1][N+1];
Mat_Graph(int num):n(num)
{
memset(Map, 0, sizeof(Map));
}
void AddDoubleEdge(int a, int b, int value = 1)
{
AddSingleEdge(a, b, value);
AddSingleEdge(b, a, value);
}
void AddSingleEdge(int start, int end, int value = 1)
{
Map[start][end] = value;
}
void DeleteDoubleEdge(int a, int b)
{
DeleteSingleEdge(a, b);
DeleteSingleEdge(b, a);
}
void DeleteSingleEdge(int start, int end)
{
Map[start][end] = 0;
}
//22.1-2
void Print();
//22.1-3
Mat_Graph* Reverse();
//22.1-5
Mat_Graph* Square();
//22.1-6
bool Universal_Sink();
};
void Mat_Graph::Print()
{
int i, j;
for(i = 1; i <= n; i++)
{
for(j = 1; j <= n; j++)
cout<<Map[i][j]<<' ';
cout<<endl;
}
}
Mat_Graph* Mat_Graph::Reverse()
{
int i, j;
Mat_Graph *ret = new Mat_Graph(n);
for(i = 1; i <= n; i++)
{
for(j = 1; j <= n; j++)
if(Map[i][j])
ret->AddSingleEdge(j, i);
}
return ret;
}
Mat_Graph* Mat_Graph::Square()
{
int i, j, k;
Mat_Graph *ret = new Mat_Graph(n);
//遍歷圖中每個頂點
for(i = 1; i <= n; i++)
{
for(j = 1; j <= n; j++)
{
if(Map[i][j])
{
//把原來有的邊加入到新圖中
ret->AddSingleEdge(i, j);
//把以E的終點為起點的邊加入新圖中
for(k = 1; k <= n; k++)
if(Map[j][k])
ret->AddSingleEdge(i, k);
}
}
}
return ret;
}
bool Mat_Graph::Universal_Sink()
{
//i指向有可能是匯的編號最小的點
int i = 1, j = 1;
while(j <= n)
{
//map[i][j] = 0,那么j沒有i的入，一定不是匯，i可能是匯
if(Map[i][j] == 0)
j++;
//若map[i][j] = 1，則(1)i有出，i不是匯(2)map[i][i+1..j-1]=0，i+1..j-1都不是匯(3)j及j以后的點可能是匯
//若i=j，j也不是匯，j+1可能是匯
else if(i == j)
{
i++;
j++;
}
//若i!=j，j以前的點都不是匯，j可能是匯
else i = j;
}
//沒有匯
if(i > n)
return false;
//找到有可能是匯的點，但是還是需要驗證一下
else
{
//匯的縱向都是1，除了map[i][i]
for(j = 1; j <= i-1; j++)
{
if(Map[i][j] == 1)
return false;
}
//匯的橫向都是0
for(j = 1; j <= n; j++)
if( i != j && Map[j][i] == 0)
return false;
return true;
}
}
~~~
###
3.main.cpp?
~~~
#include <iostream>
using namespace std;
#include "Link_Graph.h"
#include "Mat_Graph.h"
void Test1()
{
cout<<"Test1"<<endl;
int n, a, b;
cin>>n;
Link_Graph *LG = new Link_Graph(n);
while(cin>>a>>b && a && b)//輸入00時結束
LG->AddSingleEdge(a, b);
LG->OutDegree();
LG->InDegree();
delete LG;
}
void Test2()
{
cout<<"Test2"<<endl;
Link_Graph *LG = new Link_Graph(6);
Mat_Graph *MG = new Mat_Graph(6);
int edge[6][2] = {{1,2},{1,3},{2,4},{2,5},{3,6},{3,6}};
int i = 0;
for(i = 0; i < 6; i++)
{
LG->AddSingleEdge(edge[i][0], edge[i][1]);
MG->AddSingleEdge(edge[i][0], edge[i][1]);
}
LG->Print();
MG->Print();
delete LG;
delete MG;
}
void Test3()
{
cout<<"Test3"<<endl;
int n, a, b;
cin>>n;
Link_Graph *LG = new Link_Graph(n);
Mat_Graph *MG = new Mat_Graph(n);
while(cin>>a>>b && a && b)//輸入00時結束
{
LG->AddSingleEdge(a, b);
MG->AddSingleEdge(a, b);
}
Link_Graph *NewLG = LG->Reverse();
NewLG->Print();
Mat_Graph *NewMG = MG->Reverse();
NewMG->Print();
delete LG;
delete MG;
delete NewLG;
delete NewMG;
}
void Test5()
{
cout<<"Test5"<<endl;
int n, a, b;
cin>>n;
Link_Graph *LG = new Link_Graph(n);
Mat_Graph *MG = new Mat_Graph(n);
while(cin>>a>>b && a && b)//輸入00時結束
{
LG->AddSingleEdge(a, b);
MG->AddSingleEdge(a, b);
}
Link_Graph *NewLG = LG->Square();
NewLG->Print();
Mat_Graph *NewMG = MG->Square();
NewMG->Print();
delete LG;
delete MG;
delete NewLG;
delete NewMG;
}
void Test6()
{
cout<<"Test6"<<endl;
int n, a, b;
cin>>n;
Mat_Graph *MG = new Mat_Graph(n);
while(cin>>a>>b && a && b)//輸入00時結束
MG->AddSingleEdge(a, b);
if(MG->Universal_Sink())
cout<<"包含通用的匯"<<endl;
else
cout<<"不包含通用的匯"<<endl;
delete MG;
}
/*
6
1 2
1 4
4 2
2 5
5 4
3 5
3 6
6 6
0 0
*/
int main()
{
Test1();
Test2();
Test3();
Test5();
Test6();
return 0;
}
~~~
# 三、練習
22.1-1
計算出度的時間：E
計算入度的時間：E
~~~
void Test1()
{
cout<<"Test1"<<endl;
int n, a, b;
cin>>n;
Link_Graph *LG = new Link_Graph(n);
while(cin>>a>>b && a && b)//輸入00時結束
LG->AddSingleEdge(a, b);
LG->OutDegree();
LG->InDegree();
delete LG;
}
~~~
22.1-2
~~~
void Test2()
{
cout<<"Test2"<<endl;
Link_Graph *LG = new Link_Graph(6);
Mat_Graph *MG = new Mat_Graph(6);
int edge[6][2] = {{1,2},{1,3},{2,4},{2,5},{3,6},{3,6}};
int i = 0;
for(i = 0; i < 6; i++)
{
LG->AddSingleEdge(edge[i][0], edge[i][1]);
MG->AddSingleEdge(edge[i][0], edge[i][1]);
}
LG->Print();
MG->Print();
delete LG;
delete MG;
}
~~~
鄰接表表示：
1->2->3
2->4->5
3->6->7
4
5
6
7
矩陣表示：
0110000
0001100
0000011
0000000
0000000
0000000
0000000
22.1-3
鄰接表表示的有向圖的轉置
~~~
Link_Graph* Link_Graph::Reverse()
{
Link_Graph *ret = new Link_Graph(n);
int i;
//遍歷圖G中的每一條邊，以終點為起點，以起點為終點，加入到新圖RET中
for(i = 1; i <= n; i++)
{
Edge *e = V[i].head;
while(e)
{
ret->AddSingleEdge(e->end, e->start);
e = e->next;
}
}
return ret;
}
~~~
鄰接矩陣表示的有向圖的轉置?
~~~
Mat_Graph* Mat_Graph::Reverse()
{
int i, j;
Mat_Graph *ret = new Mat_Graph(n);
for(i = 1; i <= n; i++)
{
for(j = 1; j <= n; j++)
if(Map[i][j])
ret->AddSingleEdge(j, i);
}
return ret;
}
~~~
22.1-4
遍歷多重圖中的每一條邊，通過AddDoubleAdge()函數把它加入到另一個圖中
22.1-5
鄰接表表示的有向圖的平方圖
~~~
Link_Graph* Link_Graph::Square()
{
int i;
Link_Graph *ret = new Link_Graph(n);
//遍歷圖中每個頂點
for(i = 1; i <= n; i++)
{
//遍歷以該頂點為起點的邊
Edge *e = V[i].head, *e2;
while(e)
{
//把原來有的邊加入到新圖中
ret->AddSingleEdge(e->start, e->end);
//把以E的終點為起點的邊加入新圖中
e2 = V[e->end].head;
while(e2)
{
ret->AddSingleEdge(e->start, e2->end);
e2 = e2->next;
}
e = e->next;
}
}
return ret;
}
~~~
鄰接矩陣表示的有向圖的平方圖
~~~
Mat_Graph* Mat_Graph::Square()
{
int i, j, k;
Mat_Graph *ret = new Mat_Graph(n);
//遍歷圖中每個頂點
for(i = 1; i <= n; i++)
{
for(j = 1; j <= n; j++)
{
if(Map[i][j])
{
//把原來有的邊加入到新圖中
ret->AddSingleEdge(i, j);
//把以E的終點為起點的邊加入新圖中
for(k = 1; k <= n; k++)
if(Map[j][k])
ret->AddSingleEdge(i, k);
}
}
}
return ret;
}
~~~
22.1-6
如果A[i, j] = 1，即(i, j)∈E（1≤i≤|V|，1≤j≤|V|，E是G的邊集），那么頂點i就不可能是通用匯點，因為它有一條出邊。
現在假設A[i, j] = 0，即(i, j)?E，且i≠j。在這種情況下，頂點j就不可能是通用匯點，因為它的入度小于|V|-1
因此，這個問題等價于：給定一個有向圖Ｇ的|V|×|V|鄰接矩陣A，在O(|V|)時間內判斷是否存在一個整數j（1≤j≤|V|），使得對于所有的i（1≤i≤|V|且i≠j）都有A[i, j] = 1，對于所有的k（1≤k≤|V|）都有A[j, k] = 0。更形象地說，就是判斷A里面是否有這樣一個“十”字：這“十”字的橫全是0，豎全是1（除了“十”字的中心）。
~~~
bool Mat_Graph::Universal_Sink()
{
//i指向有可能是匯的編號最小的點
int i = 1, j = 1;
while(j <= n)
{
//map[i][j] = 0,那么j沒有i的入，一定不是匯，i可能是匯
if(Map[i][j] == 0)
j++;
//若map[i][j] = 1，則(1)i有出，i不是匯(2)map[i][i+1..j-1]=0，i+1..j-1都不是匯(3)j及j以后的點可能是匯
//若i=j，j也不是匯，j+1可能是匯
else if(i == j)
{
i++;
j++;
}
//若i!=j，j以前的點都不是匯，j可能是匯
else i = j;
}
//沒有匯
if(i > n)
return false;
//找到有可能是匯的點，但是還是需要驗證一下
else
{
//匯的縱向都是1，除了map[i][i]
for(j = 1; j <= i-1; j++)
{
if(Map[i][j] == 1)
return false;
}
//匯的橫向都是0
for(j = 1; j <= n; j++)
if( i != j && Map[j][i] == 0)
return false;
return true;
}
}
~~~
22.1-7
B = -BT
BBT = -B2
22.1-8
類似于鄰接表與鄰接矩陣的折中策略
- 前言
- 第6章 堆排序
- 6-3 Young氏矩陣
- 第7章 快速排序
- 第8章 線性時間排序
- 第9章 排序和順序統計學算法導論
- 算法導論 9.1-1 求第二小元素
- 第10章 10.1 棧和隊列
- 第10章 10.2 鏈表
- 第10章 10.3 指針和對象實現
- 第10章 10.4 有根樹的表示
- 第11章-散列表
- 第12章 二叉查找樹
- 第13章 紅黑樹
- 第14章 14.1 動態順序統計
- 算法導論-14-1-最大重疊點
- 算法導論-14-2-Josephus排列
- 第14章 14.3 區間樹
- 第15章 動態規劃
- 第16章 貪心算法
- 第18章 B樹
- 第19章-二項堆
- 第20章 斐波那契堆
- 第21章 用于不相交集合的數據結構
- 第22章 圖的基本算法 22.1 圖的表示
- 第22章 圖算法 22.2 廣度優先搜索
- 第22章 圖算法 22.3 深度優先搜索
- 第22章 圖的基本算法 22.4 拓撲排序
- 第22章 圖的基本算法 22.5 強聯通分支