课后作业：

假设一个有向图G采用邻接矩阵存储，分别设计实现以下要求的算法：

求出图G中每个顶点的入度

求出图G中每个顶点的出度

求出图G中出度最大的一个顶点，并输出该顶点编号。

计算图G中出度为0的顶点数

判断图G中是否存在边<i,j>

#include <errno.h>
#include <string.h>
#include <stdint.h>
#include <iostream>
#include <fstream>
#include<string>
#include <stack>
#include <vector>
#include <deque>
#include<stdlib.h>
#include <algorithm>
#pragma warning (disable: 4996)
using namespace std;
#define MAX 5
#define LIMT 99999
typedef struct
{
	int N;//顶点编号
	char name;//顶点信息
}ver;
typedef struct
{
	int adjmat[MAX][MAX];//邻接矩阵
	int v;//点个数
	int e;//边个数
	ver ver[MAX];//顶点数组
}matgraph;
void creat(matgraph*& G, int A[MAX][MAX], int v, int e)
{
	int i, j;
	G = (matgraph*)malloc(sizeof(matgraph));
	for (i = 0; i < v; i++) {
		G->ver[i].N = i;
		G->ver[i].name = 'A' + i;
	}
	for (i = 0; i < v; i++) for (j = v - 1; j >= 0; j--)G->adjmat[i][j] = A[i][j];
	G->e = e;
	G->v = v;
}
void mat_in_degree(matgraph* G) {
	int i, j, count;
	for (i = 0; i < G->v; i++) {
		count = 0;
		cout << "编号：" << G->ver[i].N << "	顶点：" << G->ver[i].name << "	入度：";
		for (j = 0; j < G->v; j++)
			if (G->adjmat[j][i] == 1)
				count++;
		cout << count << endl;
	}
}
void mat_out_degree(matgraph* G) {
	int i, j, count;
	for (i = 0; i < G->v; i++) {
		count = 0;
		cout << "编号：" << G->ver[i].N << "	顶点：" << G->ver[i].name << "	出度：";
		for (j = 0; j < G->v; j++)
			if (G->adjmat[i][j] == 1)
				count++;
		cout << count << endl;
	}
}
void mat_0_degree(matgraph* G) {
	int i, j, count = MAX;
	for (i = 0; i < G->v; i++) {
		for (j = 0; j < G->v; j++)
			if (G->adjmat[i][j] == 1) {
				count--;
				break;
			}
	}
	cout << "出度为0的个数：" << count << endl;
}
void mat_max_degree(matgraph* G) {
	int i, j, x_out, max_out = -1;
	for (i = 0; i < G->v; i++) {
		x_out = 0;
		for (j = 0; j < G->v; j++)
			if (G->adjmat[i][j] == 1) x_out++;
		if (x_out > max_out)max_out = x_out;
	}
	cout << "出度最大为：" << max_out << "	，出度最大的点编号为：";
	for (i = 0; i < G->v; i++) {
		x_out = 0;
		for (j = 0; j < G->v; j++)
			if (G->adjmat[i][j] == 1) x_out++;
		if (x_out == max_out)cout << G->ver[i].N << " ";
	}
	cout << endl;
}
void mat_judge_e(matgraph* G, int i, int j) {
	if (G->adjmat[i][j] == 1)cout << "存在边" << i << j << endl;
	else cout << "不存在边" << i << j << endl;
}
void Ppath(int path[], int i, int v) //前向递归查找路径上的顶点
{
	int k;
	k = path[i];
	if (k == v)
	{
		return;
	}
	Ppath(path, k, v);
	printf("%d", k);
}
void Dispath(int dist[], int path[], int s[], int n, int v)
{
	int i;
	for (i = 0; i < n; i++)
	{
		if (s[i] == 1)
		{
			printf("从%d到%d的最短路径长度为:%d\t路径为:", v, i, dist[i]);
			printf("%d", v);//输出路径上的起点
			Ppath(path, i, v); //输出路径上的中间点
			printf("%d\n", i);//输出路径上的终点
		}
		else
		{

			printf("从%d到%d不存在路径\n", v, i);
		}
	}
}
void BubbleSort(int* p, int length, int* ind_diff)
{
	for (int m = 0; m < length; m++)
	{
		ind_diff[m] = m;
	}

	for (int i = 0; i < length; i++)
	{
		for (int j = 0; j < length - i - 1; j++)
		{
			if (p[j] > p[j + 1])
			{
				float temp = p[j];
				p[j] = p[j + 1];
				p[j + 1] = temp;

				int ind_temp = ind_diff[j];
				ind_diff[j] = ind_diff[j + 1];
				ind_diff[j + 1] = ind_temp;
			}
		}
	}
}
void sort_path(int dist[MAX]) {//根据距离排序
	cout << "根据距离排序：";
	int ind[MAX] = { 0 };
	BubbleSort(dist, MAX, ind);
	for (int i = 0; i < MAX; i++)cout << ind[i];
	cout << endl;
}
void dijkstra(matgraph* G, int v)
{
	int mindis, i, j, u;
	int s[MAX];
	int dist[MAX];
	int path[MAX];
	for (i = 0; i < G->v; i++) {
		s[i] = 0;
		dist[i] = G->adjmat[v][i];
		if (G->adjmat[v][i] < LIMT)
			path[i] = v;
		else
			path[i] = -1;
	}
	s[v] = 1;
	path[v] = 0;
	for (i = 0; i < G->v; i++) {
		mindis = LIMT;
		for (j = 0; j < G->v; j++) {
			if (s[j] == 0 && dist[j < mindis]) {
				mindis = dist[j];
				u = j;
			}
		}
		s[u] = 1;
		for (j = 0; j < G->v; j++) {
			if (s[j] == 0) {
				if (G->adjmat[u][j] < LIMT && dist[u] + G->adjmat[u][j] < dist[j]) {
					dist[j] = dist[u] + G->adjmat[u][j];
					path[j] = u;
				}
			}
		}
	}
	Dispath(dist, path, s, G->v, v);
	sort_path(dist);
}
void dispmat(matgraph*G)  //图的邻接矩阵存储方式输出
{
	int i, j;
	printf("\n图的邻接矩阵存储\n");
	for (i = 0; i < G->v; i++)
	{
		printf("编号%d的顶点%c:", G->ver[i].N, G->ver[i].name);
		for (j = 0; j < G->v; j++)
			printf("%d ", G->adjmat[i][j]);  //没有权,这里的链表只输出邻接顶点编号
		printf("\n");
	}
}
int main()
{
	int adj_mat[MAX][MAX] =
	{                      //图的形状:
		{0,1,LIMT,1,LIMT},			//        1
		{LIMT,0,1,1,LIMT},			//     ↙↓↖
		{LIMT,LIMT,0,1,1},			//    2→ 3←0
		{LIMT,LIMT,LIMT,0,LIMT},     //     ↘↑↗
		{1,LIMT,LIMT,1,0}			//        4
	};
	int v = 5, e = 8;
	matgraph* G = NULL;
	creat(G, adj_mat, v, e);
	dispmat(G);
	mat_in_degree(G);
	mat_out_degree(G);
	mat_0_degree(G);
	mat_max_degree(G);
	int i = 2, j = 3;
	mat_judge_e(G, i, j);
	dijkstra(G, 0);
}