對(duì)比矩陣創(chuàng)建圖##
如果圖的邊數(shù)拳氢，比較少募逞，使用矩陣，會(huì)有大量空間浪費(fèi)馋评；
這個(gè)時(shí)候放接，考慮另外一種存儲(chǔ)結(jié)構(gòu)方式，將數(shù)組和鏈表結(jié)合起來來存儲(chǔ)留特；
鄰接表的處理：
- 圖中的頂點(diǎn)用一個(gè)一維數(shù)組存儲(chǔ)纠脾；
- 圖中每個(gè)頂點(diǎn)Vi的所有鄰接點(diǎn)構(gòu)成一個(gè)線性表（單鏈表）
實(shí)現(xiàn)代碼
結(jié)構(gòu)：
#define MAX_SIZE 20
// ========= 鄰接表 無向 Start ================
// 鏈表結(jié)點(diǎn) Node
typedef struct LinkNode {
int array_index; // 數(shù)組下標(biāo)
int weight; // 權(quán)重
struct LinkNode *next; // 下一個(gè)頂點(diǎn)
} LinkNode;
// 圖結(jié)點(diǎn)
typedef struct GraphNode {
char data; // 結(jié)點(diǎn)數(shù)據(jù)
struct LinkNode *first; // 頂點(diǎn)鏈表
} GraphNode;
// 圖
typedef struct GraphTable {
GraphNode nodes[MAX_SIZE];
int vertexNum, edgeNum; // 頂點(diǎn)數(shù)，變數(shù)
} GraphTable, *P_GraphTable;
創(chuàng)建表：
// ==== 使用鄰接表 來創(chuàng)建圖 無向 start ====
void printTable(P_GraphTable *G) {
int i;
LinkNode *node;
// 輸出鄰接表
printf("------------ 無向鄰接表 ----------\n");
for(i=0; i<(*G)->vertexNum; i++) {
node = NULL;
node = (*G)->nodes[i].first;
printf("%d-%c|-",i, (*G)->nodes[i].data);
while( node != NULL && node->array_index >= 0) {
printf("%d-",node->array_index);
node = node->next;
}
printf("\n"); // 換行
}
}
void createTable(P_GraphTable *G) {
(*G) = (P_GraphTable) malloc(sizeof(GraphTable));
int m,n,i;
printf("請(qǐng)輸入圖的頂點(diǎn)數(shù)與邊數(shù):");
scanf("%d %d", &m, &n);
getchar();
(*G)->vertexNum = m;
(*G)->edgeNum = n;
// 創(chuàng)建頂點(diǎn)數(shù)組 GraphNode
for(m = 0; m<(*G)->vertexNum; m++) {
printf("請(qǐng)輸入第 %d 個(gè)頂點(diǎn):", (m+1));
scanf("%c", &(*G)->nodes[m].data);
getchar();
(*G)->nodes[m].first = NULL; // 初始化為空表
}
// 創(chuàng)建邊
for(i = 0; i<(*G)->edgeNum; i++) {
printf("請(qǐng)輸入第%d條邊(Vi,Vj)上的下標(biāo)i,下標(biāo)j:\n", (i+1));
scanf("%d %d", &m, &n); // 下標(biāo)對(duì)應(yīng)頂點(diǎn)
getchar();
LinkNode *e1 = (LinkNode *)malloc(sizeof(LinkNode));
e1->array_index = n; // 設(shè)置鄰接點(diǎn)下標(biāo)
e1->next = (*G)->nodes[m].first; // 第一次時(shí)蜕青，first為NULL苟蹈，后面會(huì)被替換掉
(*G)->nodes[m].first = e1; // 放入圖中數(shù)組
LinkNode *e2 = (LinkNode *)malloc(sizeof(LinkNode));
e2->array_index = m; // 設(shè)置鄰接點(diǎn)下標(biāo)
e2->next = (*G)->nodes[n].first;
(*G)->nodes[n].first = e2;
}
printTable(G);
}
int main(int argc, const char * argv[]) {
P_GraphTable table;
createTable(&table);
return 0;
}
輸出如下
請(qǐng)輸入圖的頂點(diǎn)數(shù)與邊數(shù):4 5
請(qǐng)輸入第 1 個(gè)頂點(diǎn):A
請(qǐng)輸入第 2 個(gè)頂點(diǎn):B
請(qǐng)輸入第 3 個(gè)頂點(diǎn):C
請(qǐng)輸入第 4 個(gè)頂點(diǎn):D
請(qǐng)輸入第1條邊(Vi,Vj)上的下標(biāo)i,下標(biāo)j:
0 1
請(qǐng)輸入第2條邊(Vi,Vj)上的下標(biāo)i,下標(biāo)j:
0 2
請(qǐng)輸入第3條邊(Vi,Vj)上的下標(biāo)i,下標(biāo)j:
1 2
請(qǐng)輸入第4條邊(Vi,Vj)上的下標(biāo)i,下標(biāo)j:
2 3
請(qǐng)輸入第5條邊(Vi,Vj)上的下標(biāo)i,下標(biāo)j:
1 3
------------ 無向鄰接表 ----------
0-A|-2-1-
1-B|-3-2-0-
2-C|-3-1-0-
3-D|-1-2-
深度優(yōu)先遍歷（不斷訪問鏈表）##
直接訪問鏈表即可；
// 清空已訪問過得頂點(diǎn)數(shù)組
void clearVisit(P_GraphTable G) {
int i;
for(i=0; i<G->vertexNum; i++) {
visited[i] = FALSE;
}
}
void dfs(P_GraphTable G, int i) {
visited[i] = TRUE;
printf("%c ", G->nodes[i].data);
LinkNode *node = G->nodes[i].first;
while(node) {
if(!visited[node->array_index]) {
dfs(G, node->array_index);
}
node = node->next;
}
}
void dfs_g(P_GraphTable G) {
clearVisit(G);
int i;
for(i=0; i<G->vertexNum; i++) {
if(!visited[i]) { // 連通圖右核，只會(huì)執(zhí)行一次
dfs(G, i);
}
}
}
廣度優(yōu)先遍歷 實(shí)現(xiàn)代碼##
//========= 廣度 Start ===================
typedef struct {
int array[MAX_SIZE];
int front;
int rear;
} Queue;
void initQueue(Queue *que) {
que->front = 0;
que->rear = -1;
}
int isQueueEmpty(Queue *que) {
return (que->rear + 1 == que->front || que->front == MAX_SIZE);
}
void insertQueue(Queue *que, int x) {
if(que->rear != MAX_SIZE - 1) { // 未滿
que->array[++que->rear] = x;
}
}
int removeQueue(Queue *que) {
return que->array[que->front++];
}
void bfs(P_GraphTable G) {
Queue *que = (Queue *)malloc(sizeof(Queue));
initQueue(que);
clearVisit(G);
int i;
int v;
for(i=0; i<G->vertexNum; i++) {
if(!visited[i]) { // 選取一個(gè)未訪問的頂點(diǎn),如果圖是連通圖,則只執(zhí)行一次
printf("%c ", G->nodes[i].data);
visited[i] = TRUE;
insertQueue(que, i);
while(!isQueueEmpty(que)) {
v = removeQueue(que);
LinkNode *node = G->nodes[v].first;
while(node) {
if(!visited[node->array_index]) {
insertQueue(que, node->array_index);
visited[node->array_index] = TRUE;
printf("%c ", G->nodes[node->array_index].data);
}
node = node->next;
}
}
}
}
}
//========= 廣度 End ===================
