基礎(chǔ)介紹

圖的數(shù)據(jù)結(jié)構(gòu)

圖主要由頂點(diǎn)和邊組成


無向邊用（）

有向邊用<>

入度：
一頂點(diǎn)V為頭的弧的數(shù)目為入度，
出度：
以其為尾的數(shù)目為出度。

連通圖

連通圖生成樹

圖的定義與術(shù)語總結(jié)

圖的基本操作

圖的存儲結(jié)構(gòu) 鄰接矩陣

鄰接矩陣圖的代碼

#include "stdio.h" #include "stdlib.h" #include "io.h" #include "math.h" #include "time.h"#define OK 1 #define ERROR 0 #define TRUE 1 #define FALSE 0 #define MAXVEX 100 /* 最大頂點(diǎn)數(shù)，應(yīng)由用戶定義 */ #define INFINITY 65535typedef int Status; /* Status是函數(shù)的類型,其值是函數(shù)結(jié)果狀態(tài)代碼，如OK等 */ typedef char VertexType; /* 頂點(diǎn)類型應(yīng)由用戶定義 */ typedef int EdgeType; /* 邊上的權(quán)值類型應(yīng)由用戶定義 */typedef struct {VertexType vexs[MAXVEX];EdgeType arc[MAXVEX][MAXVEX];int numNodes;int numEdges; }MGraph;//建立無向網(wǎng)圖的鄰接矩陣表示 void CreateMGraph(MGraph* G) {int i;int j;int k;int w;printf("輸入頂點(diǎn)數(shù)和邊數(shù): \n");scanf_s("%d,%d", &G->numNodes, &G->numEdges);for (int i = 0; i < G->numNodes; i++)scanf_s(&G->vexs[i]);for (int i = 0; i < G->numNodes; i++){for (int j = 0; j < G->numNodes; j++){G->arc[i][j] = INFINITY;/* 鄰接矩陣初始化 */}}/* 讀入numEdges條邊，建立鄰接矩陣 */for (int k = 0; k < G->numEdges; k++){printf("輸入邊(vi,vj)上的下標(biāo)i，下標(biāo)j和權(quán)w:\n");scanf_s("%d,%d,%d", &i, &j, &w); /* 輸入邊(vi,vj)上的權(quán)w */G->arc[i][j] = w;G->arc[j][i] = G->arc[i][j]; /* 因?yàn)槭菬o向圖，矩陣對稱 */} } int main(void) {MGraph G;CreateMGraph(&G);return 0; }

鄰接表存儲結(jié)構(gòu)

#include "stdio.h" #include "stdlib.h" #include "io.h" #include "math.h" #include "time.h"#define OK 1 #define ERROR 0 #define TRUE 1 #define FALSE 0 #define MAXVEX 100 /* 最大頂點(diǎn)數(shù),應(yīng)由用戶定義 */typedef int Status; /* Status是函數(shù)的類型,其值是函數(shù)結(jié)果狀態(tài)代碼,如OK等 */ typedef char VertexType; /* 頂點(diǎn)類型應(yīng)由用戶定義 */ typedef int EdgeType; /* 邊上的權(quán)值類型應(yīng)由用戶定義 */typedef struct EdgeNode // 邊表節(jié)點(diǎn) {int adjvex; /* 鄰接點(diǎn)域,存儲該頂點(diǎn)對應(yīng)的下標(biāo) */EdgeType info;struct EdgeNode *next;/* 鏈域,指向下一個(gè)鄰接點(diǎn) */ }EdgeNode;typedef struct VertexNode {VertexType data; //頂點(diǎn)域EdgeNode* firstedge;//邊表頭指針 }VertexNode,AdjList[MAXVEX];typedef struct {AdjList adjList;int numNodes;//頂點(diǎn)數(shù)目int numEdges;//邊表數(shù)目 }GraphAdjList;// 建立圖的鄰接表結(jié)構(gòu) void CreateALGraph(GraphAdjList* G) {EdgeNode* e;printf("輸入頂點(diǎn)數(shù)和邊數(shù):\n");scanf_s("%d,%d", &G->numNodes, &G->numEdges); /* 輸入頂點(diǎn)數(shù)和邊數(shù) */for (int i = 0; i < G->numNodes; i++) /* 讀入頂點(diǎn)信息,建立頂點(diǎn)表 */{scanf_s(&G->adjList[i].data); /* 輸入頂點(diǎn)信息 */G->adjList[i].firstedge = NULL; /* 將邊表置為空表 */}for (int k = 0; k < G->numEdges; k++)/* 建立邊表 */{int i;int j;printf("輸入邊(vi,vj)上的頂點(diǎn)序號:\n");scanf_s("%d,%d", &i, &j); /* 輸入邊(vi,vj)上的頂點(diǎn)序號 */e = new EdgeNode();e->adjvex = j;e->next = G->adjList[i].firstedge;G->adjList[i].firstedge = e; //完成鏈表連接} }int main() {GraphAdjList G;CreateALGraph(&G);return 0; }

總結(jié)

以上是生活随笔為你收集整理的大话数据结构16：图的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。