7.2 圖的基礎綜合運算(鄰接表存儲)

實驗7.2 圖的基礎綜合運算(鄰接表存儲)

實驗目的

• 了解鄰接表存儲方式方法
• 了解連通圖以鄰接表存儲時的深度-廣度優先搜尋周遊算法及實作

說明

• 參考代碼裡面固定建立隊列和頂點數組容量為100, 鄰接矩陣固定 100*100, 有點浪費記憶體，改成動态建立了
• 代碼裡面很多變量名隻有單個字元，讀起來不友善，都改成有意義的名字了

• tu2.txt

  需要放到與編譯後可執行檔案相同的路徑下(不是源代碼目錄)，對于使用 VisualStudio 的同學，可執行檔案一般在你項目路徑下的

  Debug

  檔案夾内

代碼

tu2.txt

該檔案格式為：
結點數 邊數
結點名字(char)
邊1(結點1 結點2)
邊2
...
           

如

4 4
A B C D
A B
A C
A D
B D
           

Graph_AdjList.cpp

#include <iostream>
#include <fstream>
using namespace std;

#define OK 1
#define ERROR 0
#define OVERFLOW -2

#define GRAPH_FILE "./tu2.txt" // 輸入的檔案路徑

typedef char VerTexType; //假設頂點的資料類型為字元型
typedef int ArcType;	 //假設邊的權值類型為整型

struct ArcNode
{					  //邊結點
	int adjvex;		  //該邊所指向的頂點的位置
	ArcNode *nextarc; //指向下一條邊的指針
};

struct VNode
{
	VerTexType data;   //頂點資訊
	ArcNode *firstarc; //指向第一條依附該頂點的邊的指針
};

struct ALGraph
{
	VNode *vertices;	//鄰接表
	int vexnum, arcnum; //圖的目前頂點數和邊數
};

struct SqQueue
{
	size_t capacity; // 最大大小
	ArcType *base;	 //初始化的動态配置設定存儲空間
	int front;		 //頭指針，若隊列不空，指向隊頭元素
	int rear;		 //尾指針，若隊列不空，指向隊尾元素的下一個位置
};

// 初始化循環隊列
int InitQueue(SqQueue &Q, size_t size)
{
	Q.capacity = size;
	Q.base = new ArcType[size];
	if (!Q.base)
		return OVERFLOW;
	Q.front = Q.rear = 0;
	return OK;
}

// 銷毀循環隊列
void DestroyQueue(SqQueue &Q)
{
	delete[] Q.base;
}

// 判空
bool QueueEmpty(SqQueue &Q)
{
	return Q.front == Q.rear;
}

// 判滿
bool QueueFull(SqQueue &Q)
{
	return (Q.rear + 1) % Q.capacity == Q.front;
}

// 入隊 e
int EnQueue(SqQueue &Q, ArcType e)
{
	if (QueueFull(Q))
		return ERROR;
	Q.base[Q.rear] = e;
	Q.rear = (Q.rear + 1) % Q.capacity;
	return OK;
}

// 出隊
int DeQueue(SqQueue &Q, ArcType &u)
{
	if (QueueEmpty(Q))
		return ERROR;
	u = Q.base[Q.front];
	Q.front = (Q.front + 1) % Q.capacity;
	return OK;
}

// 找到結點 v 在頭結點清單的下标
int LocateVex(ALGraph &G, VerTexType v)
{
	for (int i = 0; i < G.vexnum; ++i)
		if (G.vertices[i].data == v)
			return i;
	return -1;
}

// 采用鄰接表表示法，建立無向圖G
void CreateUDG(ALGraph &G)
{
	fstream file;
	file.open(GRAPH_FILE);
	if (!file)
	{
		cout << "沒有找到圖檔案!" << endl;
		exit(ERROR);
	}

	file >> G.vexnum >> G.arcnum;	  // 輸入總頂點數，總邊數
	G.vertices = new VNode[G.vexnum]; // 建立表頭結點清單

	for (int i = 0; i < G.vexnum; ++i)
	{
		file >> G.vertices[i].data;		  // 輸入頂點值
		G.vertices[i].firstarc = nullptr; // 初始化表頭結點的指針域為空
	}

	for (int k = 0; k < G.arcnum; ++k)
	{
		VerTexType v1, v2;
		file >> v1 >> v2;		  // 輸入一條邊依附的兩個頂點值
		int i = LocateVex(G, v1); // 找到這兩個頂點的下标
		int j = LocateVex(G, v2);

		ArcNode *p1 = new ArcNode; // 建立一個邊結點, 插到 i 号下标結點的邊表上
		p1->adjvex = j;
		p1->nextarc = G.vertices[i].firstarc;
		G.vertices[i].firstarc = p1;

		// 相對應的，j結點的邊連結清單也要插入一個邊結點，有向圖不用下面這個
		ArcNode *p2 = new ArcNode;
		p2->adjvex = i;
		p2->nextarc = G.vertices[j].firstarc;
		G.vertices[j].firstarc = p2;
	}
}

