DS|图（存储与遍历）

发布时间：2024年01月06日

题目一：DS图 --?构建邻接表

题目描述：

已知一有向图，构建该图对应的邻接表。

邻接表包含数组和单链表两种数据结构，其中每个数组元素也是单链表的头结点，数组元素包含两个属性，属性一是顶点编号info，属性二是指针域next指向与它相连的顶点信息。

单链表的每个结点也包含两个属性，属性一是顶点在数组的位置下标，属性二是指针域next指向下一个结点。

输入要求：

第1行输入整数t，表示有t个图

第2行输入n和k，表示该图有n个顶点和k条弧。

第3行输入n个顶点。

第4行起输入k条弧的起点和终点，连续输入k行

以此类推输入下一个图

输出要求：

输出每个图的邻接表，每行输出格式：数组下标 顶点编号-连接顶点下标-......-^，数组下标从0开始。

具体格式请参考样例数据，每行最后加入“^”表示NULL。

输入样例：

1
5 7
A B C D E
A B
A D
A E
B D
C B
C E
E D

输出样例：

0 A-1-3-4-^
1 B-3-^
2 C-1-4-^
3 D-^
4 E-3-^

代码示例：

#include <iostream>
#include <string>
#include <cstring>
#include <iomanip>
#include <algorithm>
#include <cmath>
#include <queue>
using namespace std;

class List {
public:
    int sub;
    List* next;
    List() :next(NULL) {}
};

class Head {
public:
    char info;
    List* next;
    Head() :next(NULL) {}
    void CreateMap(Head* h, int n, int op) {
        char ch1, ch2;
        for (int i = 0; i < op; i++) {
            cin >> ch1 >> ch2;
            for (int j = 0; j < n; j++) {
                for (int r = 0; r < n; r++) {
                    if (ch1 == h[j].info && ch2 == h[r].info) {
                        if (h[j].next == NULL) {
                            List* l = new List;
                            h[j].next = l;
                            l->sub = r;
                        }
                        else {
                            List* l = h[j].next;
                            while (l->next) l = l->next;
                            List* p = new List;
                            l->next = p;
                            p->sub = r;
                        }
                    }
                }
            }
        }
    }
};

void Mergemap(Head* h, int n) {
    for (int i = 0; i < n; i++) {
        cout << i << ' ' << h[i].info << '-';
        List* q = h[i].next;
        while (q) {
            cout << q->sub << '-';
            q = q->next;
        }
        cout << '^' << endl;
    }
}

int main() {
    int t;
    cin >> t;
    while (t--) {
        int n, op;
        cin >> n >> op;
        Head* h = new Head[n];
        for (int i = 0; i < n; i++) cin >> h[i].info;

        h->CreateMap(h, n, op);
        Mergemap(h, n);
    }
    return 0;
}

题目二：DS图 --?图的邻接矩阵存储及度计算

题目描述：

假设图用邻接矩阵存储。输入图的顶点信息和边信息，完成邻接矩阵的设置，并计算各顶点的入度、出度和度，并输出图中的孤立点（度为0的顶点）

输入要求：

测试次数T，每组测试数据格式如下：

图类型? 顶点数 （D—有向图，U—无向图）

顶点信息

边数

每行一条边（顶点1 顶点2）或弧（弧尾 弧头）信息

输出要求：

每组测试数据输出如下信息（具体输出格式见样例）：

图的邻接矩阵

按顶点信息输出各顶点的度（无向图）或各顶点的出度? 入度? 度（有向图）。孤立点的度信息不输出。

图的孤立点。若没有孤立点，不输出任何信息。

输入样例：

2
D 5
V1 V2 V3 V4 V5
7
V1 V2
V1 V4
V2 V3
V3 V1
V3 V5
V4 V3
V4 V5
U 5
A B C D E
5
A B
A C
B D
D C
A D

输出样例：

0 1 0 1 0
0 0 1 0 0
1 0 0 0 1
0 0 1 0 1
0 0 0 0 0
V1: 2 1 3
V2: 1 1 2
V3: 2 2 4
V4: 2 1 3
V5: 0 2 2
0 1 1 1 0
1 0 0 1 0
1 0 0 1 0
1 1 1 0 0
0 0 0 0 0
A: 3
B: 2
C: 2
D: 3
E

代码示例：

#include <iostream>

using namespace std;
class Map {
private:
    int** array;
    string* vertex;
    int n;
    char type;
public:
    Map() {
        cin >> type >> n;
        array = new int* [n];
        for (int i = 0; i < n; i++) {
            array[i] = new int[n];
            for (int j = 0; j < n; j++) array[i][j] = 0;
        }
        vertex = new string[n];
        for (int i = 0; i < n; i++) cin >> vertex[i];
    }

