資料結構與算法導論(C++)連載（八）--圖（鄰接矩陣存儲和鍊式鄰接表存儲）

圖-表示多對多的關系，一組頂點V（一個非空有限頂點集合），一組邊E（一個有限邊集合），邊上有權重稱為網絡。用鄰接矩陣（稠密圖）或者鄰接表（稀疏圖）表示一個圖。

一、鄰接矩陣表示：

在Graph_M.h中：

#include"iostream"

using namespace std;

/******************鄰接矩陣表示圖**************************/

#define MaxVertexNum 128
#define WeightType int
typedef int Vertex;
typedef struct GNode *PtrToGNode;
struct GNode {
int Nv; //頂點數
int Ne; //邊數
WeightType G[MaxVertexNum][MaxVertexNum]; //存儲頂點的資料
};
typedef PtrToGNode MGraph;

typedef struct ENode *PtrToENode;
struct ENode
{
Vertex V1, V2; //有向邊<V1,V2>
WeightType Weight; //權重
};
typedef PtrToENode Edge;

MGraph CreateGraph(int VertexNum);
void InsertEdge(MGraph Graph, Edge E);
MGraph BuildGraph();
void OutputGraph(MGraph Graph);

在Graph_M.cpp中:

#include"Graph_M.h"

/******************鄰接矩陣表示圖**************************/

MGraph CreateGraph(int VertexNum)
{
	Vertex V, W;
	MGraph Graph;
	Graph = (MGraph)malloc(sizeof(struct GNode));
	Graph->Nv = VertexNum;
	Graph->Ne = 0;

	for (V = 0; V < Graph->Nv; V++)
		for (W = 0; W < Graph->Nv; W++)
			Graph->G[V][W] = 0;
	return Graph;
}

void InsertEdge(MGraph Graph, Edge E)
{
	Graph->G[E->V1][E->V2] = E->Weight;
	/*若是無向圖，還要插入邊<V2,V1>*/
	Graph->G[E->V2][E->V1] = E->Weight;
}

MGraph BuildGraph()
{
	MGraph Graph; Edge E;
	Vertex V; int Nv, i;
	cout << "Input Nv:\n";
	cin >> Nv;
	Graph = CreateGraph(Nv);
	cout << "Input Ne:\n";
	cin >> Graph->Ne;
	if (Graph->Ne !=0)
	{
		E = (Edge)malloc(sizeof(struct ENode));
		for (i = 0; i < Graph->Ne; i++)
		{
			cout << "Input Edge of V1,V2,weight:\n";
			cin >> E->V1 >> E->V2 >> E->Weight;
			InsertEdge(Graph, E);
		}
	}
	/*如果頂點有資料的話，需要在這裡讀入資料*/
	//for (V = 0; V < Graph->Nv; V++)
	//	cin >> Graph->Data[V];
	return Graph;
}

void OutputGraph(MGraph Graph)
{
	int i,j;
	for (i = 0; i < Graph->Nv; i++)
		for (j = 0; j < Graph->Nv; j++)
		{
			if (Graph->G[i][j] != 0)
				cout << i << " " << j << "-" << Graph->G[i][j]<<"\n";
		}
}

運作結果：

資料結構與算法導論(C++)連載（八）--圖（鄰接矩陣存儲和鍊式鄰接表存儲）

二、鄰接表表示

先引入隊列的實作，因為在廣度優先搜尋中需要隊列。

可參考本連載中隊列的實作：https://blog.csdn.net/qq_28821995/article/details/89447884

在Graph_T.h:

#include"iostream"


using namespace std;

/******************鄰接表表示圖**************************/

#define MaxVertexNum 128
#define WeightType int
typedef int Vertex;
typedef struct AdjVNode *PtrToAdjVNode;
struct AdjVNode {
	Vertex AdjV; /* 鄰接點下标 */
	WeightType Weight; /* 邊權重 */
	PtrToAdjVNode Next;
};

typedef struct Vnode {
	PtrToAdjVNode FirstEdge;
	//DataType Data; /* 存頂點的資料 */
} AdjList[MaxVertexNum];

typedef struct ENode *PtrToENode;
struct ENode
{
	Vertex V1, V2; //有向邊<V1,V2>
	WeightType Weight; //權重
};
typedef PtrToENode Edge;

typedef struct GNode *PtrToGNode;
struct GNode
{
	int Nv, Ne; //頂點數，邊數
	int Visited[MaxVertexNum];  //周遊時用來标記各個頂點是否通路
	AdjList G; //鄰接表
};
typedef PtrToGNode LGraph;
/* 以鄰接表方式存儲的圖類型 */

typedef struct GShort *PtrGSshort;
struct GShort
{
	int path[MaxVertexNum], dist[MaxVertexNum]; //尋找最短路徑時要使用的
};

LGraph CreateGraph(int VertexNum);
void InsertEdge(LGraph Graph, Edge E);
LGraph BuildGraph();
void DFS(LGraph G, int i);
void BFS_0(LGraph G);
void BFS(LGraph G, int V);
void BFS_Unweighted(LGraph G, Vertex S);

在Graph_T.cpp中：

#include"Graph_T.h"
#include"QueueList.h"
/******************鄰接表表示圖**************************/

LGraph CreateGraph(int VertexNum)
{
	Vertex V, W;
	LGraph Graph;
	Graph = (LGraph)malloc(sizeof(struct GNode));
	Graph->Nv = VertexNum;
	Graph->Ne = 0;
	//頂點編号從0開始的 一直到Nv-1
	for (V = 0; V < Graph->Nv; V++)
		Graph->G[V].FirstEdge = NULL;
	for (size_t i = 0; i < Graph->Nv; i++)
	{
		Graph->Visited[i] = 0;
	}
	return Graph;
}

