鄰接表介紹

鄰接矩陣是不錯的一種圖存儲結構，但是我們也發現，對于邊數相對頂點較少的圖，這種結構比較較浪費存儲空間。如果不想浪費存儲空間，大家肯定會先到鏈表。需要空間的時候再才想內存去申請，同樣適用于圖的存儲。我們把這種數組與鏈表相結合的存儲方式成為鄰接表（Adjacency List）。關于鄰接矩陣的詳細介紹請看：圖：圖的鄰接矩陣創建、深度優先遍歷和廣度優先遍歷詳解?。

鄰接表創建圖

我們創建邊表的單鏈表時，可以使用頭插法和尾插法創建，不過尾插法要麻煩一點，需要先創建頭結點，最后還要釋放頭結點，不過2種方法 效果一樣。

//鄰接表創建無向網圖 GraphAdjList* CreateGraphAdjList() {GraphAdjList* graph = (GraphAdjList*)malloc(sizeof(GraphAdjList));int vexNum, edgeNum;printf("請輸入頂點和邊數(用逗號隔開):");scanf("%d,%d",&vexNum,&edgeNum);graph->edgeNun = edgeNum;graph->vexNum = vexNum;getchar();//消除上面的換行符printf("請輸入頂點的值:");輸入頂點值//for (int i = 0; i < vexNum; i++)//{// scanf("%c", &graph->list[i].data);// graph->list[i].first = NULL;//初始化first指針域//}輸入邊表數據//for (int k = 0; k < edgeNum; k++)//{// int i, j, w;// printf("請輸入(Vi,Vj)對應的頂點下標和權值(用逗號隔開):");// scanf("%d,%d,%d", &i, &j, &w);// //i -> j i出度到j// EdgeNode* edge = (EdgeNode*)malloc(sizeof(EdgeNode));//創建邊結點// edge->vexIndex = j;// edge->weight = w;// edge->next = graph->list[i].first;//頭插法 往單鏈表插入結點// graph->list[i].first = edge;// //由于是無向的，實現上是雙向的，故邊數據(Vj,Vi)也要創建// //j -> i j出度到i// edge = (EdgeNode*)malloc(sizeof(EdgeNode));// edge->vexIndex = i;// edge->weight = w;// edge->next = graph->list[j].first;;// graph->list[j].first = edge;//}//每個單鏈表的尾指針數組EdgeNode** tailArr = (EdgeNode**)malloc(sizeof(EdgeNode*)*vexNum);//輸入頂點值for (int i = 0; i < vexNum; i++){scanf("%c", &graph->list[i].data);graph->list[i].first = (EdgeNode*)malloc(sizeof(EdgeNode));//創建頭結點，采用尾插入graph->list[i].first->next = NULL;tailArr[i] = graph->list[i].first;}//輸入邊表數據for (int k = 0; k < edgeNum; k++){int i, j, w;printf("請輸入(Vi,Vj)對應的頂點下標和權值(用逗號隔開):");scanf("%d,%d,%d", &i, &j, &w);//i -> j i出度到jEdgeNode* edge = (EdgeNode*)malloc(sizeof(EdgeNode));//創建邊結點edge->vexIndex = j;edge->weight = w;edge->next = NULL;tailArr[i]->next = edge; //采用尾插法tailArr[i] = edge;edge = (EdgeNode*)malloc(sizeof(EdgeNode));edge->vexIndex = i;edge->weight = w;edge->next = NULL;tailArr[j]->next = edge;tailArr[j] = edge;}//將頭結點釋放for (int i = 0; i < vexNum; i++){EdgeNode* head = graph->list[i].first;graph->list[i].first = head->next;free(head);}return graph; }

鄰接表的深度優先遍歷

