#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define MaxSize 8

typedef struct ArcNode {                    //【边结点】 
    int adjvex;                     //该边所指向的顶点的位置
    struct ArcNode* nextarc;        //指向下一条边的指针
}ArcNode;

typedef struct VNode {                    //【表头结点】 
    char data[3];                //顶点信息--每个顶点的数据是一个由3个字符组成的字符串（或字符数组）V0,V1 
    ArcNode* firstarc;    //指向第一条依附该顶点的边的指针
}VNode; 

typedef struct {
	VNode vertices[MaxSize];   	//邻接表(vertices为数组名) 
	int vexnum, arcnum;                 //图的当前顶点数和边数
}ALGragh;


//1、构建图：参考P151算法6.2
void InitList(ALGragh &G, char a[][3]) {      
    int i, j;
    for (i = 0; i < G.vexnum; i++) {
		for (j = 0; j < 3; j++) 
			G.vertices[i].data[j] = a[i][j]; //todo list     //输入顶点值 
        G.vertices[i].firstarc = NULL; //todo list        //初始化表头结点的指针域为NULL  
    }

    printf("请输入各边所依附的两个顶点的位置\n");
    for (int k = 0; k < G.arcnum; k++) {
        scanf("%d %d", &i, &j);
//生成一个新的边结点*p1:
        ArcNode* p1 = (ArcNode*)malloc(sizeof(struct ArcNode));    
 		p1->adjvex = j;
        p1->nextarc = G.vertices[i].firstarc;
        G.vertices[i].firstarc = p1; //todo list  设此邻接点序号为j，并将新结点*p1插入顶点vi的边表头部(头插法)

        //生成另一个对称的新的边结点*p2：
        ArcNode* p2 = (ArcNode*)malloc(sizeof(struct ArcNode));   
        p2->adjvex = i;
        p2->nextarc = G.vertices[j].firstarc;
        G.vertices[j].firstarc = p2; //todo list  设此邻接点序号为i，并将新结点*p2插入顶点vj的边表头部(头插法)
    }
}


//2、输出邻接表
void PrintInf(ALGragh G) {    
    int i;
    ArcNode* p;    //struct ArcNode* p;
    printf("输出图的邻接表：\n");
    for (i = 0; i < G.vexnum; i++) {                          //G.vexnum表示图中的顶点数量。
        printf("%s   ", G.vertices[i].data);                 //打印当前顶点 i 的数据 (%s 被用于表示待插入的数据是字符串类型)
        for (p = G.vertices[i].firstarc; p != NULL; p = p->nextarc)  //for循环遍历当前顶点 i 的所有邻接顶点，并打印这些邻接顶点。
            printf("%d   ", p->adjvex);
        printf("\n");
    }
}


//3、对采用【邻接表】表示的图，做深度优先遍历：参考P157算法6.6
void DFS_AL(ALGragh G, int visited[], int v) { 
    printf("%s ", G.vertices[v].data); // 访问第 v 个顶点
	ArcNode* p;
	int w;
	visited[v] = 1;

    p = G.vertices[v].firstarc; //todo list     //将 p 初始化为指向顶点 v 的第一个邻接点的指针  
    while (p != NULL) { //todo list     //while循环：对v未被访问的邻接顶点w递归调用DFSTraverse 函数；并寻找v相对于w的下一个邻接点
        w = p->adjvex;
        if (!visited[w]) {
            DFS_AL(G, visited, w);
        }
        p = p->nextarc;
    }
       
}

//4、深度优先遍历非连通图（也兼容连通图） ：  参考P156算法6.4      （可用于计算连通分量的个数，但需要增加count变量，如下算法5） 
void DFSTraverse_AL(ALGragh G, int visited[]) {   
    int v;
    for (v = 0; v < G.vexnum; v++)               //初始化标记数组,置为0
        visited[v] = 0;
    for (v = 0; v < G.vexnum; v++)
        if (!visited[v]) { //todo list  如果有顶点没有被访问，那就以它为起点遍历所在的连通分量
            DFS_AL(G, visited, v);
        }
    printf("\n");
}



//5、计算连通分量的个数
void Count(ALGragh G, int visited[]) {    
    int count = 0, v;
    for (v = 0; v < G.vexnum; v++)               //初始化标记数组,置为0
        visited[v] = 0;
    for (v = 0; v < G.vexnum; v++)
        if (!visited[v]) { //todo list  如果有顶点没有被访问，那就以它为起点遍历所在的连通分量，连通分量个数加一
            DFS_AL(G, visited, v);
            count++;
        }
    printf("\n");
    printf("连通分量个数:%d\n", count);
}


//6、判断有无路径可达
void Judge(ALGragh G, int visited[], int v, int u) {    
	for (int i = 0; i < G.vexnum; i++)
        visited[i] = 0;
    DFS_AL(G, visited, v); //todo list  以v作为起点，做深度优先遍历图，在此过程中不断将所有相互连接的邻接结点的visited[u]更新为1
    if (visited[u] == 1){
        printf("\n");
		printf("V%d与V%d有路径可达!\n", v, u);
	}
    else{
    	printf("\n");
        printf("V%d与V%d无路径可达!\n", v, u);
    }
}



int main() {
    int v, u;    //j是边的数目,v、u为顶点位置
	int choose = -1;
	//a是一个二维字符数组，存储顶点信息(字符串还得保存结尾的空字符\0，因此列数需要设为3)
	char a[MaxSize][3] = { "V0", "V1", "V2", "V3", "V4", "V5", "V6", "V7" };  
	int visited[MaxSize] = { 0 };
	ALGragh G;
	G.vexnum = MaxSize;

	printf("*****************************************************\n");
	printf("**********               实验八               *******\n");
	printf("*****************************************************\n");
	printf("**********     1.构建图                       *******\n");
	printf("**********     2.输出邻接表                   *******\n");
	printf("**********     3.深度优先遍历的结果             *******\n");
	printf("**********     4.判断两个点之间是否有路径可达 *******\n");
	printf("**********     5.输出连通分量的个数           *******\n");
	printf("**********     0.退出                         *******\n");
	printf("*****************************************************\n");
	while(choose) {
		printf("请输入你的选择项：");
		scanf("%d", &choose);
		switch(choose){
			case 1:
				printf("输入边数:");
				scanf("%d", &G.arcnum);
				InitList(G, a);
				break;
			case 2:
				PrintInf(G);
				break;
			case 3:	
				printf("深度优先遍历结果：");
    			DFSTraverse_AL(G, visited);  // 3 深度优先遍历图
    			//DFS_AL(G, visited,v);   //如果是一个连通图，直接调用 DFS_AL也可以得到正确结果 
    			printf("\n");
    			break;
			case 4:
				printf("输入要判断的两个点:");
				scanf("%d %d", &v, &u);
				Judge(G, visited, v, u); 
				break;
			case 5:
				Count(G, visited);
				break;
			case 0:
				exit(0);
				break;
		}
	}

    return 0;
}