有用資料結構---圖的操作和算法

#include<stdio.h>
#include<stdlib.h>
#define MAXVEX 20
#define INFINITY 65535
typedef char vertexType;
typedef int edgeType;
typedef int Boolean;
typedef int Pathmatirx[MAXVEX];		//用于存儲最短路徑下标的數組
typedef int ShortPathTabl[MAXVEX];	//用于存數最短路徑權值和的數組
Boolean visited[MAXVEX];
//圖的鄰接矩陣結構
typedef struct{
	vertexType vexs[MAXVEX];
	edgeType arc[MAXVEX][MAXVEX];
	int numVertexs, numEdges;
}Mgraph;

//鄰接矩陣圖的建立
void creatGraph(Mgraph *G){
	int i, j,k,w;
	printf("輸入頂點數和邊數\n");
	scanf_s("%d%d", &(G->numVertexs), &(G->numEdges));
	printf("輸入頂點資訊\n");
	getchar();
	for (i = 0; i < G->numVertexs; i++)
		scanf_s("%c", &(G->vexs[i]));
	//矩陣初始化
	for (i = 0; i < G->numVertexs;i++)
	for (j = 0; j < G->numVertexs; j++)
		G->arc[i][j] = INFINITY;
	printf("輸入頂點上下标i,j和權重w\n");
	getchar();
	for (k = 0; k < G->numEdges; k++)
	{
		scanf_s("%d%d%d", &i, &j, &w);
		G->arc[i][j] = w;
		G->arc[j][i] = w;	//無向圖，矩陣對稱
	}
}

////順序隊列節點
//typedef struct{
//	char data[MAXVEX];
//	int front;
//	int rear;
//}Queue;
//
////初始化隊列
//void InitQueue(Queue* q){
//	q->front = 0;
//	q->rear = 0;
//}
//
////傳回隊列長度
//int QueueLength(Queue *q){
//	return (q->rear - q->front + MAXVEX) % MAXVEX;
//}
//
////推斷隊列是否已滿
//bool isFull(Queue *q){
//	if ((q->rear + 1) % MAXVEX == q->front)
//		return true;
//	else
//		return false;
//}
//
////入隊列
//bool enQueue(Queue *q,char e){
//	if (!isFull(q)){
//		q->data[q->rear] = e;
//		q->rear = (q->rear+1) % MAXVEX;
//		return true;
//	}
//	else
//		return false;
//}
//
////出隊列
//bool Dequeue(Queue *q, char *e){
//	if (q->front == q->rear)
//		return false;
//	*e = q->data[q->front];
//	q->front = (q->front + 1) % MAXVEX;
//	return true;
//}

////圖的鄰接表結構
//邊節點
//typedef struct edgeNode{
//	int adjvex;		//目前點的下标
//	edgeType weight;
//	struct edgeNode *next;	//指向下一個鄰接點
//}edgeNode;
//typedef struct vertexNode{
//	vertexType data;	//頂點資料域
//	struct edgeNode *firstEdge;
//}vertexNode,AdjList[MAXVEX];
//typedef struct{
//	AdjList adjList;
//	int numVertexes, numEdges;	//圖中目前頂點數和邊數
//}GraphAdjList;

//鄰接表圖的建立
//void creatGraph(GraphAdjList *g){
//	int i, j, k;
//	edgeNode *e;
//	printf("輸入頂點數和邊數\n");
//	scanf_s("%d%d", &g->numVertexes, &g->numEdges);
//	getchar();
//	for (i = 0; i < g->numVertexes; i++){
//		scanf_s("%c", &g->adjList[i].data);
//		g->adjList[i].firstEdge = NULL;
//	}
//	for (k = 0; k < g->numEdges; k++){
//		printf("輸入邊上的頂點序号\n");
//		scanf_s("%d%d", &i, &j);
//		e = (edgeNode*)malloc(sizeof(edgeNode));
//		e->adjvex = j;
//		e->next = g->adjList[i].firstEdge;
//		g->adjList[i].firstEdge = e;
//		e = (edgeNode*)malloc(sizeof(edgeNode));
//		e->adjvex = i;
//		e->next = g->adjList[j].firstEdge;
//		g->adjList[j].firstEdge = e;
//	}
//}

//鄰接矩陣的深度優先算法
//void DFS(Mgraph *g,int i){
//	visited[i] = true;
//	printf("%c ", g->vexs[i]);
//	for (int j = 0; j < g->numVertexs; j++){
//		if (g->arc[i][j] == 1 && !visited[j])
//			DFS(g, j);
//	}
//}
//void DFSTraverse(Mgraph *g){
//	int i;
//	for (i = 0; i < g->numVertexs; i++)
//		visited[i] = false;
//	for (i = 0; i < g->numVertexs; i++){
//		if (!visited[i])
//			DFS(g, i);
//	}
//}
//鄰接表的深度優先周遊算法
//void DFS(GraphAdjList *a,int i){
//	visited[i] = true;
//	edgeNode *p;
//	p = a->adjList[i].firstEdge;
//	printf("%c ", a->adjList[i].data);
//	while (p){
//		if (!visited[p->adjvex])
//			DFS(a, p->adjvex);
//		p = p->next;
//	}
//}
//void DFSTraverse(GraphAdjList *a){
//	int i;
//	for (i = 0; i < a->numVertexes; i++)
//		visited[i] = false;
//	for (i = 0; i < a->numVertexes; i++)
//	{
//		if (!visited[i])
//			DFS(a, i);
//	}
//}

