阶段4 图 | Notion

10.13 day46 24年真题

degree[n]：记录各顶点的入度；
count：记录每轮遍历中入度为0的顶点个数；
index：记录入度为0的顶点下标；
关键是想到用一个数组记录各顶点的入度，以及每轮如何删除选取的顶点和边

int uniquely(MGraph G){
	int n = G.numVertics;
	int degree[n] = {0};//各顶点的度初始化为0
	for(int i = 0; i < n; i++){
		for(int j = 0; j < n; j++){
			if(G.Edge[i][j] == 1)
				degree[j]++;
		}
	}//for end
	
	//遍历n次，每次找入度为0的顶点
	for(int i = 0; i < n; i++){
		int count = 0;
		int index = -1;//遍历开始重置变量值
		for(int j = 0; j < n; j++){
			if(degree[i] == 0){
			count++;
			index = i;
			}
			if(count != 1)//多个入度为0，或没有入度为0
				return 0;
			degree[index] = -1;//将入度为0的删除（逻辑-标记）
			for(int j = 0; j < n; j++){
				if(G.Edge[index][j] == 1)
					degree[j]--;//删除这个顶点所散发出的出度（也就是其他结点的入度）
			}
		}//for.j end
	}//for.i end
	return 1;//完整走完循环 -》你是好人
}

10.15 day48 用邻接矩阵和邻接表创建一个图

//有向边：01 32 20 12 23
typedef struct {
	int numVertices,numEdges;//顶点数和边数
	char VerticesList[MAXV]//；顶点表
	int Edge[MAXV][MAXV]//邻接矩阵
}MGpaph；

void creat_graph(MGraph &G){
	int n = G.numVertices;
	for(int i = 0; i < n; i++){
		for(int j = 0; j < n; j++){
			G.Edge[i][j] = 0;//邻接矩阵初始化为0
		}
	}
	G.Edge[0][1] = 1;
	G.Edge[3][2] = 1;
	G.Edge[2][0] = 1;
	G.Edge[1][2] = 1;
	G.Edge[2][3] = 1;
}

//边表结点
typedef struct ArcNode{
	int Vertices;//该弧指向的顶点
	struct ArcNode* next;//下一条弧
}ArcNode;
//顶点表结点
typedef struct VNode{
	int data;//顶点信息
	ArcNode* firstarc;//第一条弧
}VNode,AdjList[MAX];//AdjList[]是这个结构体数组，每个数组元素都是一个顶点表结点

/*相当于：
VNode VNode;
VNode AdjList[MAX]*/

//邻接表
typedef struct{
	AdjList vertices;//邻接表
	int vnum,arcnum;//顶点数和边数
}ALGraph;
/*以参数ALGraph &G为例，访问成员变量：
G.vnum,G.arcnum;顶点数和边数
G.AdjList[i];第i个邻接表结点
G.AdjList[i].firstarc;第i个邻接表结点的第一条弧，实际上就是套娃调用的感觉*/

10.16 day49 （p22）2021 判断无向图中度为奇数的顶点个数是否为0个或两个

typedef struct {
	int numv,nume;
	char verticeslist[MAX];
	int Edge[MAX][MAX];
}MGraph;

int func(MGraph G){
	int count = 0;//记录满足条件的结点个数
	for(int i = 0; i < G.numv; i++){
		int temp = 0;//记录结点i的度数
		for(int j = 0; j < G.numv; j++){
			if(G.Edge[i][j] == 1)
				temp++;
		}
		if(temp % 2 != 0)
			count++;
	}
	if(count == 0 || count == 2)
		return 1;
	return 0;
}

11.5实现BFS

思想：类比树的层次遍历

将图的起始顶点的索引入队；
出队，访问索引，将出队顶点的相邻（且未入队过的）顶点入队；
数组visit记录当前该结点是否被访问；

typedef struct{
	int numv,nume;
	char Vertices[maxsize];
	int Edge[maxsize][maxsize];
}MGraph;

void BFS(MGraph G,int v){//其中v为开始结点
	initQueue(Q);
	int visit[maxsize] = {0};//记录访问过的顶点
	InQueue(Q,v);//起始顶点入队
	visit[v] = 1;//这里v只是索引号，不是顶点结点
	while(!isEmpty(Q)){
		v = DeQueue(Q);//队头出队
		printf("%d",v);//访问队头元素
		for(int i = 0; i < G.numv; i++){
			if(Edge[v][i]==1 && visit[i]==0){
				DeQueue(Q,i);
				visit[i] = 1;
			}	
		}
	}//while end
	return ;
}

11.10 实现DFS

从起始顶点开始遍历，对其所有相邻顶点（未访问过的）进行递归遍历；

void DFS(MGraph G,int v,int visit[]){//visit[i]表示顶点i是否被访问过
	printf("d",v);//访问当前结点
	visit[v] = 1;
	for(int i = 0; i < G.numv; i++){
		if(Edge[v][i]==1 && visit[i]==0)
			DFS(G,i,visit);
	}
}