void InsertEdge(LGraph Graph, Edge E)
{
	PtrToAdjVNode NewNode;
	/************************插入邊<V1,V2>************************/
	NewNode = (PtrToAdjVNode)malloc(sizeof(struct AdjVNode));
	NewNode->AdjV = E->V2;
	NewNode->Weight = E->Weight;
	NewNode->Next = Graph->G[E->V1].FirstEdge;
	Graph->G[E->V1].FirstEdge = NewNode;
	/************************若是無向圖，還要插入邊<V2,V1>************************/
	NewNode = (PtrToAdjVNode)malloc(sizeof(struct AdjVNode));
	NewNode->AdjV = E->V1;
	NewNode->Weight = E->Weight;
	NewNode->Next = Graph->G[E->V2].FirstEdge;
	Graph->G[E->V2].FirstEdge = NewNode;
}

LGraph BuildGraph()
{
	LGraph Graph; Edge E;
	Vertex V; int Nv, i;
	cout << "Input Nv:\n";
	cin >> Nv;
	Graph = CreateGraph(Nv);
	cout << "Input Ne:\n";
	cin >> Graph->Ne;
	if (Graph->Ne != 0)
	{
		E = (Edge)malloc(sizeof(struct ENode));
		for (i = 0; i < Graph->Ne; i++)
		{
			cout << "Input Edge of V1,V2,weight:\n";
			cin >> E->V1 >> E->V2 >> E->Weight;
			InsertEdge(Graph, E);
		}
	}
	/*如果頂點有資料的話，需要在這裡讀入資料*/
	//for (V = 0; V < Graph->Nv; V++)
	//	cin >> Graph->Data[V];
	return Graph;
}

void DFS(LGraph G, int i)
{
	PtrToAdjVNode W;
	cout << i << "-";
	G->Visited[i] = 1;
	for (W = G->G[i].FirstEdge; W; W = W->Next)
		if (!G->Visited[W->AdjV])
			DFS(G, W->AdjV);
	return;
}

void BFS_0(LGraph G)
{
	Queue Q = NULL;
	PtrToAdjVNode W;
	Q = MakeEmptyQ();
	Vertex U, V;
	for (U = 0; U<G->Nv; ++U)
		if (!G->Visited[U])  //頂點未通路
		{
			G->Visited[U] = 1;
			cout << U << "-";
			AddQ(Q, U);
			while (!IsEmptyQ(Q))
			{
				V = DeleteQ(Q); //出隊列
				for (W = G->G[V].FirstEdge; W; W = W->Next)
					if (!G->Visited[W->AdjV]) {
						G->Visited[W->AdjV] = 1;
						cout << W->AdjV << "-";
						AddQ(Q, W->AdjV);
					}
			} //while
		} //if
}

void BFS(LGraph G, int V)
{
	Queue Q = NULL;
	PtrToAdjVNode W;
	Q = MakeEmptyQ();
	G->Visited[V] = 1;
	AddQ(Q, V);
	while (!IsEmptyQ(Q))
	{
		V = DeleteQ(Q);
		cout << V << "-";
		for (W = G->G[V].FirstEdge; W; W = W->Next)
			if (!G->Visited[W->AdjV]) {
				G->Visited[W->AdjV] = 1;
				AddQ(Q, W->AdjV);
			}
	}
}

void BFS_Unweighted(LGraph G, Vertex S)
{
	int i;
	Vertex V;
	Queue Q = NULL;
	PtrToAdjVNode W;
	PtrGSshort GS;
	GS = (PtrGSshort)malloc(sizeof(struct GShort));
	for (i = 0; i < G->Nv; i++)
	{
		GS->dist[i] = -1; //S到W的最短路徑
		GS->path[i] = 0; //S到W的路上經過的某頂點
	}
	GS->dist[S] = 0;
	Q = MakeEmptyQ();
	AddQ(Q, S);
	while (!IsEmptyQ(Q))
	{
		V = DeleteQ(Q);
		/*cout << V << "-";*/
		for (W = G->G[S].FirstEdge; W; W = W->Next)
			if (GS->dist[W->AdjV] == -1) {
				GS->dist[W->AdjV] = GS->dist[V] + 1;  //0-代表直接相連，1-代表中間隔一個頂點...
				GS->path[W->AdjV] = V;
				AddQ(Q, W->AdjV);
			}
	}
}

運作結果：

資料結構與算法導論(C++)連載（八）--圖（鄰接矩陣存儲和鍊式鄰接表存儲）

資料結構與算法導論(C++)連載（八）--圖（鄰接矩陣存儲和鍊式鄰接表存儲）

繼續閱讀

[轉]ISUP信令的IAM消息詳細内容

swmm與lisflood-fp源碼如何一起編譯 CMake指令

Windows下VS開發環境環境安裝工程項目設定關于Debug和Release的提示

一文看懂字元串的加減乘除

C++ 第十五周報告1--《冒泡法排序》

C++實作簡單順序表

筆試面試題目：滑動視窗(二)

PAT 1089 Insert or Merge[難]

交通/城市相關的公開的資料集上學時整理的Xie et al., 2020收集的

資料結構與算法（27）——排序（二）

C經典書籍筆記——C陷阱與缺陷②(文法陷阱之優先級)一、錯誤案列二、優先級規律

GitHub連夜封殺！這份阿裡 10W 字内部 Java 字面試手冊到底有多強？

線性表之順序表的實作

C++判斷素數、求最大公約數代碼判斷一個數是否為素數求兩個數的最大公約數

SequoiaDB巨杉資料庫C++驅動概述

Linux裝置模型（中）之上層容器