鄰接矩陣介紹

直接說，鄰接矩陣是圖的一種存儲結構。那么圖是什么呢？圖是一種邏輯結構，和線性結構、樹形結構、集合結構一樣 是一種邏輯結構用來描述數據對象中的數據元素之間的關系。來看下圖的定義：圖（Graph）是有頂點的有窮非空集和頂點之間邊的集合組成，通常表示為G（V，E）其中，G表示一個圖，V是圖G中頂點的集合，E是圖G中邊的集合。

考慮到圖是有頂點和邊或弧2部分組成。合在一起比較困難，那就自然的考慮到分為2個結構來分別存儲。

圖的鄰接矩陣（Adjacency Matrix）存儲方式是用2個數組來表示圖。一個一維數組存儲圖中頂點的信息，一個二維數組（稱為鄰接矩陣）存儲圖中的邊或弧的信息。

鄰接矩陣創建圖

任何算法，我們最先考慮的肯定是數據結構，那么用鄰接矩陣的方式，圖的數據結構就很好表示了。包含頂點數組，鄰接矩陣，當然還有頂點數量和邊的數量。數據結構是為算法進行服務的。圖的數據結構：

typedef struct
{
VertexType vertex[MAX_VERTEX];//頂點集
EdgeType edge[MAX_VERTEX][MAX_VERTEX];//邊集
int vertexNum, edgeNum;//頂點數，邊數
}MGraph;

對圖的數據結構清楚后，創建圖的算法，其實就是圖內容的一個賦值。

CreateMGraph 函數

//鄰接矩陣創建無向網圖 MGraph* CreateMGraph() {MGraph* mGraph = (MGraph*)malloc(sizeof(MGraph));int vertexNum, edgeNum;printf("請輸入頂點數和邊數(請用逗號隔開):");scanf("%d,%d", &vertexNum, &edgeNum);mGraph->vertexNum = vertexNum;mGraph->edgeNum = edgeNum;getchar();//去除上次輸入的換行printf("請輸入頂點值:");//輸入頂點值for (int i = 0; i < vertexNum; i++){scanf("%c", &mGraph->vertex[i]);}//初始化 邊集for (int i = 0; i < vertexNum; i++){for (int j = 0; j < vertexNum; j++){mGraph->edge[i][j] = INFINITY;}}//輸入邊值for (int i = 0; i < edgeNum; i++){int i, j, w;printf("請輸入(Vi,Vj)對應的頂點的下標和權值(用逗號隔開):");scanf("%d,%d,%d", &i, &j, &w);mGraph->edge[i][j] = mGraph->edge[j][i] = w;//無向圖為對稱矩陣}return mGraph; }

鄰接矩陣的深度優先遍歷

先說下圖的遍歷：從圖中某一頂點出發訪遍圖中其余頂點，且使每個頂點僅被訪問一次，這一過程就叫做圖的遍歷（Traversing Graph）。那么何為深度優先遍歷呢？深度優先遍歷（Depth First Search），也有稱為深度優先搜索，簡稱DFS。想一想 因為在圖中有很多條道路，怎么訪問一個地方后不再訪問訪問過的頂點呢？其實有2種方案，就對應我們的2種遍歷方式。一種方案：圖中每個頂點 相連著有很多頂點，我們可以從某個結點v出發，訪問此結點，然后訪問v的未訪問過的鄰階點，然后繼續訪問該結點 的未訪問過的鄰接點，有點類似順藤摸瓜的意思，一直深入，直到圖中所有的頂點都被訪問到為止。是不是感覺可以用遞歸呢？肯定要用一個全局數組來記錄頂點是否訪問過唄，訪問過下次就不訪問了唄。下面是鄰接矩陣的深度優先遍歷：

