数据结构——图

	>极大连通子图意思是：该子图是 G 连通子图，将G 的任何不在该子图中的顶点加入，子图不再连通。

-  有向图
	- 强连通图：任意两个顶点之间都存在一条有向路径
	- 强连通分量：极大强连通子图

#define INFINITY 1000  // 定义一个无穷数
#define MAX_VERTEX_NUM  // 最大顶点数

// 图类型枚举定义{有向图，有向网，无向图，无向网}
typedef enum {DG, DN, UDG, UDN} GraphKind;

typedef struct ArcCell{// 边定义
	VRType adj;  // VRType是顶点关系类型。
		// 对无权图，用1或0表示相邻否；
		// 对带权图（网络），则为权值类型。
	InfoType* info;  // 该弧相关信息指针
}ArcCell, AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM]

typedef struct { // 图的定义
	// 顶点信息
	VertexType vexs[MAX_VERTEX_NUM];  // 顶点向量
	AdjMatrix arcs;  // 邻接矩阵
	int vexnum, arcnum;  // 顶点数量和边的数量
	GraphKind kind;  // 图的种类标志
} MGraph;

/*---------------采用邻接矩阵建立无向网络---------------*/
// 算法思路
// 1. 输入总顶点数和总边数。
// 2. 依次输入点的信息存入顶点表中。
// 3. 初始化邻接矩阵，使每个权值初始化为极大值。
// 4. 构造邻接矩阵。 
void CreateUDN(MGraph &G){
	cin >> G.vexnum >> G.arcnum;  // 输入顶点数和边数
	for(int i = 0; i < G.vexnum; i++){
		// 建立顶点表
		G.vexs[i] = new char[10];
		cin >> G.vexs[i];  // 读入顶点信息
	}
	for(int i = 0; i < G.vexnum; i++)
		// 邻接矩阵初始化
		for(j = 0; j < G.vexnum; j++){
			G.arcs[i][j].adj = INFINITY;
			G.arcs[i][j].info = NULL;
		}
	for(k = 0; k < G.arcnum; k++){
		v1 = new char[10];
		v2 = new char[10];
		cin >> v1 >> v2 >> w;  // 读入e条边上的权
		i = LocateVex_MG(G, v1);  // 查找顶点v1在图中的位置
		j = LocateVex_MG(G, v2);
		G.arcs[i][j].adj = w;
		G.arcs[j][i].adj = w;
		delete v1;
		delete v2;
	}
}

int LocateVex_MG(MGraph G, VertexType x){
	// 查找顶点x在图中的位置
	for(int k = 0; strcmp(G.vexs[k], x); k++);
	return k;
}

typedef struct ArcNode{
	// 边结点定义
	int adjvex;  // 该弧所指向的顶点的位置
	struct ArcNode* nextarc;  // 指向下一条弧的指针
	InfoType* info;  // 该弧相关信息的指针
} ArcNode;

typedef struct VNode{
	// 顶点的结点定义
	// 表头结点
	VertexType data;  // 顶点信息
	ArcNode* firstarc;  // 指向第一条附属该顶点的弧
} VNode, AdjList[MAX_VERTEX_NUM];

typedef struct{
	// 图结构定义
	AdjList vertices;  // 图的顶点结构数组
	int vexnum, arcnum;  // 顶点数和边数
	int kind;
} ALGraph;

/*------------采用邻接表表示法构造有向图------------*/
void GreateDG_ALG(ALGraph &G){
	// 构造有向图
	cin >> G.vexnum >> G.arcnum;
	for(i = 0; i < G.vexnum; i++){
		// 建立顶点表
		G.vertices[i].data = new char[10];
		cin >> G.vertices[i].data;  // 读入顶点信息
		G.vertices[i].firstarc = NULL;
	}
	for(k = 0; k < G.arcnum; k++){
		// 建立边表
		v1 = new char[10]; 
		v2 = new char[10];
		cin >> v1 >> v2;
		i = LocateVex_ALG(G, v1);  // 弧尾
		j = LocateVex_ALG(G, v2);  // 弧头
		p = new ArcNode;
		p->adjvex = j;
		p->nextarc = G.vertices[i].firstarc;
		p->info = NULL;
		G.vertices[i].firstarc = p;  // 前插
	}
}

/*------------采用邻接表表示法构造无向图------------*/
void CreateUDG(ALGraph &G){
	cin >> G.vexnum >> G.arcnum;  // 输入总顶点数，总边数
	for(i = 0; i < G.vexnum; i++){
		// 输入各点，构造表头结点表
		cin >> G.vertices[i].data;  // 输入顶点值
		G.vertices[i].firstarc = NULL;  // 初始化表头结点的指针域为NULL
	}
	for(k = 0; k < G.arcnum; ++k){
		// 输入各边，构造邻接表
		cin >> v1 >> v2;  // 输入一条边依附的两个顶点
		i = LocateVex(G, v1);
		j = LocateVex(G, v2);
		p1 = new ArcNode;  // 生成一个新的边结点*p1 
		p1->adjvex = j;  // 邻接点序号为j
		// 将新结点*p1插入顶点vi的边表头部
		p1->nextarc = G.vertices[i].firstarc;
		G.vertices[i].firstarc = p1;
		p2 = new ArcNode;  // 生成另一个对称的新的边结点*p2
		p2->adjvex = i;
		// 将新结点*p2插入顶点vj的边表头部 
		p2->nextarc = G.vertices[j].firstarc;
		G.vertices[j].firstarc = p2;
	}
}