    int findIndex(string str) {
        for (int i = 0; i < n; i++) if (str == vertex[i]) return i;
        return -1;
    }

    void createMap() {
        int n, v1, v2;
        string ch1, ch2;
        cin >> n;
        for (int i = 0; i < n; i++) {
            cin >> ch1 >> ch2;
            v1 = findIndex(ch1);
            v2 = findIndex(ch2);
            array[v1][v2] = 1;
            if (type == 'U') array[v2][v1] = 1;
        }
    }

    void printMap() {
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                cout << array[i][j];
                if (j == n - 1) cout << endl;
                else cout << " ";
            }
        }

        if (type == 'D') {
            for (int i = 0; i < n; i++) {
                int in_dimen = 0, out_dimen = 0;
                for (int j = 0; j < n; j++) {
                    in_dimen += array[i][j];
                    out_dimen += array[j][i];
                }
                if (in_dimen == 0 && out_dimen == 0) cout << vertex[i] << endl;
                else cout << vertex[i] << ": " << in_dimen << " " << out_dimen << " " << in_dimen + out_dimen << endl;
            }
        }
        else if (type == 'U') {
            for (int i = 0; i < n; i++) {
                int total_dimen = 0;
                for (int j = 0; j < n; j++) total_dimen += array[i][j];
                if (total_dimen == 0) cout << vertex[i] << endl;
                else cout << vertex[i] << ": " << total_dimen << endl;
            }
        }
    }
    ~Map() {
        for (int i = 0; i < n; i++) delete[]array[i];
        delete[]array;
        delete[]vertex;
    }
};

int main() {
    int t;
    cin >> t;
    while (t--) {
        Map M;
        M.createMap();
        M.printMap();
    }
    return 0;
}

题目三：DS图 -- 深度优先搜索

题目描述：

给出一个图的邻接矩阵，对图进行深度优先搜索，从顶点0开始

注意：图n个顶点编号从0到n-1

输入要求：

第一行输入t，表示有t个测试实例

第二行输入n，表示第1个图有n个结点

第三行起，每行输入邻接矩阵的一行，以此类推输入n行

第i个结点与其他结点如果相连则为1，无连接则为0，数据之间用空格隔开

以此类推输入下一个示例

输出要求：

每行输出一个图的深度优先搜索结果，结点编号之间用空格隔开

输入样例：

2
4
0 0 1 1
0 0 1 1
1 1 0 1
1 1 1 0
5
0 0 0 1 1
0 0 1 0 0
0 1 0 1 1
1 0 1 0 0
1 0 1 0 0

输出样例：

0 2 1 3 
0 3 2 1 4

代码示例：

#include <iostream>
#include <string>
#include <cstring>
#include <iomanip>
#include <algorithm>
#include <cmath>
#include <queue>
using namespace std;

class Map {
public:
    bool visited[20];
    int** array;
    int vexnumber;
    Map() {
        cin >>  vexnumber;
        array = new int* [vexnumber];
        for (int i = 0; i < vexnumber; i++) {
            array[i] = new int[vexnumber];
            for (int j = 0; j < vexnumber; j++) cin >> array[i][j];
        }
        for (int i = 0; i < vexnumber; i++) visited[i] = false;
    }
    //防止图是非连通图
    void DFSTraverse() {
        for (int i = 0; i < vexnumber; i++) if (!visited[i]) DFS(i);
        cout << endl;
    }
    void DFS(int v){
        visited[v] = true;
        cout << v << ' ';
        int* tmp = new int[vexnumber];
        int index = 0;
        for (int i = 0; i < vexnumber; i++) if (array[v][i]) tmp[index++] = i;
        for (int i = 0; i < index; i++) if (!visited[tmp[i]]) DFS(tmp[i]);
        delete[] tmp;
    }
};

int main() {
    int t;
    cin >> t;
    while (t--) {
        Map map;
        map.DFSTraverse();
    }
    return 0;
}

题目四：DS图 -- 广度优先搜索

题目描述：

给出一个图的邻接矩阵，对图进行广度优先搜索，从顶点0开始

注意：图n个顶点编号从0到n-1

输入要求：

第一行输入t，表示有t个测试实例

第二行输入n，表示第1个图有n个结点

第三行起，每行输入邻接矩阵的一行，以此类推输入n行

第i个结点与其他结点如果相连则为1，无连接则为0，数据之间用空格隔开

以此类推输入下一个示例

输出要求：

每行输出一个图的广度优先搜索结果，结点编号之间用空格隔开

输入样例：

