图

7.强连通图个点之间均可达（有向图）。

一、邻接矩阵存储图及遍历

结构体数组实现方式

1.初始化结构体与数组

typedef struct
{
	int idx;     //idx存储内容为symbol的数组在Node中的下标
	char symbol;   //symbol存储该节点的内容
}Node;
int edge[MaxSize][MaxSize] = { 0 };   //edge存储点与点之间是否存在边，若存在边即为1，不存在则为0（邻接矩阵）
Node node[300];

2.给定一串字符，以及字符之间的连接状况，建立邻接矩阵。 

void CreateAM(string a)
{
	//a为给定字符串
	for (int i = 0; i < a.size(); i++)
	{
		node[a[i]].idx = i; //标记a[i]在node数组中的下标
		node[i].symbol = a[i]; 
	}
	char x, y;
	cout << "请输入连接个数:" << endl;
	int m;
	cin >> m;
	cout << "请输入各连接:" << endl;
	for (int i = 0; i < m; i++)
	{
		cin >> x >> y;
		edge[node[x].idx][node[y].idx] = 1;
		edge[node[y].idx][node[x].idx] = 1;
        //x,y为给定的字符之间的连接状况,无向图，正反连接
	}
}

3.深度优先遍历

int st[MaxSize] = { 0 };//st[i]数组表示i是否被访问过，若未被访问过则为0，反之为1。
void dfs(char c,Node a[],int n)//从字符c开始深度优先遍历图
{//n 代表图的节点数，a[]代表存储的节点
	cout << c << " ";//输出c
	int idx = a[c].idx;  //idx标记c在a数组中的下标
	st[idx] = 1;         //将此节点的st值置为1代表此节点被访问过
	for (int i = 0; i < n; i++)
	{
		if (edge[idx][i] == 1 && st[i] == 0)//判断该点与其他节点是否有链接，若有链接且被连接的点未被访问过则遍历该点
		{
			st[i] = 1;              //标记该点
			dfs(a[i].symbol, a, n);
		}
	}
}

4.宽度优先遍历

void bfs(char c, Node a[], int n)
{
	//st数组在bfs中的作用是保证每个元素只能加入队列一次，防止了元素的重复访问。
	int front = -1;
	int rear = -1;
	int q[MaxSize];
	//建立一个队列存储遍历顺序
	q[++rear] = a[c].idx;
	st[a[c].idx] = 1;         //st标记该节点代表已经被加入队列
	while (front != rear)//队列不为空就继续遍历
	{
		int node = q[++front];//从队列中取出头节点
		cout << a[node].symbol << " ";
		for (int i = 0; i < n; i++)
		{
			if (edge[node][i] == 1 && st[i] == 0)
			{
				q[++rear] = i;
				st[i] = 1;   //加入队列后立即将其st置为1
			}
		}
	}
}

 map存储实现方式

1.初始化

map<char, int>node;       //char int类型键值对，存储char元素对应的下标
string a;                 //输入的节点字符串
int edge[MaxSize][MaxSize] = { 0 }; //点与点之间的是否有边

2.建立邻接矩阵 

cin >> a;            //输入节点字符串
	for (int i = 0; i < a.size(); i++)
	{
		node[a[i]] = i;  //标记字符a[i]在邻接矩阵中的下标
	}
	int m; 
	cin >> m;            //输入边的个数
	for (int i = 0; i < m; i++)//建立邻接矩阵
	{
		char x, y;
		cin >> x >> y;
		int xi = node[x];
		int yi = node[y];
		edge[xi][yi] = 1;
		edge[yi][xi] = 1;
	}

3.深度优先遍历

bool st[MaxSize] = { false };
void dfs(char c)
{
	cout << c;
	char idx = node[c];
	st[idx] = true;
	for (int i = 0; i < a.size(); i++)
	{
		if (edge[idx][node[a[i]]] == 1 && st[node[a[i]]] == false)
		{
			dfs(a[i]);
		}
	}
}

4.宽度优先遍历

char find(int x)     //find函数用于查找下标为x的点对应的char字符
{
	for (int i = 0; i < a.size(); i++)
	{
		if (node[a[i]] == x)
		{
			return a[i];
		}
	}
}
void bfs(char c)
{
	int rear = -1;
	int front = -1;
	int q[MaxSize] = { 0 };
	q[++rear] = node[c];
	st[node[c]] = true;
	while (rear != front)
	{
		int idx = q[++front];
		cout << node[find(idx)];
		for (int i = 0; i < a.size(); i++)
		{
			if (edge[idx][i] == 1 && st[i] == false)
			{
				q[++rear] = i;
				st[i] = true;
			}
		}
	}
}