圖（Graph）是一種較線性表和樹更復雜的數(shù)據(jù)結構奏候。在圖形結構中，結點之間的關系可以是任一的，圖中任意兩個數(shù)據(jù)元素之間都可能相關获印。
圖的存儲結構
鄰接矩陣
鄰接矩陣是表示頂點之間相鄰關系的矩陣品山。設G=(V,E)是一個圖胆建，其中V={v1,v2,…,vn} 。G的鄰接矩陣是一個具有下列性質的n階方陣：
- 對無向圖而言肘交，鄰接矩陣一定是對稱的笆载，而且主對角線一定為零（在此僅討論無向簡單圖），副對角線不一定為0，有向圖則不一定如此凉驻。
- 在無向圖中腻要，任一頂點i的度為第i列（或第i行）所有非零元素的個數(shù)，在有向圖中頂點i的出度為第i行所有非零元素的個數(shù)涝登，而入度為第i列所有非零元素的個數(shù)闯第。
- 用鄰接矩陣法表示圖共需要n^2個空間，由于無向圖的鄰接矩陣一定具有對稱關系缀拭，所以扣除對角線為零外咳短，僅需要存儲上三角形或下三角形的數(shù)據(jù)即可，因此僅需要n（n-1）/2個空間蛛淋。
#define INFINITYC 0
#define MAX_VERTEX_NUM 50
typedef int Status;
typedef char VertexType;
typedef int EdgeType;
typedef struct MGraph {
VertexType vexs[MAX_VERTEX_NUM];
EdgeType arc[MAX_VERTEX_NUM][MAX_VERTEX_NUM];
int numNodes, numEdges;
} MGraph;
void CreateMGraph(MGraph *G) {
printf("輸入頂點數(shù)和邊數(shù):\n");
scanf("%d,%d", &G->numNodes, &G->numEdges);
printf("頂點數(shù):%d,邊數(shù):%d\n", G->numNodes, G->numEdges);
int i, j, w;
for (i = 0; i < G->numNodes; i++) {
scanf("%c", &G->vexs[i]);
getchar();
}
for (i = 0; i < G->numNodes; i++) {
for (j = 0; j < G->numNodes; i++) {
G->arc[i][j] = INFINITYC;
}
}
for (int k = 0; k < G->numEdges; k++) {
printf("輸入邊(vi, vj)上的下標i, 下標j, 權w\n");
scanf("%d,%d,%d", &i, &j, &w);
G->arc[i][j] = w;
G->arc[j][i] = G->arc[i][j];
}
for (int i = 0; i < G->numNodes; i++) {
printf("\n");
for (int j = 0; j < G->numNodes; j++) {
printf("%d ",G->arc[i][j]);
}
}
printf("\n");
}
鄰接表
鄰接表（Adjacency List）是圖的一種鏈式存儲結構咙好。在連接表中，對圖中的每個頂點建立一個單鏈表褐荷，第i個單鏈表中的結點表示依附于頂點v1的邊勾效。每個結點由3個域組成，其中鄰接點域（adjvex）指示與頂點v1鄰接的點在圖中的位置叛甫，鏈域（nextarc）指示下一條邊或弧的結點层宫。數(shù)據(jù)域存儲和邊或弧相關的信息。每個鏈表附設一個表頭結點其监。
#define MAX_VERTEX_NUM 50
#define true 1
#define false 0
typedef char Element;
typedef int BOOL;
typedef struct ArcNode {
int adjvex;
Element data;
struct ArcNode *nextArc;
} ArcNode;
typedef struct VNode {
Element data;
ArcNode * firstedge;
} VertexNode, Adjlist[MAX_VERTEX_NUM];
typedef struct ALGraph {
Adjlist adjlist;
int arc_num;
int node_num;
BOOL is_directed;
} ALGraph, *GraphLink;
void CreateGraph(GraphLink *G) {
printf("輸入頂點數(shù)目, 邊數(shù)和方向萌腿？：\n");
scanf("%d %d %d", &(*G)->node_num, &(*G)->arc_num, &(*G)->is_directed);
printf("輸入頂點信息：\n");
int i, j;
for (i = 0; i < (*G)->node_num; i++) {
getchar();
scanf("%c", &(*G)->adjlist[i].data);
(*G)->adjlist[i].firstedge = NULL;
}
ArcNode *p;
printf("輸入邊信息：\n");
for (int k = 0; k < (*G)->arc_num; k++) {
getchar();
scanf("%d %d", &i, &j);
p = (ArcNode *)malloc(sizeof(ArcNode));
p->adjvex = j;
p->nextArc = (*G)->adjlist[i].firstedge;
(*G)->adjlist[i].firstedge = p;
if (!(*G)->is_directed) {
p = (ArcNode *)malloc(sizeof(ArcNode));
p->adjvex = i;
p->nextArc = (*G)->adjlist[j].firstedge;
(*G)->adjlist[j].firstedge = p;
}
}
}
void putGraph(GraphLink G){
printf("鄰接表中存儲信息:\n");
for (int i = 0; i < G->node_num; i++) {
ArcNode *p = G->adjlist[i].firstedge;
while (p) {
printf("%c->%c ", G->adjlist[i].data, G->adjlist[p->adjvex].data);
p = p->nextArc;
}
printf("\n");
}
}
int main(int argc, const char * argv[]) {
// insert code here...
printf("Hello, World!\n");
GraphLink g = (ALGraph *)malloc(sizeof(ALGraph));
CreateGraph(&g);
putGraph(g);
return 0;
}
圖的遍歷
和樹的遍歷類似，從圖中某一個頂點出發(fā)訪遍圖中其余頂點抖苦，且使每一個頂點緊被訪問一次毁菱，這一過程叫圖的遍歷。
深度優(yōu)先搜索
鄰接矩陣深度優(yōu)先搜索
/*
鄰接矩陣深度優(yōu)先搜索
*/
Boolean visited[MAX_VERTEX_NUM];
void DFS(MGraph G, int v) {
visited[v] = TRUE;
printf("%c ", G.vexs[v]);
for (int i = 0; i < G.numNodes; i++) {
if (!visited[i] && G.arc[v][i] == 1) {
DFS(G, i);
}
}
}
void DFSTraverse(MGraph G) {
for (int i = 0; i < G.numNodes; i++) {
visited[i] = FALSE;
}
for (int i = 0; i < G.numNodes; i++) {
if (!visited[i]) {
DFS(G, i);
}
}
printf("\n");
}
鄰接表深度優(yōu)先搜索
/*
鄰接表深度優(yōu)先搜索
*/
BOOL visited[MAX_VERTEX_NUM];
void DFS(ALGraph G, int v) {
visited[v] = true;
printf("%c", G.adjlist[v].data);
ArcNode *p;
p = G.adjlist[v].firstedge;
while (p) {
if (!visited[p->adjvex]) {
DFS(G, p->adjvex);
}
p = p->nextArc;
}
}
void DFSTraverse(ALGraph G) {
for (int i = 0; i < G.node_num; i++) {
visited[i] = false;
}
for (int i = 0; i < G.node_num; i++) {
if (!visited[i]) {
DFS(G, i);
}
}
printf("\n");
}
分析上述算法锌历，在遍歷圖時贮庞，對圖中每個頂點至多調用一次DFS函數(shù)，因為一旦某個頂點被標志成已被訪問究西，就不再從它出發(fā)進行搜索窗慎。因此，遍歷圖的過程實質上是對每個頂點查找其鄰接點的過程卤材。其耗費的時間則取決于所采用的存儲結構遮斥。
- 當用二維數(shù)組表示鄰接矩陣圖的存儲結構時，查找每個頂點的鄰接點所需要的時間為O(n^2),其中n為圖中頂點數(shù)商膊。
- 當用鄰接表作圖的存儲結構時伏伐，找鄰接點所需要的時間為O(e)宠进，其中e為無向圖中邊的數(shù)或有向圖中弧的數(shù)晕拆，因此，當以鄰接表作為存儲結構時，深度優(yōu)化搜索遍歷圖的時間浮渣度為O(n + e)实幕。
廣度優(yōu)先搜索
鄰接矩陣的廣度優(yōu)先搜索
/*
鄰接矩陣廣度優(yōu)先搜索
*/
void BFSTraverse(MGraph G) {
for (int i = 0; i < G.numNodes; i++) {
visited[i] = FALSE;
}
SqQueue Q;
InitQueue(&Q);
for (int i = 0; i < G.numNodes; i++) {
if (!visited[i]) {
visited[i] = TRUE;
printf("%c ", G.vexs[i]);
EnQueue(&Q, i);
while (!QueueEmpty(Q)) {
DeQueue(&Q, &i);
for (int j = 0; j < G.numNodes; j++) {
if (G.arc[i][j] == 1 && !visited[j]) {
visited[j] = TRUE;
printf("%c ", G.vexs[j]);
EnQueue(&Q, j);
}
}
}
}
}
}
鄰接表的廣度優(yōu)先搜索
/*
鄰接表廣度優(yōu)先搜索
*/
void BFSTraverse(ALGraph G) {
for (int i = 0; i < G.node_num; i++) {
visited[i] = FALSE;
}
SqQueue Q;
InitQueue(&Q);
ArcNode *p;
for (int i = 0; i < G.node_num; i++) {
if (!visited[i]) {
visited[i] = TRUE;
printf("%c ", G.adjlist[i].data);
EnQueue(&Q, i);
while (!QueueEmpty(Q)) {
DeQueue(&Q, &i);
p = G.adjlist[i].firstedge;
while (p) {
if (!visited[p->adjvex]) {
visited[p->adjvex] = TRUE;
printf("%c ", G.adjlist[p->adjvex].data);
EnQueue(&Q, p->adjvex);
}
p = p->nextArc;
}
}
}
}
}
分析上述算法吝镣，每個頂點至多進一次隊列。遍歷圖的過程實質上是通過邊和弧找鄰接點的過程昆庇。因此廣度優(yōu)先搜索遍歷圖的時間復雜度和深度優(yōu)先搜索遍歷相同末贾，兩者不同之處僅僅在于對頂點訪問的順序不同。
Demo：https://github.com/ShoukaiWang/DataStructuresAndAlgorithms