2
4
0 0 1 1
0 0 1 1
1 1 0 1
1 1 1 0
5
0 0 0 1 1
0 0 1 0 0
0 1 0 1 1
1 0 1 0 0
1 0 1 0 0

输出样例：

0 2 3 1 
0 3 4 2 1

代码示例：

#include <iostream>
#include <string>
#include <cstring>
#include <iomanip>
#include <algorithm>
#include <cmath>
#include <queue>
using namespace std;

class Map {
public:
    bool visited[20];
    int** array;
    int vexnumber;
    Map() {
        cin >>  vexnumber;
        array = new int* [vexnumber];
        for (int i = 0; i < vexnumber; i++) {
            array[i] = new int[vexnumber];
            for (int j = 0; j < vexnumber; j++) cin >> array[i][j];
        }
        for (int i = 0; i < vexnumber; i++) visited[i] = false;
    }
    void BFSTraverse() {
        for (int i = 0; i < vexnumber; i++) if (!visited[i]) BFS(i);
        cout << endl;
    }
    void BFS(int i){
        int* adjvex = new int[vexnumber];
        queue<int> Q;
        visited[i] = true;
        Q.push(i);
        while (!Q.empty()) {
            int temp = Q.front();
            cout << temp << ' ';
            Q.pop();
            for (int j = 0; j < vexnumber; j++) adjvex[j] = -1;
            int pos = 0;
            for (int j = 0; j < vexnumber; j++) if (array[temp][j]) adjvex[pos++] = j;
            int k = 0;
            for (int j = adjvex[k]; j >= 0; j = adjvex[k++]) {
                if (!visited[j]) {
                    visited[j] = true;
                    Q.push(j);
                }
            }
        }
        delete[] adjvex;
    }
};

int main() {
    int t;
    cin >> t;
    while (t--) {
        Map map;
        map.BFSTraverse();
    }
    return 0;
}

题目五：DS图 -- 图非0面积

题目描述：

编程计算由"1"围成的下列图形的面积。面积计算方法是统计"1"所围成的闭合曲线中"0"点的数目。如图所示，在10*10的二维数组中，"1"围住了15个点，因此面积为15。

输入要求：

测试次数t

每组测试数据格式为：

数组大小m,n

一个由0和1组成的m*n的二维数组

输出要求：

对每个二维数组，输出符号"1"围住的"0"的个数，即围成的面积。假设一定有1组成的闭合曲线，但不唯一。

输入样例：

2
10 10
0 0 0 0 0 0 0 0 0 0
0 0 0 0 1 1 1 0 0 0
0 0 0 0 1 0 0 1 0 0
0 0 0 0 0 1 0 0 1 0
0 0 1 0 0 0 1 0 1 0
0 1 0 1 0 1 0 0 1 0
0 1 0 0 1 1 0 1 1 0
0 0 1 0 0 0 0 1 0 0
0 0 0 1 1 1 1 1 0 0
0 0 0 0 0 0 0 0 0 0
5 8
0 1 1 0 0 1 1 0
1 0 1 0 1 0 0 1
0 1 0 1 0 0 1 0
0 1 0 0 1 1 1 0
0 0 0 0 0 0 0 0

输出样例：

15
5

代码示例：

#include <iostream>
#include <string>
#include <cstring>
#include <iomanip>
#include <algorithm>
#include <cmath>
#include <queue>
using namespace std;

class Map {
	int** array; // 二维数组指针，表示地图
	int row, column; // 行数和列数
public:
	// 构造函数，初始化地图大小
	Map(int m, int n) {
		row = m;
		column = n;
		array = new int*[row + 2]; // 在地图周围加一圈边界
		for (int i = 0; i < m + 2; i++) {
			array[i] = new int[column + 2];
			for (int j = 0; j < n + 2; j++) {
				array[i][j] = 0; // 初始化地图为全0
			}
		}
	}

	// 读取地图数据
	void CreateMap() {
		for (int i = 1; i < row + 1; i++) {
			for (int j = 1; j < column + 1; j++) {
				cin >> array[i][j];
			}
		}
	}

	// 使用深度优先搜索遍历地图
	void Traverse(int x, int y) {
		// 对当前点的上、下、左、右四个方向进行遍历
		if (x - 1 != -1 && array[x - 1][y] == 0) {
			array[x - 1][y] = 1; // 将访问过的位置标记为1
			Traverse(x - 1, y);
		}
		if (x + 1 != row + 2 && array[x + 1][y] == 0) {
			array[x + 1][y] = 1;
			Traverse(x + 1, y);
		}
		if (y - 1 != -1 && array[x][y - 1] == 0) {
			array[x][y - 1] = 1;
			Traverse(x, y - 1);
		}
		if (y + 1 != -1 && array[x][y + 1] == 0) {
			array[x][y + 1] = 1;
			Traverse(x, y + 1);
		}
	}