void DFTMGraph(MGraph* graph,int vexIndex) {//訪問過 就不再進行訪問if (g_visited[vexIndex] == TRUE){return;}g_visited[vexIndex] = TRUE;//對訪問到的結點進行操作VisitMGraphVertex(graph->vertex[vexIndex]);for (int j = 0; j < graph->vertexNum; j++){//權值不為零，繼續訪問下一個結點if (graph->edge[vexIndex][j] != 0){DFTMGraph(graph, j);}}return; }//深度優先遍歷 void TraverseMGraph(MGraph* graph) {if (NULL == graph){return;}//設置結點都沒有訪問過for (int i = 0; i < graph->vertexNum; i++){g_visited[i] = FALSE;}for (int i = 0; i < graph->vertexNum; i++){if (g_visited[i] == FALSE){DFTMGraph(graph,i);}}return; }

鄰接矩陣的廣度優先遍歷

廣度優先遍歷（Breath First Search），又稱為廣度優先搜索，檢測BFS。它很類似層序遍歷，從圖中某結點v出發，將該結點沒有訪問過的鄰接點訪問一遍，然后訪問已經訪問過結點的未訪問過的鄰結點訪問一遍，直到圖中的所有結點被訪問完。下面是鄰接矩陣的廣度優先遍歷：

//廣度優先遍歷 鄰接矩陣 void BFTMGraph(MGraph* graph) {Queue queue;InitQueue(&queue);for (int i = 0; i < graph->vertexNum; i++){g_visited[i] = FALSE;}for (int i = 0; i < graph->vertexNum; i++){if (g_visited[i] == FALSE){g_visited[i] = TRUE;VisitMGraphVertex(graph->vertex[i]);EnQueue(&queue,i);//當前結點下標入隊//為什么這里要循環出隊呢？出隊獲取已經訪問過結點的下標，在內層的for繼續訪問相關聯結點，將減少外層for循環進入if次數while (!EmptyQueue(&queue)){int vexIndex;DeQueue(&queue, &vexIndex);//訪問過的結點下標出隊for (int j = 0; j < graph->vertexNum; j++){//將該節點的連接的結點且沒有被訪問過的結點訪問，然后入隊if (graph->edge[vexIndex][j] != 0 && graph->edge[vexIndex][j] != INFINITY && g_visited[j] == FALSE){g_visited[j] = TRUE;VisitMGraphVertex(graph->vertex[j]);EnQueue(&queue, graph->vertex[j]);}}}}}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; }

MGraph.c

#define _CRT_SECURE_NO_WARNINGS #include <stdio.h> #include <stdlib.h> #include "Queue.h" #define MAX_VERTEX 100 #define INFINITY 65535 typedef char VertexType;//頂點類型 typedef int EdgeType;//邊上權值類型 typedef struct {VertexType vertex[MAX_VERTEX];//頂點集EdgeType edge[MAX_VERTEX][MAX_VERTEX];//邊集int vertexNum, edgeNum;//頂點數，邊數 }MGraph; Boolean g_visited[MAX_VERTEX] = {0};//全局變量 頂點訪問標志位數組 //鄰接矩陣創建無向網圖 MGraph* CreateMGraph() {MGraph* mGraph = (MGraph*)malloc(sizeof(MGraph));int vertexNum, edgeNum;printf("請輸入頂點數和邊數(請用逗號隔開):");scanf("%d,%d", &vertexNum, &edgeNum);mGraph->vertexNum = vertexNum;mGraph->edgeNum = edgeNum;getchar();//去除上次輸入的換行printf("請輸入頂點值:");//輸入頂點值for (int i = 0; i < vertexNum; i++){scanf("%c", &mGraph->vertex[i]);}//初始化 邊集for (int i = 0; i < vertexNum; i++){for (int j = 0; j < vertexNum; j++){mGraph->edge[i][j] = INFINITY;}}//輸入邊值for (int i = 0; i < edgeNum; i++){int i, j, w;printf("請輸入(Vi,Vj)對應的頂點的下標和權值(用逗號隔開):");scanf("%d,%d,%d", &i, &j, &w);mGraph->edge[i][j] = mGraph->edge[j][i] = w;//無向圖為對稱矩陣}return mGraph; } //打印鄰接矩陣的無向圖數據 void PrintMGraph(MGraph* mGraph) {printf("頂點數組數據:\n");for (int i = 0; i < mGraph->vertexNum; i++){printf("%c ", mGraph->vertex[i]);}printf("\n邊點數組數據:\n");for (int i = 0; i < mGraph->vertexNum; i++){for (int j = 0; j < mGraph->vertexNum; j++){printf("%d\t", mGraph->edge[i][j]);}printf("\n");} } //訪問頂點元素 void VisitMGraphVertex(VertexType data) {printf("%c ",data);return; }void DFTMGraph(MGraph* graph,int vexIndex) {//訪問過 就不再進行訪問if (g_visited[vexIndex] == TRUE){return;}g_visited[vexIndex] = TRUE;//對訪問到的結點進行操作VisitMGraphVertex(graph->vertex[vexIndex]);for (int j = 0; j < graph->vertexNum; j++){//權值不為零，繼續訪問下一個結點if (graph->edge[vexIndex][j] != 0){DFTMGraph(graph, j);}}return; }//深度優先遍歷 void TraverseMGraph(MGraph* graph) {if (NULL == graph){return;}//設置結點都沒有訪問過for (int i = 0; i < graph->vertexNum; i++){g_visited[i] = FALSE;}for (int i = 0; i < graph->vertexNum; i++){if (g_visited[i] == FALSE){DFTMGraph(graph,i);}}return; } //廣度優先遍歷 鄰接矩陣 void BFTMGraph(MGraph* graph) {Queue queue;InitQueue(&queue);for (int i = 0; i < graph->vertexNum; i++){g_visited[i] = FALSE;}for (int i = 0; i < graph->vertexNum; i++){if (g_visited[i] == FALSE){g_visited[i] = TRUE;VisitMGraphVertex(graph->vertex[i]);EnQueue(&queue,i);//當前結點下標入隊//為什么這里要循環出隊呢？出隊獲取已經訪問過結點的下標，在內層的for繼續訪問相關聯結點，將減少外層for循環進入if次數while (!EmptyQueue(&queue)){int vexIndex;DeQueue(&queue, &vexIndex);//訪問過的結點下標出隊for (int j = 0; j < graph->vertexNum; j++){//將該節點的連接的結點且沒有被訪問過的結點訪問，然后入隊if (graph->edge[vexIndex][j] != 0 && g_visited[j] == FALSE){g_visited[j] = TRUE;VisitMGraphVertex(graph->vertex[j]);EnQueue(&queue, graph->vertex[j]);}}}}}return; }int main(int argc, char *argv[]) {MGraph* mGraph = CreateMGraph();PrintMGraph(mGraph);printf("深度優先遍歷鄰接矩陣:\n");TraverseMGraph(mGraph);printf("\n廣度優先遍歷鄰接矩陣:\n");BFTMGraph(mGraph);printf("\n");return 0; }

代碼運行檢測

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

代碼運行結果：

總結

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

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