//删除鄰接表圖
//void del(GraphAdjList *a, int i){
//	edgeNode *p;
//	visited[i] = true;
//	p = a->adjList[i].firstEdge->next;
//	free(a->adjList[i].firstEdge);
//	a->adjList[i].firstEdge->next = p->next;
//	while (p){
//		if (!visited[p->adjvex])
//			del(a, p->adjvex);
//		p = p->next;
//	}
//}
//void delGraph(GraphAdjList *a){
//	int i;
//	for (i = 0; i < a->numVertexes; i++){
//		if (!visited[i])
//			del(a, i);
//	}
//}

//鄰接矩陣圖的廣度優先周遊
//void BFS(Mgraph G){
//	int i;
//	char e;
//	for (i = 0; i < G.numVertexs; i++)
//		visited[i] = false;
//	Queue p;
//	Queue *q = &p;
//	InitQueue(q);
//	for (i = 0; i < G.numVertexs; i++){
//		if (!visited[i]){
//			visited[i] = true;
//			enQueue(q, G.vexs[i]);
//			while (q->front != q->rear){
//				Dequeue(q, &e);
//				printf("%c ", e);
//				for (int j = 0; j < G.numVertexs; j++){
//					if (!visited[j] && G.arc[i][j] == 1){
//						visited[j] = true;
//						enQueue(q, G.vexs[j]);
//					}
//
//				}
//			}
//		}
//
//	}
//}


//prim最小生成樹算法
void MinSpanTree_prim(Mgraph G){
	int min, i, j, k;
	int adjvex[MAXVEX];
	int lowcost[MAXVEX];
	lowcost[0] = 0;
	adjvex[0] = 0;
	for (i = 1; i < G.numVertexs; i++){
		lowcost[i] = G.arc[0][i];
		adjvex[i] = 0;
	}
	for (i = 1; i < G.numVertexs; i++){
		min = INFINITY;
		j = 1;
		k = 0;
		while (j < G.numVertexs){
			if (lowcost[j] != 0 && lowcost[j] < min){
				min = lowcost[j];
				k = j;
			}
			j++;
		}
		printf("(%d %d) ", adjvex[k], k);
		lowcost[k] = 0;
		for (j = 1; j < G.numVertexs; j++){
			if (lowcost[j] != 0 && G.arc[k][j] < lowcost[j]){
				lowcost[j] = G.arc[k][j];
				adjvex[j] = k;
			}
		}
	}
}
//void MinSpanTree_prim(Mgraph G){
//	int i, j, k, min;
//	int adjvex[MAXVEX];
//	int lowcost[MAXVEX];
//	lowcost[0] = 0;
//	adjvex[0] = 0;
//	for (i = 1; i < G.numVertexs; i++){
//		lowcost[i] = G.arc[0][i];
//		adjvex[i] = 0;
//	}
//	for (i = 1	; i < G.numVertexs; i++){
//		min = INFINITY;
//		k = 0;
//		j = 1;
//		while (j < G.numVertexs){
//			if (lowcost[j] != 0 && lowcost[j]<min){
//				min = lowcost[j];
//				k = j;
//			}
//			j++;
//		}
//		lowcost[k] = 0;
//		printf("(%d,%d)", adjvex[k], k);
//		for (j = 1; j < G.numVertexs; j++){
//			if (lowcost[j] != 0 && lowcost[j] > G.arc[k][j]){
//				lowcost[j] = G.arc[k][j];
//				adjvex[j] = k;
//			}
//		}
//	}
//}
//迪傑斯特拉

//迪傑斯特拉最短路徑算法
//p[v]的值為前驅頂點下标,D[v]表示從v0到v最短路徑長度和
void ShotestPath_Dijkstra(Mgraph G, int v0, Pathmatirx *P, ShortPathTabl *D){
	int v, w, k, min;
	int visited[MAXVEX];			//visited[i]=1表示求得v0到vi的最短路徑
	for (v = 0; v < G.numVertexs; v++){
		visited[v] = 0;				//所有頂點初始化為未知最短路徑狀态
		(*D)[v] = G.arc[v0][v];		//将與v0點有連線的頂點加上權值
		(*P)[v] = 0;				//初始化路徑數組p為0
	}
	(*D)[v0] = 0;					//v0到v0的路徑為0
	visited[v0] = 1;				//v0到v0不須要求路徑
	//開始主循環，每次求得v0到某個v的最短路徑
	for (v = 1; v < G.numVertexs; v++){
		min = INFINITY;
		//尋找離v0近期的頂點
		for (w = 0; w < G.numVertexs; w++){
			if (!visited[w] && (*D)[w] < min){
				k = w;
				min = (*D)[w];		//w頂點離v0點更近
			}
		}
		visited[k] = 1;
		//修正目前最短路徑及距離
		for (w = 0; w < G.numVertexs; w++){
			//假設經過v頂點的路徑比方今這條路徑的長度短的話
			if (!visited[w] && (min + G.arc[k][w]) < (*D)[w]){
				//說明找到了更短的路徑，修正	D[w]和P[w]
				(*D)[w] = min + G.arc[k][w];
				(*P)[w] = k;
			}
		}
	}
}
//輸出最小路徑
void print(Pathmatirx *P,int n){
	if (n == 0){
		printf("0\n");
		return;
	}
	printf("%d<-", n);
	print(P, (*P)[n]);
}
int main(){
	Pathmatirx P[MAXVEX];
	ShortPathTabl D[MAXVEX];
	int v0 = 0;
	Mgraph G;
	creatGraph(&G);
	//MinSpanTree_prim(G);
	ShotestPath_Dijkstra(G, v0, P, D);
	print(P,8);
	system("pause");
	return 0;
}