void DFTGraphAdjList(GraphAdjList* graph,int vexIndex) {//訪問過不再訪問if (g_visited[vexIndex] == TRUE){return;}g_visited[vexIndex] = TRUE;VisitGraphAdjListVertex(graph->list[vexIndex].data);EdgeNode* node = graph->list[vexIndex].first;while (node){DFTGraphAdjList(graph, node->vexIndex);node = node->next;}return; }//深度優先遍歷鄰接表 void TraverseGraphAdjList(GraphAdjList* graph) {if (NULL == graph){return;}for (int i = 0; i < graph->vexNum; i++){g_visited[i] = FALSE;}for (int i = 0; i < graph->vexNum; i++){if (g_visited[i] == FALSE){DFTGraphAdjList(graph, i);}}return; }

鄰接表的廣度優先遍歷

//廣度優先遍歷鄰接表 void BFTGraphAdjList(GraphAdjList* graph) {if (NULL == graph){return;}Queue queue;InitQueue(&queue);//初始化頂點都沒有訪問過for (int i = 0; i < graph->vexNum; i++){g_visited[i] = FALSE;}for (int i = 0; i < graph->vexNum; i++){if (g_visited[i] == FALSE){g_visited[i] = TRUE;VertexType vex = graph->list[i].data;VisitGraphAdjListVertex(vex);//訪問頂點數據EnQueue(&queue, i);//將訪問過的頂點下標入隊//為什么這里要循環出隊呢？出隊獲取已經訪問過結點的下標，在內層的for繼續訪問其相關聯結點，將減少外層for循環進入if次數while (!EmptyQueue(&queue)){int vexIndex;DeQueue(&queue, &vexIndex);//將訪問過的頂點下標出隊EdgeNode* node = graph->list[vexIndex].first;//將該節點的連接的結點且沒有被訪問過的結點進行訪問，然后入隊while (node != NULL && g_visited[node->vexIndex] == FALSE){g_visited[node->vexIndex] = TRUE;VertexType vex = graph->list[node->vexIndex].data;VisitGraphAdjListVertex(vex);EnQueue(&queue, node->vexIndex);node = node->next;}}}}return; }

代碼匯總

Queue.h

#pragma once #ifndef __QUEUE_H__ #define __QUEUE_H__typedef int EleType;//元素類型 typedef enum { ERROR, OK } Status; typedef enum {FALSE,TRUE} Boolean;//隊列結點 typedef struct QueueNode {EleType data;struct QueueNode* next; }QueueNode;//隊列 typedef struct Queue {QueueNode* front;QueueNode* tail; }Queue;//隊列初始化 void InitQueue(Queue* queue);//入隊 int EnQueue(Queue* queue, EleType data);//出隊 int DeQueue(Queue* queue, EleType* data);//隊列是否為空 int EmptyQueue(Queue* queue);#endif // !__QUEUE_H__

Queue.c

#include <stdlib.h> #include "Queue.h"//隊列初始化 void InitQueue(Queue* queue) {queue->front = NULL;queue->tail = NULL;return; }//入隊 int EnQueue(Queue* queue, EleType data) {if (NULL == queue){return ERROR;}QueueNode* node = (QueueNode*)malloc(sizeof(QueueNode));node->data = data;node->next = NULL;if (queue->front == NULL){queue->front = queue->tail = node;}else{queue->tail->next = node;queue->tail = node;}return OK; } //出隊 int DeQueue(Queue* queue, EleType* data) {if (NULL == queue){return ERROR;}if (!EmptyQueue(queue)){QueueNode* node = queue->front;*data = node->data;queue->front = queue->front->next;if (NULL != node){free(node);node = NULL;}//隊列的最后一個元素出隊列后，tail指針也要置為空if (EmptyQueue(queue)){queue->tail = queue->front;}}return OK; }//隊列是否為空 int EmptyQueue(Queue* queue) {if (NULL == queue){return ERROR;}if (queue->front == NULL){return TRUE;}return FALSE; }

GraphAdjList.c

#define _CRT_SECURE_NO_WARNINGS #include <stdio.h> #include <stdlib.h> #include "Queue.h" #define MAX_VERTEX 100 typedef char VertexType;//頂點類型 typedef int EdgeType;//邊上權值類型 //邊表結點數據結構 typedef struct EdgeNode {int vexIndex;//頂點下標EdgeType weight;//權值struct EdgeNode* next; //指向下一個結點 }EdgeNode; Boolean g_visited[MAX_VERTEX] = { 0 };//全局變量 頂點訪問標志位數組 //頂點表數據結構 typedef struct VextexNode {VertexType data;EdgeNode* first;//邊表第一個結點 }VextexNode,AdjList[MAX_VERTEX];typedef struct GraphAdjList {AdjList list;int vexNum, edgeNun;//頂點，邊 的數量 }GraphAdjList;//鄰接表創建無向網圖 GraphAdjList* CreateGraphAdjList() {GraphAdjList* graph = (GraphAdjList*)malloc(sizeof(GraphAdjList));int vexNum, edgeNum;printf("請輸入頂點和邊數(用逗號隔開):");scanf("%d,%d",&vexNum,&edgeNum);graph->edgeNun = edgeNum;graph->vexNum = vexNum;getchar();//消除上面的換行符printf("請輸入頂點的值:");輸入頂點值//for (int i = 0; i < vexNum; i++)//{// scanf("%c", &graph->list[i].data);// graph->list[i].first = NULL;//初始化first指針域//}輸入邊表數據//for (int k = 0; k < edgeNum; k++)//{// int i, j, w;// printf("請輸入(Vi,Vj)對應的頂點下標和權值(用逗號隔開):");// scanf("%d,%d,%d", &i, &j, &w);// //i -> j i出度到j// EdgeNode* edge = (EdgeNode*)malloc(sizeof(EdgeNode));//創建邊結點// edge->vexIndex = j;// edge->weight = w;// edge->next = graph->list[i].first;//頭插法 往單鏈表插入結點// graph->list[i].first = edge;// //由于是無向的，實現上是雙向的，故邊數據(Vj,Vi)也要創建// //j -> i j出度到i// edge = (EdgeNode*)malloc(sizeof(EdgeNode));// edge->vexIndex = i;// edge->weight = w;// edge->next = graph->list[j].first;;// graph->list[j].first = edge;//}//每個單鏈表的尾指針數組EdgeNode** tailArr = (EdgeNode**)malloc(sizeof(EdgeNode*)*vexNum);//輸入頂點值for (int i = 0; i < vexNum; i++){scanf("%c", &graph->list[i].data);graph->list[i].first = (EdgeNode*)malloc(sizeof(EdgeNode));//創建頭結點，采用尾插入graph->list[i].first->next = NULL;tailArr[i] = graph->list[i].first;}//輸入邊表數據for (int k = 0; k < edgeNum; k++){int i, j, w;printf("請輸入(Vi,Vj)對應的頂點下標和權值(用逗號隔開):");scanf("%d,%d,%d", &i, &j, &w);//i -> j i出度到jEdgeNode* edge = (EdgeNode*)malloc(sizeof(EdgeNode));//創建邊結點edge->vexIndex = j;edge->weight = w;edge->next = NULL;tailArr[i]->next = edge; //采用尾插法tailArr[i] = edge;edge = (EdgeNode*)malloc(sizeof(EdgeNode));edge->vexIndex = i;edge->weight = w;edge->next = NULL;tailArr[j]->next = edge;tailArr[j] = edge;}//將頭結點釋放for (int i = 0; i < vexNum; i++){EdgeNode* head = graph->list[i].first;graph->list[i].first = head->next;free(head);}return graph; } //打印 鄰接表的無向圖 void PrintGraphAdjList(GraphAdjList* graph) {printf("頂點數據:\n");//頂點數據for (int i = 0; i < graph->vexNum; i++){printf("%c ",graph->list[i].data);}printf("\n邊數據:\n");EdgeNode* temp = NULL;//邊數據for (int i = 0; i < graph->vexNum; i++){temp = graph->list[i].first;while (temp){printf("%d\t",temp->weight);temp = temp->next;}printf("\n");}return; } //訪問頂點元素 void VisitGraphAdjListVertex(VertexType data) {printf("%c ", data);return; } void DFTGraphAdjList(GraphAdjList* graph,int vexIndex) {//訪問過不再訪問if (g_visited[vexIndex] == TRUE){return;}g_visited[vexIndex] = TRUE;VisitGraphAdjListVertex(graph->list[vexIndex].data);EdgeNode* node = graph->list[vexIndex].first;while (node){DFTGraphAdjList(graph, node->vexIndex);node = node->next;}return; }//深度優先遍歷鄰接表 void TraverseGraphAdjList(GraphAdjList* graph) {if (NULL == graph){return;}for (int i = 0; i < graph->vexNum; i++){g_visited[i] = FALSE;}for (int i = 0; i < graph->vexNum; i++){if (g_visited[i] == FALSE){DFTGraphAdjList(graph, i);}}return; } //廣度優先遍歷鄰接表 void BFTGraphAdjList(GraphAdjList* graph) {if (NULL == graph){return;}Queue queue;InitQueue(&queue);//初始化頂點都沒有訪問過for (int i = 0; i < graph->vexNum; i++){g_visited[i] = FALSE;}for (int i = 0; i < graph->vexNum; i++){if (g_visited[i] == FALSE){g_visited[i] = TRUE;VertexType vex = graph->list[i].data;VisitGraphAdjListVertex(vex);//訪問頂點數據EnQueue(&queue, i);//將訪問過的頂點下標入隊//為什么這里要循環出隊呢？出隊獲取已經訪問過結點的下標，在內層的for繼續訪問其相關聯結點，將減少外層for循環進入if次數while (!EmptyQueue(&queue)){int vexIndex;DeQueue(&queue, &vexIndex);//將訪問過的頂點下標出隊EdgeNode* node = graph->list[vexIndex].first;//將該節點的連接的結點且沒有被訪問過的結點進行訪問，然后入隊while (node != NULL && g_visited[node->vexIndex] == FALSE){g_visited[node->vexIndex] = TRUE;VertexType vex = graph->list[node->vexIndex].data;VisitGraphAdjListVertex(vex);EnQueue(&queue, node->vexIndex);node = node->next;}}}}return; }int main(int argc, char *argv[]) {GraphAdjList* graph = CreateGraphAdjList();PrintGraphAdjList(graph);printf("深度優先遍歷鄰接表:\n");TraverseGraphAdjList(graph);printf("\n廣度優先遍歷鄰接表:\n");BFTGraphAdjList(graph);printf("\n");return 0; }

代碼運行測試

我們來創建如下圖的一個圖，圖是教材上的。

代碼運行結果：

總結

以上是生活随笔為你收集整理的图：图的邻接表创建、深度优先遍历和广度优先遍历代码实现的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。