图的基本应用：社交网络图中结点的“重要性”计算

题目描述：

输入：

输出：

样例：

输入：                                                            输出：

9 14                                                                Cc(3)=0.47
1 2                                                                  Cc(4)=0.62
1 3                                                                  Cc(9)=0.35
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

解题思路：(本题思路完全根据自己上课所学所打，如有更好解法可以评论区交流)

本题采用的是邻接矩阵的方法来实现的（当然用邻接表定义一个类可能更加简单一点，但懒得改了bushi）

我们先利用邻接矩阵的方法构建一个图，由于要找最短路径，这里用到的是广度优先遍历算法即bfs，这样能确保我们一定能找到最短路径；BFS这里不细说怎么实现，原理就是利用队列的数据结构，但值得注意的是我们要找最短路径，则要标记是否访问过，否则存在环路会是结果发生错误甚至产生异常，所以我们给结构体中加了一个visited的标志位，除此之外，记得每次进行BFS之前都要对标志位进行初始化（即文中的initialfalse)；

那我们怎么计算距离呢，找到结点之后？我们给每个结构体都定义了一个parent变量方便回溯，这样，并将全部初始化为-1，如果回溯到某个结点parent为-1，则结束，得到距离；注意这里每BFS也都要初始化parent（即文中的initialparent）；

最后要注意的是可能出现非连通图，所以每次进来先判断是不是连通图，如果不是直接退出并输出0.00，同理在判断每个节点与其他点的距离的时候也可以先判断两者之间是否路径，没有则为非连通图，直接距离为0，进行下一步循环；

#include<iostream>
#include<queue>
#include<iomanip>
using namespace std;
struct VexNode {
	int data;
	int* ArcList;
	int Nodenum;
	bool visited;
	int parent;
};
void initialfalse(VexNode* v) {
	for (int i = 0; i < v[0].Nodenum; i++)
		v[i].visited = false;
}
void initialparent(VexNode* v) {
	for (int i = 0; i < v[0].Nodenum; i++)
		v[i].parent = -1;
}
VexNode* CreateGraph() {
	int nodenum, i, j, arcnum;
	cin >> nodenum>>arcnum;
	VexNode* v = new VexNode[nodenum];
	for (i = 0; i <nodenum; i++) {
		v[i].data=i;
		v[i].Nodenum = nodenum;
		v[i].parent = -1;
		v[i].ArcList = new int[nodenum];
		for (j = 0; j < nodenum; j++)
			v[i].ArcList[j] = 0;
	}
	int x, y;
	for (i = 0; i < arcnum; i++) {
		cin >> x >> y;
		v[x - 1].ArcList[y-1] = 1;
		v[y - 1].ArcList[x-1] = 1;
	}
	return v;
}
bool judge(VexNode* v, int index) {
	bool flag = false;
	for (int i = 0; i < v[0].Nodenum; i++) {
		if (v[index].ArcList[i] != 0)
			flag = true;
	}
	return flag;
}
void BFS(VexNode* v, int index,int i) {
	queue<int>q;
	q.push(index);
	v[index].visited = true;
	while (!q.empty()) {
		int top = q.front();
		q.pop();
		int k = 0;
		while (k < v[0].Nodenum) {
			if (v[top].ArcList[k]==1) {
				if (k == i) {
					v[k].parent = top;
					return;
				}
				if (v[k].visited == false) {
					v[k].visited=true;
					q.push(k);
					v[k].parent = top;
					//cout << v[k].data << ' ';
				}
			}
			k++;
		}
	}
}
int calcDepth(VexNode* v, int i) {
	int k = i,depth=0;
	while (v[k].parent != -1) {
		k = v[k].parent;
		depth++;
	}
	return depth;
}
void BFSTraverse(VexNode* v,int index) {
	if (!judge(v, index - 1)) {
		cout << "0.00" << endl;
		return;
	}
	int i,k=0;
	int distance[1000];
	for (i = 0; i < v[0].Nodenum; i++) {
		if (i == index - 1)
			continue;
		initialfalse(v);
		if (judge(v, i)) {
			BFS(v, index - 1, i);
			distance[k] = calcDepth(v, i);
			initialparent(v);
		}
		else
			distance[k] = 0;
		k++;
	}
	double result = 0;
	for (i = 0; i < v[0].Nodenum-1; i++) {
		result += distance[i];
	}
	result /= (v[0].Nodenum - 1);
	cout << "Cc(" << index << ")=" <<fixed<< setprecision(2) << 1.0/result << endl;
}
int main()
{
	VexNode* v = CreateGraph();
	int n,i,index;
	cin >> n;
	for (i = 0; i < n; i++) {
		cin >> index;
		BFSTraverse(v, index);
	}
	return 0;
}

以上即为本题的全部内容，可能存在一些可以改进的地方和不足的地方，欢迎大家评论相互交流，感谢观看！