網(wǎng)站首頁(yè) 編程語(yǔ)言 正文
文章目錄
- 一、圖的介紹
- 二、圖的定義和術(shù)語(yǔ)
- 三、圖的存儲(chǔ)結(jié)構(gòu)：
- 鄰接矩陣：
- 鄰接矩陣的優(yōu)點(diǎn)：
- 鄰接矩陣的缺點(diǎn)：
- 鄰接表：
- 鄰接表優(yōu)點(diǎn)：
- 鄰接表缺點(diǎn)：
- 十字鏈表：
- 十字鏈表的優(yōu)點(diǎn)：
- 十字鏈表的缺點(diǎn)：
- 鄰接多重表：
一、圖的介紹
? 圖是一種比較復(fù)雜的數(shù)據(jù)結(jié)構(gòu)，在線性表中數(shù)據(jù)元素之間僅有線性關(guān)系，每個(gè)元素只有一個(gè)直接前驅(qū)和直接后繼（元素之間只存在一對(duì)一關(guān)系），在樹(shù)形結(jié)構(gòu)中元素之間有著明顯的層次關(guān)系，每一層的元素只能和下層的多個(gè)元素有關(guān)系（元素之間存在一對(duì)多關(guān)系），而在圖形結(jié)構(gòu)中，任意兩個(gè)結(jié)點(diǎn)之間都可能有關(guān)系（元素之間存在多對(duì)多關(guān)系）。
二、圖的定義和術(shù)語(yǔ)
**頂點(diǎn)：**圖中的數(shù)據(jù)元素被稱(chēng)為頂點(diǎn)，一般使用V表示圖的頂點(diǎn)的有窮非空集合。
**弧：**兩個(gè)頂點(diǎn)之間的關(guān)系記作<v，w>，表示能從頂點(diǎn)v到達(dá)頂點(diǎn)w，也就是v能到w，但w不一定能到v，我們稱(chēng)v為弧尾或初始點(diǎn)，稱(chēng)w為弧頭或終端點(diǎn)。
**有向圖：**由弧+頂點(diǎn)構(gòu)成的圖叫有向圖，也就是頂點(diǎn)之間是單行道。
**邊：**兩個(gè)頂點(diǎn)之間的關(guān)系記錄（v，w），表示既能從v到w，也能從w到v，我們稱(chēng)v和w之間的關(guān)系是一條邊。
**無(wú)向圖：**由邊+頂構(gòu)成的圖有無(wú)向圖，頂點(diǎn)之間的雙行道。
**注意：**一般使用G代表圖，V頂點(diǎn)的集合，VR代表弧或邊的集合，n代表頂點(diǎn)的數(shù)目，e代表邊或弧的數(shù)目，我們不討論頂點(diǎn)到自己的邊或弧。
**完全圖：**在無(wú)向圖中，e的取值范圍是0 ~ n/2(n-1)，如果無(wú)向圖的邊的數(shù)量達(dá)到最大值這種無(wú)向圖稱(chēng)稱(chēng)為完全圖。
**有向完全圖：**在有向圖中，e的取值范圍是0 ~ n(n-1)，如果有向圖的弧的數(shù)量達(dá)到最大值這種有向圖稱(chēng)稱(chēng)為有向完全圖。
**稀疏圖和稠密圖：**如果圖中的邊和弧很少，e<nlogn 這種圖被稱(chēng)為稀疏圖，反之稱(chēng)為稠密圖。
**權(quán)和網(wǎng)：**如果圖中的頂點(diǎn)到另一個(gè)頂點(diǎn)需要代價(jià)（距離或耗費(fèi)），那么在表示邊或弧的時(shí)候需要附加數(shù)據(jù)，附加的數(shù)據(jù)就叫做權(quán)，帶權(quán)的圖通常被稱(chēng)為網(wǎng)，這也是互聯(lián)網(wǎng)的由來(lái)。
**子圖：**假定有兩個(gè)圖G1和G2，如果G1的頂點(diǎn)集合是G2的頂點(diǎn)集合的子集，且G1的邊或弧集合是G2的邊或弧集合的子集，則稱(chēng)G1是G2的子圖。
**鄰接點(diǎn)：**在無(wú)向圖中如果有一條邊（v，w），則v，w兩個(gè)頂點(diǎn)互為鄰接點(diǎn)，即v和w相鄰接，邊（v，w）依附于頂點(diǎn)v，w，或者說(shuō)（v，w）和頂點(diǎn)v、w相關(guān)聯(lián)。
**頂點(diǎn)v的度：**在無(wú)向圖中與頂點(diǎn)v相關(guān)聯(lián)的邊的數(shù)量。
**頂點(diǎn)v的入度和出度：**在有向圖中，以頂點(diǎn)v作為弧頭的弧的數(shù)量稱(chēng)為頂點(diǎn)的入度，以頂點(diǎn)v作為弧尾的弧的數(shù)量稱(chēng)為頂點(diǎn)的出度。
**路徑：**從頂點(diǎn)v到達(dá)頂點(diǎn)w所經(jīng)歷的頂點(diǎn)序叫做路徑，路徑的長(zhǎng)度就是邊或弧的數(shù)目。
**回路或環(huán)：**起始點(diǎn)和終點(diǎn)相同的路徑稱(chēng)為回路或環(huán)。
**簡(jiǎn)單路徑：**路徑中頂點(diǎn)不重復(fù)出現(xiàn)的路徑稱(chēng)為簡(jiǎn)單路徑。
**簡(jiǎn)單回路或簡(jiǎn)單環(huán)：**起始點(diǎn)和終點(diǎn)相同且其余頂點(diǎn)不重復(fù)出現(xiàn)，被稱(chēng)為簡(jiǎn)單回路或簡(jiǎn)單環(huán)。
**連通圖：**在無(wú)向圖中，從頂點(diǎn)v到頂點(diǎn)w有路徑，則稱(chēng)v和w是連通的，如果圖中任意兩個(gè)頂點(diǎn)都是連通的，則稱(chēng)圖為連通圖。
**連通分量：**G1和G2都是連通圖，且G1是G2的子圖，則稱(chēng)G1是G2的連通分量或極大連通子圖。
強(qiáng)連通圖：在有向圖中，如果任意一對(duì)頂點(diǎn)都雙向連通，則稱(chēng)圖為強(qiáng)連通圖。
強(qiáng)連通分量：G1和G2都是強(qiáng)連通圖，且G1是G2的子圖，則稱(chēng)G1是G2的強(qiáng)連通分量或極大強(qiáng)連通子圖。
三、圖的存儲(chǔ)結(jié)構(gòu)：
鄰接矩陣：
? 使用兩個(gè)數(shù)組來(lái)存儲(chǔ)數(shù)據(jù)元素（頂點(diǎn)）和數(shù)據(jù)元素之間的關(guān)系（邊或弧）的信息。
? 一維數(shù)組：用于存儲(chǔ)頂點(diǎn)。
? 二維數(shù)組：用于存儲(chǔ)弧或邊。
鄰接矩陣的優(yōu)點(diǎn)：
? 訪問(wèn)速度快，方便計(jì)算結(jié)點(diǎn)的度、入度、出度。
鄰接矩陣的缺點(diǎn)：
? 頂點(diǎn)的容量有限，擴(kuò)容非常麻煩，只適合存儲(chǔ)稠密圖，存儲(chǔ)稀疏圖時(shí)會(huì)有大量的內(nèi)存浪費(fèi)。
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
// 無(wú)向圖
typedef struct Grahh
{
size_t cal; // 頂點(diǎn)容量
size_t cnt; // 頂點(diǎn)數(shù)量
char *vertex; // 存儲(chǔ)頂點(diǎn)的一維數(shù)組
char **edge; // 存儲(chǔ)邊的二維數(shù)組
} Graph;
Graph *create_graph(size_t cal)
{
Graph *graph = malloc(sizeof(Graph));
graph->vertex = malloc(sizeof(char) * cal);
graph->cal = cal;
graph->cnt = 0;
graph->edge = malloc(sizeof(char *) * cal);
for (int i = 0; i < cal; i++)
{
graph->edge[i] = calloc(sizeof(char), cal);
}
return graph;
}
bool add_vertex_graph(Graph *graph, char vertex)
{
if (graph->cnt >= graph->cal)
return false;
for (int i = 0; i < graph->cnt; i++)
{
if (graph->vertex[i] == vertex)
return false;
}
graph->vertex[graph->cnt++] = vertex;
return true;
}
bool add_edge_graph(Graph *graph, char v1, char v2)
{
int v1_index = -1, v2_index = -1;
for (int i = 0; i < graph->cnt; i++)
{
if (graph->vertex[i] == v1)
v1_index = i;
if (graph->vertex[i] == v2)
v2_index = i;
}
if (-1 == v1_index || -1 == v2_index || v1_index == v2_index)
return false;
graph->edge[v1_index][v2_index] = 1;
graph->edge[v2_index][v1_index] = 1;
return true;
}
// 查詢(xún)頂點(diǎn)在一維數(shù)組中的位置，如果不存在則返回-1
int query_vertex_graph(Graph *graph, char vertex)
{
for (int i = 0; i < graph->cnt; i++)
{
if (vertex == graph->vertex[i])
return i;
}
return -1;
}
// 查詢(xún)頂點(diǎn)第一個(gè)鄰接點(diǎn)，如果不存在則返回'\0'
char first_vertex_graph(Graph *graph, char vertex)
{
int index = query_vertex_graph(graph, vertex);
if (-1 == index)
return '\0';
for (int i = 0; i < graph->cnt; i++)
{
if (1 == graph->edge[index][i])
return graph->vertex[i];
}
return '\0';
}
// 刪除頂點(diǎn)
bool del_vertex_graph(Graph *graph, char vertex)
{
int index = query_vertex_graph(graph, vertex);
if (-1 == index)
return false;
for (int i = 0; i < graph->cnt; i++)
{
graph->edge[index][i] = 0;
graph->edge[i][index] = 0;
}
return true;
}
void _dfs_graph(Graph *graph, int index, bool *flags)
{
if (!flags[index])
return;
printf("%c\n", graph->vertex[index]);
flags[index] = false;
for (int i = 0; i < graph->cnt; i++)
{
if (1 == graph->edge[index][i])
_dfs_graph(graph, i, flags);
}
}
// 深度優(yōu)先遍歷，與樹(shù)的前序遍歷類(lèi)似
void dfs_graph(Graph *graph)
{
bool flags[graph->cnt];
for (int i = 0; i < graph->cnt; i++)
flags[i] = true;
for (int i = 0; i < graph->cnt; i++)
_dfs_graph(graph, i, flags);
}
// 廣度優(yōu)先遍歷，與樹(shù)的層序遍歷一樣，需要隊(duì)列結(jié)構(gòu)配合
void bfs_graph(Graph *graph)
{
bool flags[graph->cnt];
for (int i = 0; i < graph->cnt; i++)
flags[i] = true;
int queue[graph->cnt], front = 0, rear = 0;
for (int i = 0; i < graph->cnt; i++)
{
if (flags[i])
{
flags[i] = false;
queue[rear++] = i;
}
while (front != rear)
{
int index = queue[front++];
printf("%c ", graph->vertex[index]);
for (int j = 0; j < graph->cnt; j++)
{
if (1 == graph->edge[index][j] && flags[j])
{
flags[j] = false;
queue[rear++] = j;
}
}
}
}
}
// 銷(xiāo)毀圖
void destroy_graph(Graph *graph)
{
for (int i = 0; i < graph->cnt; i++)
{
free(graph->edge[i]);
}
free(graph->edge);
free(graph->vertex);
free(graph);
}
int main(int argc, const char *argv[])
{
Graph *graph = create_graph(5);
add_vertex_graph(graph, 'A');
add_vertex_graph(graph, 'B');
add_vertex_graph(graph, 'C');
add_vertex_graph(graph, 'D');
add_vertex_graph(graph, 'E');
add_edge_graph(graph, 'A', 'C');
add_edge_graph(graph, 'A', 'D');
add_edge_graph(graph, 'C', 'B');
add_edge_graph(graph, 'B', 'D');
// del_vertex_graph(graph,'C');
printf("------------------------\n");
for (int i = 0; i < graph->cnt; i++)
{
for (int j = 0; j < graph->cnt; j++)
{
printf("%hhd ", graph->edge[i][j]);
}
printf("\n");
}
// destroy_graph(graph);
// printf("%c\n",first_vertex_graph(graph,'D'));
// dfs_graph(graph);
bfs_graph(graph);
return 0;
}
鄰接表：
? 采用一維數(shù)組加單向鏈表的方式存儲(chǔ)存儲(chǔ)。
? 一維數(shù)組：用于存儲(chǔ)頂點(diǎn)和單向鏈表的頭指針。
? 單向鏈表：存儲(chǔ)著從該頂點(diǎn)出發(fā)的弧或邊。
鄰接表優(yōu)點(diǎn)：
? 與鄰接矩陣相比，它可以節(jié)約內(nèi)存，有多少條邊或弧就創(chuàng)建多少個(gè)鏈表節(jié)點(diǎn)，比較適合存儲(chǔ)稀疏圖。
鄰接表缺點(diǎn)：
? 計(jì)算入度、刪除節(jié)點(diǎn)時(shí)比較麻煩。
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
// 弧
typedef struct Bow
{
int dest;
struct Bow *next;
} Bow;
// 頂點(diǎn)
typedef struct Vertex
{
char data;
Bow first; // 單鏈表的空白頭節(jié)點(diǎn)
} Vertex;
// 有向圖
typedef struct Graph
{
Vertex *vertex;
size_t cal;
size_t cnt;
} Graph;
// 創(chuàng)建圖
Graph *create_graph(size_t cal)
{
Graph *graph = malloc(sizeof(Graph));
graph->vertex = malloc(sizeof(Vertex) * cal);
graph->cal = cal;
graph->cnt = 0;
return graph;
}
// 添加頂點(diǎn)
bool add_vertex_graph(Graph *graph, char vertex)
{
if (graph->cnt >= graph->cal)
return false;
// 頂點(diǎn)不能重復(fù)
for (int i = 0; i < graph->cnt; i++)
if (vertex == graph->vertex[i].data)
return false;
graph->vertex[graph->cnt].data = vertex;
graph->vertex[graph->cnt++].first.next = NULL;
return true;
}
// 查詢(xún)頂點(diǎn)
int query_vertex_graph(Graph *graph, char vertex)
{
for (int i = 0; i < graph->cnt; i++)
{
if (graph->vertex[i].data == vertex)
return i;
}
return -1;
}
// 添加弧
bool add_bow_graph(Graph *graph, char bow_tail, char bow_head)
{
int index_tail = query_vertex_graph(graph, bow_tail);
if (-1 == index_tail)
return false;
int index_head = query_vertex_graph(graph, bow_head);
if (-1 == index_head)
return false;
Bow *bow = malloc(sizeof(Bow));
bow->dest = index_head;
bow->next = graph->vertex[index_tail].first.next;
graph->vertex[index_tail].first.next = bow;
return true;
}
// 刪除頂點(diǎn)
bool del_vertex_graph(Graph *graph, char vertex)
{
int index = query_vertex_graph(graph, vertex);
if (-1 == index)
return false;
if (NULL != graph->vertex[index].first.next)
{
Bow *bow = graph->vertex[index].first.next;
graph->vertex[index].first.next = bow->next;
free(bow);
}
graph->vertex[index].data = '\0';
for (int i = 0; i < graph->cnt; i++)
{
for (Bow *bow = &graph->vertex[i].first; NULL != bow->next; bow = bow->next)
{
if (index == bow->next->dest)
{
Bow *tmp = bow->next;
bow->next = tmp->next;
free(tmp);
}
}
}
return true;
}
// 計(jì)算入度，計(jì)算出有多個(gè)弧的弧頭是某頂點(diǎn)
int indegree_vertex_graph(Graph *graph, char vertex)
{
// 打到頂點(diǎn)，遍歷所有弧，dest等于vertex下的弧有多少條，如果找不到則返回-1
int index = query_vertex_graph(graph, vertex);
if (-1 == index)
return -1;
int indegree = 0;
for (int i = 0; i < graph->cnt; i++)
{
Bow *bow = graph->vertex[i].first.next;
while (NULL != bow)
{
if (index == bow->dest)
indegree++;
bow = bow->next;
}
}
return indegree;
}
// 計(jì)算出度
int outdegree_vertex_graph(Graph *graph, char vertex)
{
// 找到頂點(diǎn)，從它出發(fā)的弧有多少條，如果找不到則返回-1
int index = query_vertex_graph(graph, vertex);
if (-1 == index)
return -1;
int outdegree = 0;
Bow *bow = graph->vertex[index].first.next;
while (NULL != bow)
{
outdegree++;
bow = bow->next;
}
return outdegree;
}
// 深度優(yōu)先遍歷
void _dfs_graph(Graph *graph, int index, bool *flags)
{
flags[index] = false;
printf("%c ", graph->vertex[index].data);
Bow *bow = graph->vertex[index].first.next;
while (NULL != bow)
{
if (flags[bow->dest])
_dfs_graph(graph, bow->dest, flags);
bow = bow->next;
}
}
void dfs_graph(Graph *graph)
{
// 參考昨天鄰接矩陣的業(yè)務(wù)邏輯
bool flags[graph->cnt];
for (int i = 0; i < graph->cnt; i++)
flags[i] = true;
for (int i = 0; i < graph->cnt; i++)
if (flags[i])
_dfs_graph(graph, i, flags);
printf("\n");
}
// 廣度優(yōu)先遍歷
void bfs_graph(Graph *graph)
{
bool flags[graph->cnt];
for (int i = 0; i < graph->cnt; i++)
flags[i] = true;
int queue[graph->cnt], front = 0, rear = 0;
for (int i = 0; i < graph->cnt; i++)
{
if (flags[i])
{
flags[i] = false;
queue[rear++] = i;
}
while (front != rear)
{
int index = queue[front++];
printf("%c ", graph->vertex[index].data);
Bow *bow = graph->vertex[index].first.next;
while (NULL != bow)
{
if (flags[bow->dest])
{
flags[bow->dest] = false;
queue[rear++] = bow->dest;
}
bow = bow->next;
}
}
}
printf("\n");
}
// 銷(xiāo)毀圖
void destroy_graph(Graph *graph)
{
for (int i = 0; i < graph->cnt; i++)
{
Bow *bow = &graph->vertex[i].first;
while (NULL != bow->next)
{
Bow *tmp = bow->next;
bow->next = tmp->next;
free(tmp);
}
}
free(graph->vertex);
free(graph);
}
int main(int argc, const char *argv[])
{
Graph *graph = create_graph(10);
add_vertex_graph(graph, 'A');
add_vertex_graph(graph, 'B');
add_vertex_graph(graph, 'C');
add_vertex_graph(graph, 'D');
add_vertex_graph(graph, 'E');
add_bow_graph(graph, 'A', 'D');
add_bow_graph(graph, 'A', 'E');
add_bow_graph(graph, 'A', 'C');
add_bow_graph(graph, 'C', 'B');
add_bow_graph(graph, 'B', 'D');
// add_bow_graph(graph,'E','D');
/*
del_vertex_graph(graph,'E');
for(int i=0; i<graph->cnt; i++)
{
printf("%d %c first->%p",i,graph->vertex[i].data,graph->vertex[i].first.next);
for(Bow* bow=graph->vertex[i].first.next; NULL!=bow; bow=bow->next)
{
printf(" %p dest:%d ",bow,bow->dest);
}
printf("\n");
}
printf("%d\n",outdegree_vertex_graph(graph,'B'));
printf("%d\n",indegree_vertex_graph(graph,'A'));
*/
dfs_graph(graph);
bfs_graph(graph);
destroy_graph(graph);
return 0;
}
十字鏈表：
? 采用一維數(shù)組加兩個(gè)十字鏈表進(jìn)行存儲(chǔ)，之所以叫十字鏈表，是因?yàn)樗逆湵砘」?jié)點(diǎn)會(huì)被兩個(gè)鏈表指向，同時(shí)弧節(jié)點(diǎn)有兩個(gè)指針，指向后續(xù)的弧節(jié)點(diǎn)。
? 一維數(shù)組：存儲(chǔ)了頂點(diǎn)數(shù)據(jù)，兩個(gè)鏈表頭指針。
? 出度鏈表：指向的是以該結(jié)點(diǎn)作為弧尾的弧節(jié)點(diǎn)。
? 入度鏈表：指向的是以該結(jié)點(diǎn)作為弧頭的弧節(jié)點(diǎn)。
十字鏈表的優(yōu)點(diǎn)：
? 與鄰接矩陣相比，它更節(jié)約內(nèi)存，與鄰接表相比它更方便計(jì)算頂點(diǎn)的出度。
十字鏈表的缺點(diǎn)：
? 刪除頂點(diǎn)和刪除弧時(shí)比較麻煩，也可以表示與實(shí)現(xiàn)無(wú)向圖，但更合適表示與實(shí)現(xiàn)有向圖。
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
// 弧
typedef struct Bow
{
int tailvex; // 弧尾的頂點(diǎn)下標(biāo)
int headvex; // 弧頭的頂點(diǎn)下標(biāo)
struct Bow *tlink; // 指向相同弧尾的弧節(jié)點(diǎn)
struct Bow *hlink; // 指向相同弧頭的弧節(jié)點(diǎn)
} Bow;
// 頂點(diǎn)
typedef struct Vertex
{
char data;
Bow *inlink;
Bow *outlink;
} Vertex;
// 圖
typedef struct Graph
{
Vertex *vertex;
size_t cal;
size_t cnt;
} Graph;
// 創(chuàng)建圖
Graph *create_graph(size_t cal)
{
Graph *graph = malloc(sizeof(Graph));
graph->vertex = malloc(sizeof(Vertex) * cal);
graph->cal = cal;
graph->cnt = 0;
return graph;
}
// 查詢(xún)頂點(diǎn)下標(biāo)
int query_vertex_graph(Graph *graph, char vertex)
{
for (int i = 0; i < graph->cnt; i++)
if (vertex == graph->vertex[i].data)
return i;
return -1;
}
// 添加頂點(diǎn)
bool add_vertex_graph(Graph *graph, char vertex)
{
// 如果頂點(diǎn)已經(jīng)滿(mǎn)，或頂點(diǎn)已經(jīng)存在則返回false
if (graph->cnt >= graph->cal || -1 != query_vertex_graph(graph, vertex))
return false;
graph->vertex[graph->cnt].data = vertex;
graph->vertex[graph->cnt].inlink = NULL;
graph->vertex[graph->cnt++].outlink = NULL;
return true;
}
// 添加弧
bool add_bow_graph(Graph *graph, char tailvex, char headvex)
{
// 如果弧頭或弧尾的頂點(diǎn)不存在則添加失敗
int tailindex = query_vertex_graph(graph, tailvex);
int headindex = query_vertex_graph(graph, headvex);
if (-1 == tailindex || -1 == headindex)
return false;
// 創(chuàng)建一個(gè)弧
Bow *bow = malloc(sizeof(Bow));
bow->tailvex = tailindex;
bow->headvex = headindex;
bow->tlink = graph->vertex[tailindex].outlink;
graph->vertex[tailindex].outlink = bow;
bow->hlink = graph->vertex[headindex].inlink;
graph->vertex[headindex].inlink = bow;
return true;
}
// 刪除頂點(diǎn)
bool del_vertex_graph(Graph *graph, char vertex)
{
// 找到頂點(diǎn)的下標(biāo)，如果找不到則返回false
int index = query_vertex_graph(graph, vertex);
if (-1 == index)
return false;
// 以它作為弧尾的弧要全部斷開(kāi)
graph->vertex[index].inlink = NULL;
// 以它作為弧頭的弧要全部刪除
for (int i = 0; i < graph->cnt; i++)
{
Bow *out = graph->vertex[i].outlink;
while (NULL != out && NULL != out->tlink)
{
if (out->tlink->headvex == index)
{
Bow *tmp = out->tlink;
out->tlink = tmp->tlink;
free(tmp);
}
out = out->tlink;
}
if (NULL != graph->vertex[i].outlink &&
index == graph->vertex[i].outlink->headvex)
{
Bow *tmp = graph->vertex[i].outlink;
graph->vertex[i].outlink = tmp->tlink;
free(tmp);
}
}
return true;
}
// 刪除弧
bool del_bow_graph(Graph *graph, char tailvex, char headvex)
{
// 找到弧頭、弧尾頂點(diǎn)的下標(biāo)，如果有一個(gè)找不到就返回false
int tailindex = query_vertex_graph(graph, tailvex);
int headindex = query_vertex_graph(graph, headvex);
if (-1 == tailindex || -1 == headindex)
return false;
// 刪除弧，并且要保證兩個(gè)鏈表不斷開(kāi)
Bow *out = graph->vertex[tailindex].outlink;
while (NULL != out && NULL != out->tlink)
{
if (out->tlink->headvex == headindex)
{
out->tlink = out->tlink->tlink;
break;
}
out = out->tlink;
}
if (NULL != graph->vertex[tailindex].outlink &&
headindex == graph->vertex[tailindex].outlink->headvex)
{
graph->vertex[tailindex].outlink = graph->vertex[tailindex].outlink->tlink;
}
Bow *in = graph->vertex[headindex].inlink;
while (NULL != in && NULL != in->hlink)
{
if (in->hlink->tailvex == tailindex)
{
Bow *tmp = in->hlink;
in->hlink = tmp->hlink;
free(tmp);
break;
}
in = in->hlink;
}
if (NULL != graph->vertex[headindex].outlink &&
tailindex == graph->vertex[headindex].outlink->tailvex)
{
Bow *tmp = graph->vertex[headindex].inlink;
graph->vertex[headindex].inlink = tmp->hlink;
free(tmp);
}
return true;
}
// 計(jì)算入度
int indegree_vertex_graph(Graph *graph, char vertex)
{
int index = query_vertex_graph(graph, vertex);
if (-1 == index)
return -1;
int indegree = 0;
Bow *in = graph->vertex[index].inlink;
while (NULL != in)
{
indegree++;
in = in->hlink;
}
return indegree;
}
// 計(jì)算出度
int outdegree_vertex_graph(Graph *graph, char vertex)
{
int index = query_vertex_graph(graph, vertex);
if (-1 == index)
return -1;
int outdegree = 0;
Bow *out = graph->vertex[index].outlink;
while (NULL != out)
{
outdegree++;
out = out->tlink;
}
return outdegree;
}
// 深度優(yōu)先
void _dfs_graph(Graph *graph, int index, bool *flags)
{
printf("%c ", graph->vertex[index].data);
flags[index] = false;
Bow *out = graph->vertex[index].outlink;
while (NULL != out)
{
if (flags[out->headvex])
_dfs_graph(graph, out->headvex, flags);
out = out->tlink;
}
}
void dfs_graph(Graph *graph)
{
bool flags[graph->cnt];
for (int i = 0; i < graph->cnt; i++)
flags[i] = true;
for (int i = 0; i < graph->cnt; i++)
if (flags[i])
_dfs_graph(graph, i, flags);
printf("\n");
}
// 廣度優(yōu)先
void bfs_graph(Graph *graph)
{
bool flags[graph->cnt];
for (int i = 0; i < graph->cnt; i++)
flags[i] = true;
int queue[graph->cnt], front = 0, rear = 0;
for (int i = 0; i < graph->cnt; i++)
{
if (flags[i])
{
queue[rear++] = i;
flags[i] = false;
}
while (front != rear)
{
int index = queue[front++];
printf("%c ", graph->vertex[index].data);
Bow *out = graph->vertex[index].outlink;
while (NULL != out)
{
if (flags[out->headvex])
{
queue[rear++] = out->headvex;
flags[out->headvex] = false;
}
out = out->tlink;
}
}
}
printf("\n");
}
// 銷(xiāo)毀圖
void destroy_graph(Graph *graph)
{
for (int i = 0; i < graph->cnt; i++)
del_vertex_graph(graph, graph->vertex[i].data);
free(graph->vertex);
free(graph);
}
int main(int argc, const char *argv[])
{
Graph *graph = create_graph(10);
add_vertex_graph(graph, 'A');
add_vertex_graph(graph, 'B');
add_vertex_graph(graph, 'C');
add_vertex_graph(graph, 'D');
add_vertex_graph(graph, 'E');
add_bow_graph(graph, 'A', 'D');
add_bow_graph(graph, 'A', 'E');
add_bow_graph(graph, 'A', 'C');
add_bow_graph(graph, 'C', 'B');
add_bow_graph(graph, 'B', 'D');
add_bow_graph(graph, 'E', 'D');
dfs_graph(graph);
bfs_graph(graph);
destroy_graph(graph);
// del_vertex_graph(graph,'D');
// del_bow_graph(graph,'A','D');
/*
printf("%d\n",indegree_vertex_graph(graph,'B'));
for(int i=0; i<graph->cnt; i++)
{
printf("vex:%c",graph->vertex[i].data);
printf("\n\t");
Bow* out = graph->vertex[i].outlink;
while(NULL != out)
{
printf("%d->%d ",out->tailvex,out->headvex);
out = out->tlink;
}
printf("\n\t");
Bow* in= graph->vertex[i].inlink;
while(NULL != in)
{
printf("%d<-%d ",in->headvex,in->tailvex);
in = in->hlink;
}
printf("\n");
}
*/
return 0;
}
鄰接多重表：
? 是對(duì)鄰接表一種擴(kuò)展，在鄰接表邊的基礎(chǔ)上，增加了訪問(wèn)標(biāo)記、組成邊的兩個(gè)頂點(diǎn)的下標(biāo)、指向依附這兩個(gè)頂點(diǎn)的下一條邊的指針。
? 使用鄰接表時(shí)，它的一條邊的兩個(gè)節(jié)點(diǎn)，分別在第i和第j的兩個(gè)鏈表中，這給圖的操作帶來(lái)不便，而鄰接多重表的鏈表節(jié)點(diǎn)增加各項(xiàng)成員，方便對(duì)圖的操作。
A’, ‘C’);
add_bow_graph(graph, ‘C’, ‘B’);
add_bow_graph(graph, ‘B’, ‘D’);
add_bow_graph(graph, ‘E’, ‘D’);
dfs_graph(graph);
bfs_graph(graph);
destroy_graph(graph);
// del_vertex_graph(graph,‘D’);
// del_bow_graph(graph,‘A’,‘D’);
/*
printf(“%d\n”,indegree_vertex_graph(graph,‘B’));
for(int i=0; icnt; i++)
{
printf(“vex:%c”,graph->vertex[i].data);
printf(“\n\t”);
Bow* out = graph->vertex[i].outlink;
while(NULL != out)
{
printf(“%d->%d “,out->tailvex,out->headvex);
out = out->tlink;
}
printf(”\n\t”);
Bow* in= graph->vertex[i].inlink;
while(NULL != in)
{
printf(“%d<-%d “,in->headvex,in->tailvex);
in = in->hlink;
}
printf(”\n”);
}
*/
return 0;
}
#### 鄰接多重表：
? 是對(duì)鄰接表一種擴(kuò)展，在鄰接表邊的基礎(chǔ)上，增加了訪問(wèn)標(biāo)記、組成邊的兩個(gè)頂點(diǎn)的下標(biāo)、指向依附這兩個(gè)頂點(diǎn)的下一條邊的指針。
? 使用鄰接表時(shí)，它的一條邊的兩個(gè)節(jié)點(diǎn)，分別在第i和第j的兩個(gè)鏈表中，這給圖的操作帶來(lái)不便，而鄰接多重表的鏈表節(jié)點(diǎn)增加各項(xiàng)成員，方便對(duì)圖的操作。
原文鏈接：https://blog.csdn.net/weixin_52744725/article/details/127041968
相關(guān)推薦
- 2022-12-04 Flutter狀態(tài)管理Provider的使用示例詳解_Android
- 2022-05-18 基于python介紹pytorch保存和恢復(fù)參數(shù)_python
- 2022-09-05 SpringBoot 自動(dòng)配置原理
- 2022-08-21 android實(shí)現(xiàn)貝塞爾曲線之波浪效果_Android
- 2022-11-08 云原生系列Kubernetes深度解析YAML文件使用_云其它
- 2022-12-10 Qt如何自定義滑動(dòng)條_C 語(yǔ)言
- 2022-10-15 Go?Excelize?API源碼解讀GetSheetViewOptions與SetPageLayo
- 2022-06-08 Spring Cloud Nacos 配置動(dòng)態(tài)刷新
- 最近更新
-
- window11 系統(tǒng)安裝 yarn
- 超詳細(xì)win安裝深度學(xué)習(xí)環(huán)境2025年最新版（
- Linux 中運(yùn)行的top命令 怎么退出？
- MySQL 中decimal 的用法？ 存儲(chǔ)小
- get 、set 、toString 方法的使
- @Resource和 @Autowired注解
- Java基礎(chǔ)操作-- 運(yùn)算符，流程控制 Flo
- 1. Int 和Integer 的區(qū)別，Jav
- spring @retryable不生效的一種
- Spring Security之認(rèn)證信息的處理
- Spring Security之認(rèn)證過(guò)濾器
- Spring Security概述快速入門(mén)
- Spring Security之配置體系
- 【SpringBoot】SpringCache
- Spring Security之基于方法配置權(quán)
- redisson分布式鎖中waittime的設(shè)
- maven:解決release錯(cuò)誤：Artif
- restTemplate使用總結(jié)
- Spring Security之安全異常處理
- MybatisPlus優(yōu)雅實(shí)現(xiàn)加密？
- Spring ioc容器與Bean的生命周期。
- 【探索SpringCloud】服務(wù)發(fā)現(xiàn)-Nac
- Spring Security之基于HttpR
- Redis 底層數(shù)據(jù)結(jié)構(gòu)-簡(jiǎn)單動(dòng)態(tài)字符串（SD
- arthas操作spring被代理目標(biāo)對(duì)象命令
- Spring中的單例模式應(yīng)用詳解
- 聊聊消息隊(duì)列，發(fā)送消息的4種方式
- bootspring第三方資源配置管理
- GIT同步修改后的遠(yuǎn)程分支
提供CDN加速