数据结构(六) 图

图

实现有向图、无向图、有权图、无权图的邻接矩阵和邻接表表示方法

//实现有向图、无向图、有权图、无权图的邻接矩阵和邻接表表示方法

//邻接矩阵 
#define maxn 64 //最大顶点数 
typedef char vtype  //设当前顶点为字符类型 
typedef int adjtype  //设邻接矩阵A中元素aij为整型 
typedef struct 
{
   
	vtype V[maxn];  //顶点存储空间 
	adjtype A[maxn][maxn];  //邻接矩阵 
}mgraph;  //图的说明符 

void createmgraph(mgraph G)  //建立无向图的邻接矩阵法的算法 
{
   
	int i, j, n;
	vtype ch, u, v;
	adjtype w;
	i = n = 0;
	ch = getchar();  //输入顶点 
	while(ch != '#')  //'#'为结束符 
	{
   
		n++;  //顶点计数 
		if(n > maxn - 1) ERROR(n);  //溢出处理 
		G.V[i++] = ch;  //存入顶点 
		ch = getchar();
	}
	for(i = 0; i < n; i++)  //初始化邻接矩阵 
		for(j = 0; j < n; j++)
			G.A[i][j] = max;  //设max为机器表示的无穷大 
	scanf("%c %c %d", &u, &v, &w)  //读入一条边 
	while(u != '#')  //u='#'时结束 
	{
   
		i = locatevex(G, u);  //求u的序号 
		j = locatevex(G, v);  //求v的序号 
		G.A[i][j] = G.A[j][i] = w;  //邻接矩阵的赋值（对称） 
		scanf("%c %c %d", &u, &v, &w);  //读入下一条边 
	}
}


//邻接表 
typedef struct node  //链表节点类型 
{
   
	int adj;  //临界点域 
	int w;  //存放边上的权 
	struct node *next;  //指向下一弧或边 
}linknode;

typedef struct  //顶点类型 
{
   
	vtype data;  //顶点值域 
	linknode *farc;  //指向与本顶点关联的第一条弧或边 
}Vnode;

Vnode G[maxn];  //顶点表 

void createadj(vnode G[maxn])  //建立无向图邻接表算法 
{
   
	int i, j, n;
	linknode *p;
	vtype ch, u, v;
	i = n = 0;
	ch = getchar();   //读入顶点（设数据为字符） 
	while(ch != '#')  //'#'为结束符 
	{
   
		n++;  //顶点计数 
		G[i].data = ch;  //存入顶点 
		G[i].farc = NULL;  //置空表 
		i++;
		ch = getchar();
	}
	scanf("%c %c", u, v);  //读入一条边 
	while(u != '#')  //u='#'时结束 
	{
   
		i = locatevex(G, u);   //求u的序号 
		j = locatevex(G, v);  //求v的序号 
		
		//建立v1到v2的链接 
		p = (linknode*)malloc(sizeof(linknode));  //申请链表节点
		p -> adj = j;  //存入临界点序号 
		p -> next = G[i].farc;  //将p节点作为单链表的第一节点插入 
		G[i].farc = p;
		
		//由无向图的对称性建立V1到V2的链接 
		p = (linknode*)malloc(sizeof(linknode));
		p -> adj = i;
		p -> next = G[j].farc;
		G[j].farc = p;
		scanf("%c %c", &u, &v);  //读下一条边 
	}
}

实现图的深度优先搜索、广度优先搜索

//实现图的深度优先搜索、广度优先搜索

//深度优先搜索算法 
void DFS(Vnode G[], int v)
{
   
	int u;
	visit(G, v);
	visited[v] = True;
	u = firstadj(G, v);
	while(u >= 0)
	{
   
		if(visit[u] == False) DFS{
   G, u};
		u = nextadj(G, v, u);
	}
}

//广度优先搜索算法
void BFS(Vnode G[], int v)
{
   
	int u; 
	Clearqueue(Q);
	visit(G, v);
	visited[v] = True;
	Equeue(Q, v);
	while(!Emptyqueue(Q))
	{
   
		v = Delqueue(Q);
		u = firstadj(G, v);
		while(u >= 0)
		{
   
			if(visitied[u] == False)
			{
   
				visit(G, u);
				visited[u] = True;
				Equeue(Q, u);
			}
			u = nextadj(G, v, u);
		}
	
	}
}

实现 Dijkstra 算法、A* 算法

//实现 Dijkstra 算法、A* 算法
typedef struct
{
   
	int pi[n];
	int end;
}pathtype;

pathtype path[n];
int dist[n];
void Dijkstra(mgraph G, pathtype path[], int dist[], int v, int n)
{
   
	int i, count, S[n], m, u, w;
	for(i = 0; i < n; i++)
	{
   
		S[i] = 0;
		dist[i] = G.A[v][i];
		path[i].pi[0] = v;
		path[i].end = 0;
	}
	S[v] = 1;
	count = 1;
	while(count <= n-1)
	{
   
		m = max;
		for(w = 0; w <= n - 1; w++)
		{
   
			if(S[w] == 0 && dist[w] < m){
   
				u = w;
				m = dist[w];
			}
			if(m = max) break;
			S[u] = 1;
			path[u].end++;
			path[u].pi[end] = u;
			for(w = 0; w <= n - 1; w++)
			{
   
				if(S[w] == 0 && dist[w] > dist[u] + G.A[u][w])
				{
   
					dist[w] = dist[u] + G.A[u][w];
					path[w] = path[u];
				}
				count++;
			}
		}
	 } 
}

实现拓扑排序的 Kahn 算法、DFS 算法

//实现拓扑排序的 Kahn 算法、DFS 算法 
void Creatid(Vexnode G[], int n, int id[])
{
   
	int count, i;
	arcnode *p;
	for(i = 0; i < n; i++){
   
		count = 0;
		p = G[i].fin;
		while(p)
		{
   
			count++;
			p = p->hlink;
		}
		id[i] = count;
	}
}

void Topsort(Vexnode G[], int n)
{
   
	int i, j, k, count, id[];
	arcnode *p;
	Creatid(G, n, id);
	Clearstack(s);
	for(i = 0; i < n; i++)
		if(id[i] == 0)
			Push(s, i);
	count = 0;
	while(!Emptystack(s))
	{
   
		j = Pop(s);
		output(j, G[j].data);
		count++;
		p = G[j].fout;
		while(p)
		{
   
			k = p->head;
			id[k]--;
			if(id[k] == 0)
				Push(s, k);
			p = p->tlink;
		}
	}
	if(count == n)
		printf("This graph has not cycle.");
	else
		printf("This graph has cycle.");
}