欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

邻接矩阵表示图的深度优先搜索遍历

程序员文章站 2022-05-19 19:53:23
...

这次用了点c++,用c的话需要考虑吞字符,一开始没想到,写完了也就没改。
运行结果:
邻接矩阵表示图的深度优先搜索遍历

#include <iostream>
using namespace std;
#define MaxInt 32767
#define MVNum 100
#define OK 1;
bool visited[MVNum];
typedef int Status;
typedef char VerTexType;
typedef int ArcType;
typedef struct
{
	VerTexType vexs[MVNum];
	ArcType arcs[MVNum][MVNum];
	int vexnum,arcnum;
}AMGraph;
int  LocateVex(AMGraph G,VerTexType u)
{
	int i;
	for(i = 0; i < G.vexnum; i++)
	{
		if( u == G.vexs [i])
			break;
	}
			return i;

}
Status CreateUDN(AMGraph &G)
{
	int i,j,k,w;
	char v1,v2;
	printf("请输入顶点数 总边数:");
	scanf("%d,%d",&G.vexnum,&G.arcnum);
	printf("请输入顶点信息:");
    for(i=0;i<G.vexnum;++i)
    {
		cout<<"第"<<i+1<<"个顶点:";
		cin>>G.vexs[i];
	}
	for(i = 0;i < G.vexnum ; i++)
		for(j = 0;j < G.vexnum ; j++)
			G.arcs [i][j] = MaxInt;
	printf("请输入一条边依附的顶点及其权值(例:a,b,1 a,c,2):");
	for(k = 0;k < G.arcnum ; k++)
	{
		cout<<"第"<<k+1<<"条边依附的顶点及权值:";
		cin>>v1>>v2>>w;
		i = LocateVex(G,v1);
		j = LocateVex(G,v2);
		G.arcs[i][j]=w;
        G.arcs[j][i]=G.arcs[i][j];
	}
	return OK;
}
void DFS_AM(AMGraph G,int v)
{
	int w;

	cout<<G.vexs[v];
	visited[v] =  true;
	for(w = 0; w < G.vexnum;w++ )
		if((G.arcs [v][w]!=0)&&(!visited[w]))
			DFS_AM(G,w);
}

int main()
{
	int v,i,j;
	AMGraph G;
	CreateUDN(G);
	cout << "创建的无向网如下" << endl;
	for(i = 0 ; i < G.vexnum ; ++i)
	{
		for(j = 0; j < G.vexnum; ++j)
		{
            if(G.arcs[i][j] != MaxInt)
            cout << G.arcs[i][j] << "\t";
            else
            cout << "∞" << "\t";
		}
		cout<<endl<<endl;
	}
	for(int i=0;i<G.vexnum;i++)
		visited[i]=false;
	cout<<"从哪个顶点开始DFS?"<<endl;
	cin>>v;
	DFS_AM(G,v);
	cout <<endl;
    return 0;
}

上一篇: 二叉树 - 红黑树

下一篇: 树 遍历