前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >图的基本算法实现(邻接矩阵与邻接表两种方法)

图的基本算法实现(邻接矩阵与邻接表两种方法)

作者头像
阳光岛主
发布2019-02-20 16:31:24
9240
发布2019-02-20 16:31:24
举报
文章被收录于专栏:米扑专栏

本博客前面文章已对图有过简单的介绍,本文主要是重点介绍有关图的一些具体操作与应用

阅读本文前,可以先参考本博客 各种基本算法实现小结(四)—— 图及其遍历

一、无向图

1 无向图——邻接矩阵

测试环境:VS2008

代码语言:javascript
复制
#include "stdafx.h"
#include <stdlib.h>
#include <malloc.h>
#define MAX_VEX 20
#define INFINITY 65535
int *visited;
struct _node
{
	int vex_num;
	struct _node *next;
};
typedef struct _node node, *pnode;
struct _graph
{
	char *vexs;
	int arcs[MAX_VEX][MAX_VEX];
	int vexnum, arcnum;
};
typedef struct _graph graph, *pgraph;
int locate(graph g, char ch)
{
	int i;
	for(i=1; i<=g.vexnum; i++)
		if(g.vexs[i]==ch)
			return i;
	return -1;
}
graph create_graph()
{
	int i, j, w, p1, p2;
	char ch1, ch2;
	graph g;
	printf("Enter vexnum arcnum: ");
	scanf("%d %d", &g.vexnum, &g.arcnum);
	getchar();
	for(i=1; i<=g.vexnum; i++)
		for(j=1; j<g.vexnum; j++)
			g.arcs[i][j]=INFINITY;
	g.vexs=(char *)malloc(sizeof(char));
	printf("Enter %d vexnum.../n", g.vexnum);
	for(i=1; i<=g.vexnum; i++)
	{
		printf("vex %d: ", i);
		scanf("%c", &g.vexs[i]);
		getchar();
	}
	printf("Enter %d arcnum.../n", g.arcnum);
	for(i=1; i<=g.arcnum; i++)
	{
		printf("arc %d: ", i);
		scanf("%c %c %d", &ch1, &ch2, &w);
		getchar();
		p1=locate(g, ch1);
		p2=locate(g, ch2);
		g.arcs[p1][p2]=g.arcs[p2][p1]=w;
	}
	return g;
}
int firstvex_graph(graph g, int i)
{
	int k;
	if(i>=1 && i<=g.vexnum)
		for(k=1; k<=g.vexnum; k++)
			if(g.arcs[i][k]!=INFINITY)
				return k;
	return -1;
}
int nextvex_graph(graph g, int i, int j)
{
	int k;
	if(i>=1 && i<=g.vexnum && j>=1 && j<=g.vexnum)
		for(k=j+1; k<=g.vexnum; k++)
			if(g.arcs[i][k]!=INFINITY)
				return k;
	return -1;
}
void dfs(graph g, int i)
{
	int k, j;
	if(!visited[i])
	{
		visited[i]=1;
		printf("%3c", g.vexs[i]);
		for(j=firstvex_graph(g, i); j>=1; j=nextvex_graph(g, i, j))
			if(!visited[j])
				dfs(g, j);
	}
}
void dfs_graph(graph g)
{
	int i;
	visited=(int *)malloc((g.vexnum+1)*sizeof(int));
	for(i=1; i<=g.vexnum; i++)
		visited[i]=0;
	for(i=1; i<g.vexnum; i++)
		if(!visited[i])
			dfs(g, i);
}
int _tmain(int argc, _TCHAR* argv[])
{
	graph g;
	g=create_graph();
	printf("DFS: ");
	dfs_graph(g);
	printf("/n");
	return 0;
}

运行结果:

==========================================================

2 无向图—— 邻接表

测试环境:VS2008

代码语言:javascript
复制
#include "stdafx.h"
#include <stdlib.h>
#include <malloc.h>
#define MAX_VEX 20
int *visited;
typedef struct _ArcNode
{
	int ivex; /* next ivex */
	struct _ArcNode *nextarc; /* next node */
	int *info; /* arc weight */
};
typedef struct _ArcNode ArcNode, *pArcNode;
struct _VNode
{
	char adjvex; /* note vex */
	ArcNode *firstarc;
};
typedef struct _VNode VNode;
struct _ALGraph
{
	VNode AdjList[MAX_VEX];
	int vexnum, arcnum;
	int kink;
};
typedef struct _ALGraph ALGraph;
int locate(ALGraph g, char ch)
{
	int i;
	for(i=1; i<=g.vexnum; i++)
		if(g.AdjList[i].adjvex==ch)
			return i;
	return -1;
}
ALGraph create_graph()
{
	int i, j, w, p1, p2;
	char ch1, ch2;
	pArcNode pnode, pnode1, pnode2;
	ALGraph g;
	printf("Enter vexnum arcnum: ");
	scanf("%d %d", &g.vexnum, &g.arcnum);
	getchar();
	
	printf("Enter %d vexnum.../n", g.vexnum);
	for(i=1; i<=g.vexnum; i++)
	{
		printf("vex %d: ", i);
		scanf("%c", &g.AdjList[i].adjvex);
		getchar();
		g.AdjList[i].firstarc=NULL;
	}
	printf("Enter arc.../n");
	for(i=1; i<=g.arcnum; i++)
	{
		printf("arc %d: ", i);
		scanf("%c %c", &ch1, &ch2);
		getchar();
		p1=locate(g, ch1);
		p2=locate(g, ch2);
		pnode1=(pArcNode)malloc(sizeof(ArcNode));
		pnode2=(pArcNode)malloc(sizeof(ArcNode));
		pnode1->ivex=p2; /* next ivex */
		pnode1->nextarc=g.AdjList[p1].firstarc;
		g.AdjList[p1].firstarc=pnode1;
		pnode2->ivex=p1; /* next ivex */
		pnode2->nextarc=g.AdjList[p2].firstarc;
		g.AdjList[p2].firstarc=pnode2;
	}
	return g;
}
int firstvex_graph(ALGraph g, int i)
{
	int k;
	if(i>=1 && i<=g.vexnum)	
		if(g.AdjList[i].firstarc)
			return g.AdjList[i].firstarc->ivex;
	return -1;
}
int nextvex_graph(ALGraph g, int i, int k)
{
	pArcNode pnode;
	if(i>=1 && i<=g.vexnum && k>=1 && k<=g.vexnum)
	{
		pnode=g.AdjList[i].firstarc;
		while(pnode->nextarc)
		{
			k=pnode->nextarc->ivex;
			if(!visited[k])
				return k;
			else
				pnode=pnode->nextarc;
		}
	}
	return -1;
}
void dfs(ALGraph g, int i)
{
	int k;
	if(!visited[i])
	{
		visited[i]=1;
		printf("%c", g.AdjList[i].adjvex);
		for(k=firstvex_graph(g, i); k>=1; k=nextvex_graph(g, i, k))
			if(!visited[k])
				dfs(g, k);
	}
}
void dfs_graph(ALGraph g)
{
	int i;
	visited=(int *)malloc((g.vexnum+1)*sizeof(int));
	for(i=1; i<=g.vexnum; i++)
		visited[i]=0;
	for(i=1; i<=g.vexnum; i++)
		if(!visited[i])
			dfs(g, i);
}
int _tmain(int argc, _TCHAR* argv[])
{
	ALGraph g;
	g=create_graph();
	dfs_graph(g);
	printf("/n");
	return 0;
}

运行结果:

==========================================================

本文参与 腾讯云自媒体同步曝光计划,分享自作者个人站点/博客。
原始发表:2010年06月21日,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档