	// 计算未被访问过的区域大小
	void CountArea() {
		int area = 0;
		for (int i = 1; i < row + 1; i++) {
			for (int j = 1; j < column + 1; j++) {
				if (array[i][j] == 0) area++; // 统计未被访问过的位置
			}
		}
		cout << area << endl;
	}
};

int main() {
	int t;
	cin >> t;
	while (t--) {
		int m, n;
		cin >> m >> n;
		Map map(m, n); // 创建地图对象
		map.CreateMap(); // 读取地图数据
		map.Traverse(0, 0); // 从起始点开始深度优先搜索
		map.CountArea(); // 计算未被访问过的区域大小
	}
	return 0;
}

题目六：DS图 -- 社交网络图中结点的“重要性”计算

题目描述：

在社交网络中，个人或单位（结点）之间通过某些关系（边）联系起来。他们受到这些关系的影响，这种影响可以理解为网络中相互连接的结点之间蔓延的一种相互作用，可以增强也可以减弱。而结点根据其所处的位置不同，其在网络中体现的重要性也不尽相同。

“紧密度中心性”是用来衡量一个结点到达其它结点的“快慢”的指标，即一个有较高中心性的结点比有较低中心性的结点能够更快地（平均意义下）到达网络中的其它结点，因而在该网络的传播过程中有更重要的价值。在有N个结点的网络中，结点v_i的“紧密度中心性”Cc(v_i?)数学上定义为v_i到其余所有结点v_j?(i=j)的最短距离d(v_i, v_j)的平均值的倒数：

对于非连通图，所有结点的紧密度中心性都是0。

给定一个无权的无向图以及其中的一组结点，计算这组结点中每个结点的紧密度中心性。

输入要求：

输入第一行给出两个正整数N和M，其中N(\leq 10^4)是图中结点个数，顺便假设结点从1到N编号；M(\leq 10^5)是边的条数。随后的M行中，每行给出一条边的信息，即该边连接的两个结点编号，中间用空格分隔。最后一行给出需要计算紧密度中心性的这组结点的个数K（≤100）以及K个结点编号，用空格分隔。

输出要求：

按照Cc(i)=x.xx的格式输出K个给定结点的紧密度中心性，每个输出占一行，结果保留到小数点后2位。

输入样例：

9 14
1 2
1 3
1 4
2 3
3 4
4 5
4 6
5 6
5 7
5 8
6 7
6 8
7 8
7 9
3 3 4 9

输出样例：

Cc(3)=0.47
Cc(4)=0.62
Cc(9)=0.35

代码示例：

#include <iostream>
#include <string>
#include <cstring>
#include <iomanip>
#include <algorithm>
#include <cmath>
#include <queue>
using namespace std;

class Map {
	int array[1000][1000];
	int n, m;
	bool flag = true;
public:
	Map() {}
	Map(int n0, int m0) {
		n = n0, m = m0;
	}
	void Init() {
		for (int i = 1; i <= n; i++) {
			for (int j = 1; j <= n; j++) {
				if (i == j) array[i][j] = 0;
				else array[i][j] = 65535;
			}
		}
	}
	void Create() {
		for (int i = 0; i < m; i++) {
			int x, y;
			cin >> x >> y;
			array[x][y] = array[y][x] = 1;
		}
	}
	void Tramap() {
		for (int k = 1; k <= n; k++) {
			for (int i = 1; i <= n; i++) {
				for (int j = 1; j <= n; j++) {
					if (array[i][j] > array[i][k] + array[k][j]) {
						array[i][j] = array[i][k] + array[k][j];
					}
				}
			}
		}
	}
	void Flag() {
		for (int i = 1; i <= n; i++) {
			for (int j = 1; j <= n; j++) {
				if (array[i][j] == 65535) {
					flag = false;
					break;
				}
			}
			if (!flag)break;
		}
	}
	void Display() {
		int k, id;
		cin >> k;
		while (k--) {
			cin >> id;
			if (!flag) cout << "Cc(" << id << ")=0.00" << endl;
			else {
				int distance = 0;
				for (int i = 1; i <= n; i++) distance += array[id][i];
				cout << "Cc(" << id << ")=";
				cout << fixed << setprecision(2) << (n - 1) * 1.0 / distance << endl;
			}
		}
	}
};

int main() {
	int n0, m0;
	cin >> n0 >> m0;
	Map map(n0, m0);
	map.Init();
	map.Create();
	map.Tramap();
	map.Flag();
	map.Display();
}

文章来源:https://blog.csdn.net/2203_75720729/article/details/135420107
本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。
最新文章