数据结构OJ实验9-图存储结构和遍历

A. 图综合练习--构建邻接表

题目描述

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

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

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

输入

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

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

第3行输入n个顶点。

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

以此类推输入下一个图

输出

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

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

样例查看模式 

正常显示查看格式

输入样例1 

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

输出样例1

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

AC代码

#include<iostream>
#include<vector>
#include<map>
using namespace std;
class graph
{int n, k;vector<int>h;vector<int>ne;vector<int>e;int idx;map<char, int>id;vector<char>value;
public:graph(){idx = 0;cin >> n >> k;h.resize(2 * n, -1);ne.resize(2 * n);e.resize(2 * n);for (int i = 0; i < n; i++){char c;cin >> c;id[c] = i;value.push_back(c);}for (int i = 0; i < k; i++){char u, v;cin >> u >> v;add(id[u], id[v]);}}void add(int a, int b){e[idx] = b;ne[idx] = h[a];h[a] = idx++;}void show(){for (int i = 0; i < n; i++){cout << i << " " << value[i] << "-";vector<int>ans;for (int j = h[i]; ~j; j = ne[j]){int k = e[j];ans.push_back(id[value[k]]);}//由于本题使用头插法，而此方法是尾插法，故要逆转for (int i=ans.size()-1;i>=0;i--){cout << ans[i] << "-";}cout << "^" << endl;}}
};
int main()
{int t;cin >> t;while (t--){graph g;g.show();}return 0;
}

B. DS图—图的邻接矩阵存储及度计算

题目描述

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

--程序要求--

若使用C++只能include一个头文件iostream；若使用C语言只能include一个头文件stdio

程序中若include多过一个头文件，不看代码，作0分处理

不允许使用第三方对象或函数实现本题的要求

输入

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

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

顶点信息

边数

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

输出

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

图的邻接矩阵

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

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

样例查看模式 

正常显示查看格式

输入样例1 

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

输出样例1

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

AC代码

#include<iostream>
using namespace std;
//输入测试次数，每组测试：
//图类型，顶点数
//顶点信息，边数，每条边的头尾
//输出每个点的出度和入度，单独输出孤立点
class Map
{int vertexnum;string* vertex;int** adjmatrix;char kind;
public:Map(){cin >> kind >> vertexnum;vertex = new string[vertexnum];for (int i = 0; i < vertexnum; i++){cin >> vertex[i];}adjmatrix = new int* [vertexnum];for (int i = 0; i < vertexnum; i++){adjmatrix[i] = new int[vertexnum];for (int j = 0; j < vertexnum; j++){adjmatrix[i][j] = 0;}}int n;cin >> n;for (int i = 0; i < n; i++){string s1, s2;cin >> s1 >> s2;int index1 = 0;int index2 = 0;for (int j = 0; j < vertexnum; j++){if (vertex[j] == s1){index1 = j;break;}}for (int j = 0; j < vertexnum; j++){if (vertex[j] == s2){index2 = j;break;}}switch (kind){case 'U':adjmatrix[index2][index1] = 1;case 'D':adjmatrix[index1][index2] = 1;default:break;}}}void display_array(){for (int i = 0; i < vertexnum; i++){cout << adjmatrix[i][0];for (int j = 1; j < vertexnum; j++){cout << " " << adjmatrix[i][j];}cout << endl;}}void display_node(){if (kind == 'U'){for (int i = 0; i < vertexnum; i++){int cnt = 0;for (int j = 0; j < vertexnum; j++){if (adjmatrix[i][j] != 0){cnt++;}}if (cnt){cout << vertex[i] << ": " << cnt << endl;}else{cout << vertex[i] << endl;}}}else if (kind == 'D'){for (int i = 0; i < vertexnum; i++){int cnt1 = 0;for (int j = 0; j < vertexnum; j++){if (adjmatrix[i][j] != 0){cnt1++;}}int cnt2 = 0;for (int j = 0; j < vertexnum; j++){if (adjmatrix[j][i] != 0){cnt2++;}}if (cnt1 || cnt2)//存在其中一个就不是孤立点{cout << vertex[i] << ": " << cnt1 << " " << cnt2 << " " << cnt1 + cnt2 << endl;}else{cout << vertex[i] << endl;}}}}~Map(){delete[]vertex;for (int i = 0; i < vertexnum; i++){delete[]adjmatrix[i];}delete[]adjmatrix;}
};
int main()
{int n;cin >> n;while (n--){Map m;m.display_array();m.display_node();}return 0;
}

C. DS图遍历--深度优先搜索

题目描述

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

代码框架参考课本P169算法7.4和7.5，同学们可在理解的基础上自行设计算法，不强制要求完全相同

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

输入

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

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

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

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

以此类推输入下一个示例

输出

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

样例查看模式 

正常显示查看格式

输入样例1 

2\n
4\n
0 0 1 1\n
0 0 1 1\n
1 1 0 1\n
1 1 1 0\n
5\n
0 0 0 1 1\n
0 0 1 0 0\n
0 1 0 1 1\n
1 0 1 0 0\n
1 0 1 0 0\n

输出样例1

0 2 1 3 \n
0 3 2 1 4 \n

AC代码

#include<bits/stdc++.h>
using namespace std;
int main()
{int t;cin >> t;while (t--){int n;cin >> n;vector<vector<int>>v(n);for (int i = 0; i < n; i++){for (int j = 0; j < n; j++){int x;cin >> x;v[i].push_back(x);}}vector<int>st(n);//标记是否已经走过stack<int>s;//深度优先搜索使用栈for (int i = 0; i < n; i++)//每个结点都要搜一次，确定每个都走过{if (st[i])continue;s.push(i);while (!s.empty())//每个点开始搜{auto t = s.top();s.pop();if (st[t])continue;st[t] = 1;cout << t << " ";//满足条件可以搜//注意逆序枚举连接点//因为是栈，先进去后出来for (int j = n - 1; j >= 0; j--){if (v[t][j] && !st[j]){s.push(j);}}}}cout << endl;}return 0;
}

D. DS图遍历--广度优先搜索

题目描述

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

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

输入

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

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

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

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

以此类推输入下一个示例

输出

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

样例查看模式 

正常显示查看格式

输入样例1 

2\n
4\n
0 0 1 1\n
0 0 1 1\n
1 1 0 1\n
1 1 1 0\n
5\n
0 0 0 1 1\n
0 0 1 0 0\n
0 1 0 1 1\n
1 0 1 0 0\n
1 0 1 0 0\n

输出样例1

0 2 3 1 \n
0 3 4 2 1 \n

AC代码

#include<bits/stdc++.h>
using namespace std;
int main()
{int t;cin >> t;while (t--){int n;cin >> n;vector<vector<int>>v(n);for (int i = 0; i < n; i++){for (int j = 0; j < n; j++){int x;cin >> x;v[i].push_back(x);}}vector<int>st(n);//标记是否已经走过queue<int>s;//广度搜索使用队列for (int i = 0; i < n; i++)//每个结点都要搜一次，确定每个都走过{if (st[i])continue;s.push(i);while (!s.empty())//每个点开始搜{auto t = s.front();s.pop();if (st[t])continue;st[t] = 1;cout << t << " ";//满足条件可以搜//注意顺序枚举连接点//因为是队列，先进去先出来for (int j = 0; j<=n-1;j++){if (v[t][j] && !st[j]){s.push(j);}}}}cout << endl;}return 0;
}

E. DS图—图非0面积

题目描述

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

提示：queue

输入

测试次数t

每组测试数据格式为：

数组大小m,n

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

输出

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

样例查看模式 

正常显示查看格式

输入样例1 

2\n
10 10\n
0 0 0 0 0 0 0 0 0 0\n
0 0 0 0 1 1 1 0 0 0\n
0 0 0 0 1 0 0 1 0 0\n
0 0 0 0 0 1 0 0 1 0\n
0 0 1 0 0 0 1 0 1 0\n
0 1 0 1 0 1 0 0 1 0\n
0 1 0 0 1 1 0 1 1 0\n
0 0 1 0 0 0 0 1 0 0\n
0 0 0 1 1 1 1 1 0 0\n
0 0 0 0 0 0 0 0 0 0\n
5 8\n
0 1 1 0 0 1 1 0\n
1 0 1 0 1 0 0 1\n
0 1 0 1 0 0 1 0\n
0 1 0 0 1 1 1 0\n
0 0 0 0 0 0 0 0\n

输出样例1

15\n
5\n

#include<bits/stdc++.h>
using namespace std;
int n,m;
int dx[]={1,-1,0,0};
int dy[]={0,0,-1,1};
vector<vector<int>>v;
void dfsfind(int x,int y)
{if(x<0||y<0||x>=m||y>=n||v[x][y])return;v[x][y]=1;for(int i=0;i<4;i++){dfsfind(x+dx[i],y+dy[i]);}
}
int main()
{int t;cin>>t;while(t--){v.clear();cin>>m>>n;v.resize(m);for(int i=0;i<m;i++){for(int j=0;j<n;j++){int x;cin>>x;v[i].push_back(x);}}int ans=0;for(int i=0;i<m;i++)//先按行{dfsfind(i,0);dfsfind(i,n-1);}for(int i=0;i<n;i++)//后按列{dfsfind(0,i);dfsfind(m-1,i);}for(int i=0;i<m;i++){for(int j=0;j<n;j++){if(v[i][j]==0)ans++;}}cout<<ans<<endl;}return 0;
}

F. 社交网络图中结点的“重要性”计算

题目描述

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

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

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

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

输入

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

输出

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

样例查看模式 

正常显示查看格式

输入样例1 

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

输出样例1

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

AC代码

#include<bits/stdc++.h>
using namespace std;
//求一个点到其余各点的最短路->FLoyd
const int N = 1000, inf = 1e9;
long long res = 0;
int n, m, k;
int d[N][N];
void floyd()
{for (int k = 1; k <= n; k++)//中间点枚举放在首个循环{for (int i = 1; i <= n; i++){for (int j = 1; j <= n; j++){d[i][j] = min(d[i][j], d[i][k] + d[k][j]);}}}
}
int main()
{cin >> n >> m;//注意弗洛伊德的初始for (int i = 1; i <= n; i++){for (int j = 1; j <= n; j++){if (i == j)d[i][j] = 0;else d[i][j] = inf;}}for (int i = 0; i < m; i++){int a, b;cin >> a >> b;d[a][b] = d[b][a] = 1;//无向图}floyd();bool flag = 0;cin >> k;for (int i = 0; i < k; i++) {res = 0;int x;cin >> x;if (!flag){for (int j = 1; j <= n; j++){if (x == j)continue;if (d[x][j] > inf / 2)//此时不连通{flag = 1;break;}res += d[x][j];}}if (flag)printf("Cc(%d)=0.00\n", x);//无法满足到其余所有点else{double ans = (double)(n - 1) / res;printf("Cc(%d)=%.2lf\n", x, ans);}}return 0;
}