- info：边结点的数据域，保存边的权值等。
- tailvex：本条边的出发结点的地址。
- headvex：本条边的终止结点的地址。
- hlink：终止结点相同的边中的下一条边的地址。
- tlink：出发结点相同的边中的下一条边的地址。typedef struct ArcBox{
	// 弧结点结构表示
	int tailvex, headvex;
	InfoType* info;
	struct ArcBox* hlink,* tlink;
} ArcBox;

typedef struct VexNode{
	// 顶点的结构表示
	VertexType data;
	ArcBox* firstin,* firstout;
} VexNode;

typedef struct{
	// 有向图的十字链表
	VexNode xlist[MAX_VERTEX_NUM];  // 顶点结点
	int vexnum, arcnum;  // 有向图的当前顶点数和弧数
} OLGraph;

void CreatDG_OLG(OLGraph &G){
	// 构造有向图
	cin >> G.vexnum >> G.arcnum;  // 顶点数，弧数
	for(i = 0; i < G.vexnum; i++){
		// 建立顶点表
		G.xlist[i].data = new char[10];
		cin >> G.xlist[i].data;  // 读入顶点信息
		G.xlist[i].firstin = NULL;
		G.xlist[i].firstout = NULL;
	}
	for(k = 0; k < G.arcnum; k++){
		// 建立十字链表
		v1 = new char[10];
		v2 = new char[10];
		i = LocateVex_OLG(G, v1);
		j = LocateVex_OLG(G, v2);
		p = new ArcBox;
		p->info = NULL;
		p->headvex = j;  // 弧的终点
		p->tailvex = i;  // 弧的起点
		p->hlink = G.xlist[j].firstin;  // 前插
		p->tlink = G.xlist[i].firstout;
		G.xlist[j].firstin = G.xlist[i].firstout = p;
	}
}undefined无向图的邻接多重表存储表示

int visited[MAX_VERTEX_NUM];  // 全局变量
void Visit(VertexType x){cout << x << " ";}

/*-----------图的深度优先搜索算法（连通图）-----------*/
void DFS(Graph G, int v){
	Visit(v); 
	visited[v] = true;
	// FirstAdjVex(G, v) 表示v的第一个邻接点
	// NextAdjVex(G, v, w) 表示v相对于w的下一个邻接点
	// w >= 0 表示邻接点存在
	for(w = FirstAdjVex(G, v); w >= 0; w = NextAdjVex(G, v, w))
		if(!visited[w]) DFS(G, w);
}

/*-----------图的深度优先搜索算法（非连通图）-----------*/
void DFSTraverse(Graph G){
	for(v = 0; v < G.vexnum; ++v) visited[v] = false;  // 访问标志数初始化
	for(v = 0; v < G.vexnum; ++v)
		if(!visited[v]) DFS(G, v);
}

/*-----------邻接矩阵表示图的深度优先搜索遍历-----------*/
void DFS_AM(AMGraph G, int v){
	// 图G为邻接矩阵类型
	cout << v;
	// 访问第v个结点
	visited[v] = true;
	for(w = 0; w < G.vexnum; w++){
		// 一次检查邻接矩阵v所在行
		if((G.arcs[v][w] != 0) && (!visited[w]))
			DFS(G, w);
		// w是v的邻接点，如果w未访问，则递归调用DFS
	}
}

/*-----------邻接表表示图的深度优先搜索遍历-----------*/
void DFS_AL(ALGraph G, int v){
	// 图G为邻接表类型
	cout << v;
	visited[v] = true;  // 访问第v个顶点
	p = G.vertics[v].firstarc;  // p指向v的边链表的第一个边结点
	while(p != NULL){
		// 边结点非空 
		w = p->adjvex;  //表示w是v的邻接点
		if(!visited[w]) DFS(G, w);  // 如果w未访问，则递归调用DFS
			p = p->nextarc;  // p指向下一个边结点
		}
}

/*------------广度优先非递归遍历连通图G（连通图）------------*/
void BFS(Graph G, int v){
	cout << v;
	visited[v] = true;  // 访问第v个顶点
	InitQueue(Q);
	EnQueue(Q, v);
	while(!QueueEmpty(Q)){
		DeQueue(Q, u);
		for(w = FirstAdjVex(G, u); w >= 0; w = NextAdjVex(G, u, w)) 
			if(!visited[w]){
				// w为u的尚未访问的邻接顶点
				cout << w;
				visited[w] = false;
				EnQueue(Q, w);  // w进队
			}
	}
}

/*------------广度优先非递归遍历连通图G（非连通图）------------*/
void BFSTraverse(Graph G){
	for(v = 0; v < G.vexnum; ++v) visited[v] = false;  // 访问标志数初始化
	for(v = 0; v < G.vexnum; ++v)
		if(!visited[v]) BFS(G, v);
}