大体与上次实验相同, 特点为图是邻接表存储结构
-- 博客后半部分有程序的所有代码 --
1, 图邻接表存储结构表示及基本操作算法实现
所加载的库函数或常量定义及类的定义:
- #include "SeqQueue.h"
- const int MaxVertices = 100;
- const int MaxWeight=10000;
(1) 邻接表存储结构类定义:
- struct EdgeType
- {
- int dest;
- DistT weight;
- EdgeType *next;
- EdgeType(){};
- EdgeType(int d, DistT w): dest(d), weight(w), next(NULL){}
- };
- struct ItemType
- {
- VerT data;
- EdgeType *adj;
- };
- class AdjTWGraph
- {
- private:
- ItemType Vertices[MaxVertices];
- int numVertices;
- double numOfEdges;
- void DepthFirstSearch(const int v, int visited[]);
- void BroadFirstSearch(const int v, int visited[]);
- public:
- AdjTWGraph(void);
- ~AdjTWGraph(void);
- int NumOfVertices(void)
- {return numVertices;}
- double NumOfEdges(void)
- {return numOfEdges;}
- VerT GetValue(const int i);
- int GetWeight(const int v1, const int v2);
- void Show(); // 输出邻接矩阵结果
- void InsertVertex(const VerT &vertex);
- void InsertWayEdge(const int v1, const int v2, int weight);
- void InsertNoWayEdge(const int v1, const int v2, int weight);
- void DeleteVertex(const int v);
- void DeleteEdge(const int v1, const int v2);
- int GetFirstNeighbor(const int v);
- int GetNextNeighbor(const int v1, const int v2);
- void DepthFirstSearch();
- void BroadFirstSearch();
- };
(2) 创建邻接表算法
创建无向网邻接表算法:
- void CreatNoWayWeb(AdjTWGraph &G, DataType V[],int n,RowColWeight E[], int e)
- {
- // 在图 G 中插入 n 个顶点
- for(int i = 0; i <n; i++)
- G.InsertVertex(V[i]);
- // 在图 G 中插入 e 条边
- for(int k = 0; k < e; k++)
- {
- if(E[k].row>E[k].col)
- {
- cout<<"无向网参数输入错误";
- exit(0);
- }
- G.InsertNoWayEdge(E[k].row, E[k].col, E[k].weight);
- G.InsertNoWayEdge(E[k].col, E[k].row, E[k].weight);
- }
- }
创建有向网邻接表算法:
- void CreatWayWeb(AdjTWGraph &G, DataType V[], int n,RowColWeight E[],int e)
- // 在图 G 中插入 n 个顶点 V 和 e 条边 E
- {
- // 在图 G 中插入 n 个顶点
- for(int i = 0; i <n; i++)
- G.InsertVertex(V[i]);
- // 在图 G 中插入 e 条边
- for(int k = 0; k < e; k++)
- G.InsertWayEdge(E[k].row, E[k].col, E[k].weight);
- }
(3) 输出邻接表结果算法
- void AdjTWGraph::Show()
- {
- for(int i=0;i<numVertices;i++)
- {
- for(int j=0;j<numVertices;j++)
- {
- int a=GetWeight(i,j);
- if(a==MaxWeight)
- cout<<"∞";
- else
- cout<<a<<" ";
- }
- cout<<endl;
- }
- }
测试结果粘贴如下:
2, 图的遍历递归算法
(1)(存储结构为邻接表) 深度优先遍历算法 - 递归算法
- void AdjTWGraph::DepthFirstSearch()
- {
- int *visited = new int[NumOfVertices()];
- for(int i = 0; i < NumOfVertices(); i++) visited[i] = 0;
- for(int i = 0; i < NumOfVertices(); i++)
- if(! visited[i])
- DepthFirstSearch(i, visited);
- delete []visited;
- }
- void AdjTWGraph::DepthFirstSearch(const int v, int visited[])
- {
- cout<<GetValue(v)<<" ";
- visited[v] = 1;
- int w = GetFirstNeighbor(v);
- while(w != -1)
- {
- if(! visited[w])
- DepthFirstSearch(w, visited);
- w = GetNextNeighbor(v, w);
- }
- }
测试结果粘贴如下:
- int main()
- {
- AdjTWGraph g,f;
- char a[] = {'A','B','C','D','E'};
- char b[] = {'A','B','C','D','E','F'};
- RowColWeight r1[] ={{0,1,10},{0,4,20},{1,3,30},{2,1,40},{3,2,50},{2,4,25}};
- RowColWeight r2[] ={{0,1,10},{0,4,20},{1,3,30},{1,2,40},{2,3,50},{4,5,15},{3,4,12}};
- int n1,n2,e1,e2;
- n1=sizeof(a)/sizeof(a[0]);
- n2=sizeof(b)/sizeof(b[0]);
- e1=sizeof(r1)/sizeof(r1[0]);
- e2=sizeof(r2)/sizeof(r2[0]);
- CreatWayWeb(g, a, n1, r1, e1); // 创建有向网
- CreatNoWayWeb(f, b, n2, r2, e2); // 创建无向网
- cout<<"有向网:"<<endl;
- cout << "\n 深度优先搜索序列为:";
- g.DepthFirstSearch();
- cout<<"\n\n 无向网"<<endl;
- cout << "\n 深度优先搜索序列为:";
- f.DepthFirstSearch();
- return 0;
- }
有向网 / 无向网的测试结果:
(2) 广度优先遍历算法 (递归算法)
- void AdjTWGraph::BroadFirstSearch()
- {
- int *visited = new int[NumOfVertices()];
- for(int i = 0; i < NumOfVertices(); i++) visited[i] = 0;
- for(int i = 0; i < NumOfVertices(); i++)
- if(!visited[i]) BroadFirstSearch(i, visited);
- delete []visited;
- }
- void AdjTWGraph::BroadFirstSearch(const int v, int visited[])
- {
- VerT u, w;
- SeqQueue queue;
- cout<<GetValue(v)<<" ";
- visited[v] = 1;
- queue.Append(v);
- while(queue.NotEmpty())
- {
- u = queue.Delete();
- w = GetFirstNeighbor(u);
- while(w != -1)
- {
- if(!visited[w])
- {
- cout<<GetValue(w)<<" ";;
- visited[w] = 1;
- queue.Append(w);
- }
- w = GetNextNeighbor(u, w);
- }
- }
- }
测试结果粘贴如下:
- int main()
- {
- AdjTWGraph g,f;
- char a[] = {'A','B','C','D','E'};
- char b[] = {'A','B','C','D','E','F'};
- RowColWeight r1[] ={{0,1,10},{0,4,20},{1,3,30},{2,1,40},{3,2,50},{2,4,25}};
- RowColWeight r2[] ={{0,1,10},{0,4,20},{1,3,30},{1,2,40},{2,3,50},{4,5,15},{3,4,12}};
- int n1,n2,e1,e2;
- n1=sizeof(a)/sizeof(a[0]);
- n2=sizeof(b)/sizeof(b[0]);
- e1=sizeof(r1)/sizeof(r1[0]);
- e2=sizeof(r2)/sizeof(r2[0]);
- CreatWayWeb(g, a, n1, r1, e1); // 创建有向网
- CreatNoWayWeb(f, b, n2, r2, e2); // 创建无向网
- cout<<"有向网:"<<endl;
- cout << "\n 广度优先搜索序列为:";
- g.BroadFirstSearch();
- cout<<"\n\n 无向网"<<endl;
- cout << "\n 广度优先搜索序列为:";
- f.BroadFirstSearch();
- return 0;
- }
有向网 / 无向网的测试结果:
最后附上整体代码结构与结果
- AdjTWGraph.h#include "SeqQueue.h"const int MaxVertices = 100;
- const int MaxWeight = 10000;
- struct EdgeType {
- int dest;
- DistT weight;
- EdgeType * next;
- EdgeType() {};
- EdgeType(int d, DistT w) : dest(d),
- weight(w),
- next(NULL) {}
- };
- struct ItemType {
- VerT data;
- EdgeType * adj;
- };
- class AdjTWGraph {
- private: ItemType Vertices[MaxVertices];
- int numVertices;
- double numOfEdges;
- void DepthFirstSearch(const int v, int visited[]);
- void BroadFirstSearch(const int v, int visited[]);
- public: AdjTWGraph(void);~AdjTWGraph(void);
- int NumOfVertices(void) {
- return numVertices;
- }
- double NumOfEdges(void) {
- return numOfEdges;
- }
- VerT GetValue(const int i);
- int GetWeight(const int v1, const int v2);
- void Show(); // 输出邻接矩阵结果
- void InsertVertex(const VerT & vertex);
- void InsertWayEdge(const int v1, const int v2, int weight);
- void InsertNoWayEdge(const int v1, const int v2, int weight);
- void DeleteVertex(const int v);
- void DeleteEdge(const int v1, const int v2);
- int GetFirstNeighbor(const int v);
- int GetNextNeighbor(const int v1, const int v2);
- void DepthFirstSearch();
- void BroadFirstSearch();
- };
- AdjTWGraph: :AdjTWGraph(void) {
- for (int i = 0; i < MaxVertices; i++) Vertices[i].adj = NULL;
- numVertices = 0;
- numOfEdges = 0;
- }
- AdjTWGraph: :~AdjTWGraph(void) {
- for (int i = 0; i < numVertices; i++) {
- EdgeType * p = Vertices[i].adj,
- *q;
- while (p != NULL) {
- q = p - >next;
- delete p;
- p = q;
- }
- }
- }
- VerT AdjTWGraph: :GetValue(const int i) {
- if (i < 0 || i > numVertices) {
- cout << "参数 i 越界出错!" << endl;
- exit(0);
- }
- return Vertices[i].data;
- }
- int AdjTWGraph: :GetWeight(const int v1, const int v2) {
- if (v1 < 0 || v1 > numVertices || v2 < 0 || v2 > numVertices) {
- cout << "参数 v1 或 v2 越界出错!" << endl;
- exit(0);
- }
- EdgeType * p = Vertices[v1].adj;
- while (p != NULL && p - >dest < v2) p = p - >next;
- if (p == NULL || v2 != p - >dest) {
- return MaxWeight;
- }
- return p - >weight;
- }
- void AdjTWGraph: :InsertVertex(const VerT & vertex) {
- Vertices[numVertices].data = vertex;
- numVertices++;
- }
- void AdjTWGraph: :InsertWayEdge(const int v1, const int v2, int weight) {
- if (v1 < 0 || v1 > numVertices || v2 < 0 || v2 > numVertices) {
- cout << "参数 v1 或 v2 越界出错!" << endl;
- exit(0);
- }
- EdgeType * q = new EdgeType(v2, weight);
- if (Vertices[v1].adj == NULL) Vertices[v1].adj = q;
- else {
- EdgeType * curr = Vertices[v1].adj,
- *pre = NULL;
- while (curr != NULL && curr - >dest < v2) {
- pre = curr;
- curr = curr - >next;
- }
- if (pre == NULL) {
- q - >next = Vertices[v1].adj;
- Vertices[v1].adj = q;
- } else {
- q - >next = pre - >next;
- pre - >next = q;
- }
- }
- numOfEdges++;
- }
- void AdjTWGraph: :InsertNoWayEdge(const int v1, const int v2, int weight)
- // 插入一条起始顶点为 v1, 终止顶点为 v2, 权值为 weight 的边
- {
- if (v1 < 0 || v1 > numVertices || v2 < 0 || v2 > numVertices) {
- cout << "参数 v1 或 v2 越界出错!" << endl;
- exit(0);
- }
- EdgeType * q = new EdgeType(v2, weight);
- if (Vertices[v1].adj == NULL) Vertices[v1].adj = q;
- else {
- EdgeType * curr = Vertices[v1].adj,
- *pre = NULL;
- while (curr != NULL && curr - >dest < v2) {
- pre = curr;
- curr = curr - >next;
- }
- if (pre == NULL) {
- q - >next = Vertices[v1].adj;
- Vertices[v1].adj = q;
- } else {
- q - >next = pre - >next;
- pre - >next = q;
- }
- }
- numOfEdges += 0.5; // 边的个数加 0.5
- }
- void AdjTWGraph: :DeleteVertex(const int v) {
- EdgeType * pre,
- *curr;
- for (int i = 0; i < numVertices; i++) {
- pre = NULL;
- curr = Vertices[i].adj;
- while (curr != NULL && curr - >dest < v) {
- pre = curr;
- curr = curr - >next;
- }
- if (pre == NULL && curr - >dest == v) {
- Vertices[i].adj = curr - >next;
- delete curr;
- numOfEdges--;
- } else if (curr != NULL && curr - >dest == v) {
- pre - >next = curr - >next;
- delete curr;
- numOfEdges--;
- }
- }
- EdgeType * p = Vertices[v].adj,
- *q;
- for (int i = v; i < numVertices - 1; i++) Vertices[i] = Vertices[i + 1];
- numVertices--;
- while (p != NULL) {
- q = p - >next;
- delete p;
- p = q;
- numOfEdges--;
- }
- }
- void AdjTWGraph: :DeleteEdge(const int v1, const int v2) {
- if (v1 < 0 || v1 > numVertices || v2 < 0 || v2 > numVertices) {
- cout << "参数 v1 或 v2 越界出错!" << endl;
- exit(0);
- }
- EdgeType * curr = Vertices[v1].adj,
- *pre = NULL;
- while (curr != NULL && curr - >dest < v2) {
- pre = curr;
- curr = curr - >next;
- }
- if (pre == NULL && curr - >dest == v2) {
- Vertices[v1].adj = curr - >next;
- delete curr;
- numOfEdges--;
- } else if (pre != NULL && curr - >dest == v2) {
- pre - >next = curr - >next;
- delete curr;
- numOfEdges--;
- } else {
- cout << "边 < v1, v2 > 不存在!" << endl;
- exit(0);
- }
- }
- int AdjTWGraph: :GetFirstNeighbor(const int v) {
- if (v < 0 || v > numVertices) {
- cout << "参数 v1 越界出错!" << endl;
- exit(0);
- }
- EdgeType * p = Vertices[v].adj;
- if (p != NULL) return p - >dest;
- else return - 1;
- }
- int AdjTWGraph: :GetNextNeighbor(const int v1, const int v2) {
- if (v1 < 0 || v1 > numVertices || v2 < 0 || v2 > numVertices) {
- cout << "参数 v1 或 v2 越界出错!" << endl;
- exit(0);
- }
- EdgeType * p = Vertices[v1].adj;
- while (p != NULL) {
- if (p - >next != NULL && p - >dest == v2) return p - >next - >dest;
- else p = p - >next;
- }
- return - 1;
- }
- void AdjTWGraph: :DepthFirstSearch() {
- int * visited = new int[NumOfVertices()];
- for (int i = 0; i < NumOfVertices(); i++) visited[i] = 0;
- for (int i = 0; i < NumOfVertices(); i++) if (!visited[i]) DepthFirstSearch(i, visited);
- delete[] visited;
- }
- void AdjTWGraph: :DepthFirstSearch(const int v, int visited[]) {
- cout << GetValue(v) << " ";
- visited[v] = 1;
- int w = GetFirstNeighbor(v);
- while (w != -1) {
- if (!visited[w]) DepthFirstSearch(w, visited);
- w = GetNextNeighbor(v, w);
- }
- }
- void AdjTWGraph: :BroadFirstSearch() {
- int * visited = new int[NumOfVertices()];
- for (int i = 0; i < NumOfVertices(); i++) visited[i] = 0;
- for (int i = 0; i < NumOfVertices(); i++) if (!visited[i]) BroadFirstSearch(i, visited);
- delete[] visited;
- }
- void AdjTWGraph: :BroadFirstSearch(const int v, int visited[]) {
- VerT u,
- w;
- SeqQueue queue;
- cout << GetValue(v) << " ";
- visited[v] = 1;
- queue.Append(v);
- while (queue.NotEmpty()) {
- u = queue.Delete();
- w = GetFirstNeighbor(u);
- while (w != -1) {
- if (!visited[w]) {
- cout << GetValue(w) << " ";;
- visited[w] = 1;
- queue.Append(w);
- }
- w = GetNextNeighbor(u, w);
- }
- }
- }
- void AdjTWGraph: :Show() {
- for (int i = 0; i < numVertices; i++) {
- for (int j = 0; j < numVertices; j++) {
- int a = GetWeight(i, j);
- if (a == MaxWeight) cout << "∞";
- else cout << a << " ";
- }
- cout << endl;
- }
- }
- CreatAdjTWGraph.h struct RowColWeight {
- int row; // 行下标
- int col; // 列下标
- int weight; // 权值
- };
- void CreatWayWeb(AdjTWGraph & G, DataType V[], int n, RowColWeight E[], int e)
- // 在图 G 中插入 n 个顶点 V 和 e 条边 E
- {
- // 在图 G 中插入 n 个顶点
- for (int i = 0; i < n; i++) G.InsertVertex(V[i]);
- // 在图 G 中插入 e 条边
- for (int k = 0; k < e; k++) G.InsertWayEdge(E[k].row, E[k].col, E[k].weight);
- }
- void CreatNoWayWeb(AdjTWGraph & G, DataType V[], int n, RowColWeight E[], int e) {
- // 在图 G 中插入 n 个顶点
- for (int i = 0; i < n; i++) G.InsertVertex(V[i]);
- // 在图 G 中插入 e 条边
- for (int k = 0; k < e; k++) {
- if (E[k].row > E[k].col) {
- cout << "无向网参数输入错误";
- exit(0);
- }
- G.InsertNoWayEdge(E[k].row, E[k].col, E[k].weight);
- G.InsertNoWayEdge(E[k].col, E[k].row, E[k].weight);
- }
- }
- SeqQueue.h#include < iostream > using namespace std;
- class SeqQueue {
- private: DataType data[MaxQueueSize]; // 顺序队列数组
- int front; // 队头指示器
- int rear; // 队尾指示器
- int count; // 元素个数计数器
- public: SeqQueue(void) // 构造函数
- {
- front = rear = 0;
- count = 0;
- };~SeqQueue(void) {}; // 析构函数
- void Append(const DataType & item); // 入队列
- DataType Delete(void); // 出队列
- DataType GetFront(void) const; // 取队头数据元素
- int NotEmpty(void) const // 非空否
- {
- return count != 0;
- };
- };
- void SeqQueue: :Append(const DataType & item) // 入队列
- // 把数据元素 item 插入队列作为当前的新队尾
- {
- if (count > 0 && front == rear) {
- cout << "队列已满!" << endl;
- exit(0);
- }
- data[rear] = item; // 把元素 item 加在队尾
- rear = (rear + 1) % MaxQueueSize; /// 队尾指示器加 1
- count++; // 计数器加 1
- }
- DataType SeqQueue: :Delete(void) // 出队列
- // 把队头元素出队列, 出队列元素由函数返回
- {
- if (count == 0) {
- cout << "队列已空!" << endl;
- exit(0);
- }
- DataType temp = data[front]; // 保存原队头元素
- front = (front + 1) % MaxQueueSize; // 队头指示器加 1
- count--; // 计数器减 1
- return temp; // 返回原队头元素
- }
- DataType SeqQueue: :GetFront(void) const // 取队头数据元素
- // 取队头元素并由函数返回
- {
- if (count == 0) {
- cout << "队列空!" << endl;
- exit(0);
- }
- return data[front]; // 返回队头元素
- }
- GraphTest.cpp#include < iostream > #include < stdlib.h > const int MaxQueueSize = 100;
- typedef char VerT;
- typedef int DistT;
- typedef char DataType;#include "AdjTWGraph.h"#include "CreatAdjTWGraph.h"int main() {
- AdjTWGraph g,
- f;
- char a[] = {
- 'A',
- 'B',
- 'C',
- 'D',
- 'E'
- };
- char b[] = {
- 'A',
- 'B',
- 'C',
- 'D',
- 'E',
- 'F'
- };
- RowColWeight r1[] = {
- {
- 0,
- 1,
- 10
- },
- {
- 0,
- 4,
- 20
- },
- {
- 1,
- 3,
- 30
- },
- {
- 2,
- 1,
- 40
- },
- {
- 3,
- 2,
- 50
- },
- {
- 2,
- 4,
- 25
- }
- };
- RowColWeight r2[] = {
- {
- 0,
- 1,
- 10
- },
- {
- 0,
- 4,
- 20
- },
- {
- 1,
- 3,
- 30
- },
- {
- 1,
- 2,
- 40
- },
- {
- 2,
- 3,
- 50
- },
- {
- 4,
- 5,
- 15
- },
- {
- 3,
- 4,
- 12
- }
- };
- int n1,
- n2,
- e1,
- e2;
- n1 = sizeof(a) / sizeof(a[0]);
- n2 = sizeof(b) / sizeof(b[0]);
- e1 = sizeof(r1) / sizeof(r1[0]);
- e2 = sizeof(r2) / sizeof(r2[0]);
- CreatWayWeb(g, a, n1, r1, e1); // 创建有向网
- CreatNoWayWeb(f, b, n2, r2, e2); // 创建无向网
- cout << "有向网:" << endl;
- g.Show();
- cout << "\n 顶点个数为:" << g.NumOfVertices();
- cout << "\n 边的条数为:" << g.NumOfEdges();
- cout << "\n 广度优先搜索序列为:";
- g.BroadFirstSearch();
- cout << "\n 深度优先搜索序列为:";
- g.DepthFirstSearch();
- cout << "\n\n 无向网" << endl;
- f.Show();
- cout << "\n 顶点个数为:" << f.NumOfVertices();
- cout << "\n 边的条数为:" << f.NumOfEdges();
- cout << "\n 深度优先搜索序列为:";
- f.DepthFirstSearch();
- cout << "\n 广度优先搜索序列为:";
- f.BroadFirstSearch();
- return 0;
- }
最终结果
来源: http://www.bubuko.com/infodetail-3066878.html