// 深度優先遞歸周遊連通圖G
void DFS(ALGraph &G, int vex_index, bool *visited)
{
	cout << G.vertices[vex_index].data << '\t' << flush; // 通路下标為 vex_index 的結點
	visited[vex_index] = true;
	ArcNode *p = G.vertices[vex_index].firstarc; // p 指向下标為 vex_index 結點的邊連結清單的第一個邊結點
	while (p)
	{
		int adj_vex_index = p->adjvex;		// 與它相鄰的第一個結點的下标
		if (!visited[adj_vex_index])		// 如果沒有通路過
			DFS(G, adj_vex_index, visited); // 繼續遞歸周遊它
		p = p->nextarc;						// 繼續周遊下一條邊
	}
}

// 廣度優先周遊
void BFS(ALGraph &G, int vex_index)
{
	bool *visited = new bool[G.vexnum]{}; // 建立 visited 數組記錄已經通路過的結點下标

	cout << G.vertices[vex_index].data << '\t'; // 通路下标為 vex_index 的結點
	visited[vex_index] = true;

	SqQueue Q;
	int visited_index;
	InitQueue(Q, G.vexnum); // 建立一個長度為結點數的隊列
	EnQueue(Q, vex_index);	// 通路過的下标入隊
	while (!QueueEmpty(Q))
	{
		DeQueue(Q, visited_index);						 // 取出第一個通路過的結點
		ArcNode *p = G.vertices[visited_index].firstarc; // 找到它的第一個邊結點
		while (p)
		{
			if (!visited[p->adjvex]) // 如果它存在且為被通路
			{
				cout << G.vertices[p->adjvex].data << '\t'; // 通路它
				visited[p->adjvex] = true;
				EnQueue(Q, p->adjvex); // 通路過的下标入隊
			}
			p = p->nextarc; // 沿着鄰接點連結清單一直往下周遊
		}
	}
	delete[] visited;
}

// 顯示圖
void Display(ALGraph &G)
{
	for (int i = 0; i < G.vexnum; ++i)
	{
		VNode temp = G.vertices[i];
		ArcNode *p = temp.firstarc;
		if (!p)
			cout << G.vertices[i].data << "|" << endl;
		else
		{
			cout << temp.data << "|";
			while (p)
			{
				cout << " -> ";
				cout << G.vertices[p->adjvex].data;
				p = p->nextarc;
			}
		}
		cout << endl;
	}
}

// 銷毀圖
void DestroyGraph(ALGraph &G)
{
	for (int i = 0; i < G.vexnum; i++)
	{
		ArcNode *p = G.vertices[i].firstarc;
		while (p)
		{
			ArcNode *t = p;
			delete t;
			p = p->nextarc;
		}
	}
	delete[] G.vertices;
}

int main()
{
	cout << "************算法6.6　采用鄰接表表示圖的深度優先搜尋周遊**************" << endl;
	ALGraph G;
	CreateUDG(G);
	cout << "無向連通圖G建立完成！" << endl;
	cout << "**************鄰接表表示無向連通圖*******************" << endl;
	Display(G);
	cout << "********************************" << endl;
	VerTexType vex_name;
	int i;
	do
	{
		cout << "請輸入周遊連通圖的起始點: ";
		cin >> vex_name;
		for (i = 0; i < G.vexnum; ++i)
		{
			if (vex_name == G.vertices[i].data)
				break;
			else
				cout << "該點不存在，請重新輸入！" << endl;
		}
	} while (i >= G.vexnum);

	cout << "深度優先搜尋周遊連通圖結果：" << endl;
	bool *visited = new bool[G.vexnum]{}; // 動态建立visited數組儲存結點通路狀态
	DFS(G, i, visited);
	delete[] visited;
	cout << "\n廣度優先搜尋周遊連通圖結果：" << endl;
	BFS(G, i);
	cout << endl;
	DestroyGraph(G);
}
           

運作截圖

OOP 版

還沒寫...