0.数据结构

typedef struct{
	int Vertics[maxsize];//顶点结点
	int Edge[maxsize][maxsize];
	int numv,nume;
}MGraph;

typedef struct ArcNode{
	int data;
	struct ArcNode* next;
}ArcNode;

typedef struct VNode{
	int data;
	struct ArcNode* first;
}VNode;

typedef struct{
	struct VNode* List[maxsize];
	int numv,nume;
}ALGraph;

1.DFS

• 每次选取与当前结点相连，且未被访问过的结点；

void DFS(MGraph G,int v,int visit[]){
	printf("%d",v);
	visit[v] = 1;
	for(int i = 0; i < G.numv; i++){
		if(Edge[v][i]!=0 && visit[i]!=1)
			DFS(G,i,visit);
	}
}

void DFS(ALGraph G,int v,int visit[]){
	printf("%d",v);
	visit[v] = 1;
	ArcNode* p = G.List[v].first;
	while(p != NULL){
		if(!visit[p->data])
			DFS(G,p->data,visit);
		p = p->next;
	}
}

2.BFS

1. 起始顶点的索引入队；
2. 访问当前顶点，并将与当前顶点相邻且未访问过的结点入队；
3. 辅助数组visit[ ]记录结点i是否被访问过，入队时，将visit对应置为1即可；

void BFS(MGraph G,int v){
	InitQueue(Q);
	int visit[maxsize] = {0};
	EnQueue(Q,v);//当前顶点的索引入队
	visit[v] = 1;
	while(!isEmpty(Q)){
		v = DeQueue(Q);//队头元素出队;
		printf("%d",v);
		for(int i = 0; i < G.numv; i++){
			if(G.Edge[v][i]!=0 && visit[i]!=1){
				EnQueue(Q,i);
				visit[i] = 1;
			}
		}	
	}
	return ;
}

void BFS(ALGraph G,int v){
	InitQueue(Q);
	int visit[maxsize] = {0};
	EnQueue(Q,v);
	visit[v] = 1;
	while(!isEmpty(Q)){
		v = DeQueue(Q);
		printf("%d",v);
		ArcNode *p = G.List[v].first;
		while(p != NULL){
			if(visit[p->data] == 0){//相邻且未访问过的边入队
				EnQueue(Q,p->data);
				visit[p->data] = 1;
			}
			p = p->next;
		}
	}
	return ;
}

3.判断无向图中度为奇数的顶点个数是否为0个或两个（21）

bool func(MGraph G){
	int count = 0;//记录度为奇数的顶点个数
	for(int i = 0; i < G.numv; i++){
		for(int j = 0; j < G.numv; j++){
			int t = 0;//记录当前结点度的个数
			if(G.Edge[i][j] == 1)
				t++;
		}
		if(t % 2 != 0)
			count++;
	}
	if(count==0 || count==2)
		return true;
	return false;
}

bool func(ALGraph G){
	int count = 0;
	for(int i = 0; i < G.numv; i++){
		ArcNode *p = G.List[i]->first;
		int t = 0;//记录当前结点度的个数
		while(p != NULL){
			t++;
			p = p->next;
		}
		if(t % 2 != 0)
			count++;
	}
	if(count==0 || count==2)
		return true;
	return false;
}

4.输出有向图G中所有K结点，并返回K结点的个数

• K结点指出度大于入度的结点；

int node_K(MGraph G){
	int count;//记录K结点的个数
	for(int i = 0; i < G.numv; i++){
		int in = 0;//该结点入度个数
		int out = 0;//该结点出度个数
		for(int j = 0; j < G.numv; j++){
			if(G.Edge[i][j] == 1)
				out++;
			if(G.Edge[j][i] == 1)
				in++;
		}
		if(out > in){
			printf("%c",G.Vertices[i]);
			count++;
		}
	}
	return count;
}

int note_K(ALGraph G){
	int count;
	for(int i = 0; i < G.numv; i++){
		int in = 0,out = 0;
		ArcNode *p = G.List[i].fitst;
		//求出度
		while(p != NULL){
			out++;
			p = p->next;
		}
		//求入度
		for(int j = 0; j < G.numv; j++){
			ArcNode *q = G.List[j].first;
			while(q != NULL){
				if(q->data == p->data)
					in++;
				q = q->next;
			}
		}
		if(out > in){
			printf("%c",G.List[i].data);
			count++;	
		}
	}
	return count;
}