首页 > 代码库 > 各种图的创建以及广度，深度优先遍历（临接矩阵存储）
各种图的创建以及广度，深度优先遍历（临接矩阵存储）
#include <stdio.h>
#include <iostream>
#include <limits.h>
#include <queue>
#define INFINTY INT_MAX //最大值
#define MaxVertexNum 100 //最大顶点数
using namespace std;
typedef enum{DG,UDG,DN,UDN} GraphKind; //图的种类（有向图。无向图，又向网，无向网）
typedef char VertexType; //顶点类型
typedef int AdjType; //边的关系类型（对于无权图，用1/0表示是否相邻；
// 对带权图，则为权值类型）
typedef char InfoType;
typedef struct {
AdjType adj;
InfoType* info; //该弧相关信息的指针
}ArcCell,AdjMatrix[MaxVertexNum][MaxVertexNum]; //定义弧和邻接矩阵
typedef struct {
VertexType vertex[MaxVertexNum]; //顶点向量
AdjMatrix arcs; //邻接矩阵
int vexnum,arcnum; //图的当前顶点数和弧数
GraphKind kind;
int visited[MaxVertexNum]; //标示每一个顶点是否被訪问过
}MGraph;
void CreateGraph(MGraph *G);
int LocateVex(MGraph *G,VertexType v);
void CreateDG(MGraph *G);
void CreateDN(MGraph *G);
void CreateUDG(MGraph *G);
void CreateUDN(MGraph *G);
void CommonInit(MGraph *G);
void display(MGraph *G);
void InsertDGArc(MGraph *G,VertexType v,VertexType w);
void InsertUDGArc(MGraph *G,VertexType v,VertexType w);
void DFSTraver(MGraph *G);
void BFSTraver(MGraph *G);
int main()
{
MGraph G;
CreateGraph(&G);
DFSTraver(&G);
BFSTraver(&G);
return 0;
}
//创建图
void CreateGraph(MGraph *G)
{
printf("please enter the kind of the graph(DG:0,UDG:1,DN:2,UDN:3):");
scanf("%d",(int *)&(G->kind));
switch(G->kind) {
case DG: CreateDG(G); break;
case UDG: CreateUDG(G); break;
case DN: CreateDN(G); break;
case UDN: CreateUDN(G); break;
}
}
//求顶点位置函数
int LocateVex(MGraph *G,VertexType v)
{
int i;
for(i=0;i<G->vexnum;i++)
{
if(G->vertex[i] == v)
return i;
}
return -1;
}
/*
a b
a c
b d
c d
d a
*/
void CommonInit(MGraph *G)
{
int infoflag;//假设为0，则不含其他信息。
//1.确定顶点数和弧数
printf("please enter vexnum , arcnum and is info(1 or 0):");
scanf("%d%d%d",&(G->vexnum),&(G->arcnum),&infoflag);
//2.确定各个顶点的值
printf("the value of each vertex:");
for(int i=0;i<G->vexnum;i++)
{
//getchar();
scanf(" %c",&(G->vertex[i]));
}
//3.初始化邻接矩阵
for (int i = 0; i < G->vexnum; ++i)
{
for(int j=0;j< G->vexnum;j++)
{
G->arcs[i][j].adj = 0;
G->arcs[i][j].info = NULL;
}
}
}
//插入又向边
void InsertDGArc(MGraph *G,VertexType v,VertexType w)
{
int i = LocateVex(G,v);
int j = LocateVex(G,w);
if(i>=0 && j>=0)
G->arcs[i][j].adj = 1;
}
//插入无向边
void InsertUDGArc(MGraph *G,VertexType v,VertexType w)
{
int i = LocateVex(G,v);
int j = LocateVex(G,w);
if(i>=0 && j>=0) {
G->arcs[j][i].adj = 1;
G->arcs[i][j].adj = 1;
}
}
//创建有向图
void CreateDG(MGraph *G)
{
CommonInit(G);
VertexType v1,v2;
//确定邻接矩阵
printf("please input %d heads and %d tails:\n",G->arcnum,G->arcnum);
for(int k=0; k<G->arcnum; k++)
{
scanf(" %c %c",&v1,&v2);
InsertDGArc(G,v1,v2);
}
display(G);
}
//创建无向图
void CreateUDG(MGraph *G)
{
CommonInit(G);
VertexType v1,v2;
//确定邻接矩阵
printf("please input %d heads and %d tails:\n",G->arcnum,G->arcnum);
for(int k=0; k<G->arcnum; k++)
{
scanf(" %c %c",&v1,&v2);
InsertUDGArc(G,v1,v2);
}
display(G);
}
//创建又向网
void CreateDN(MGraph *G)
{
VertexType v1,v2;
int weight;
CommonInit(G);
//初始化邻接矩阵
for (int i = 0; i < G->vexnum; ++i)
{
for(int j=0;j< G->vexnum;j++)
G->arcs[i][j].adj = INFINTY;
}
//确定邻接矩阵
printf("please input %d heads and %d tails and weights:\n",G->arcnum,G->arcnum);
for(int k=0; k<G->arcnum; k++)
{
scanf(" %c %c %d",&v1,&v2,&weight);
int i = LocateVex(G,v1);
int j = LocateVex(G,v2);
if(i>=0 && j>=0)
{
G->arcs[i][j].adj = weight;
}
}
display(G);
}
//创建无向网
void CreateUDN(MGraph *G)
{
VertexType v1,v2;
int weight;
CommonInit(G);
//初始化邻接矩阵
for (int i = 0; i < G->vexnum; ++i)
{
for(int j=0;j< G->vexnum;j++)
G->arcs[i][j].adj = INFINTY;
}
//确定邻接矩阵
printf("please input %d heads and %d tails and weights:\n",G->arcnum,G->arcnum);
for(int k=0; k<G->arcnum; k++)
{
scanf(" %c %c %d",&v1,&v2,&weight);
int i = LocateVex(G,v1);
int j = LocateVex(G,v2);
if(i>=0 && j>=0)
{
G->arcs[i][j].adj = weight;
G->arcs[j][i].adj = weight;
}
}
display(G);
}
void display(MGraph *G)
{
for(int i=0;i<G->vexnum;i++)
{
for(int j=0;j<G->vexnum;j++)
{
printf("%d ",G->arcs[i][j].adj);
}
printf("\n");
}
}
void Visit(MGraph *G,int v)
{
printf("%c ",G->vertex[v]);
}
void DFS(MGraph *G,int v)
{
Visit(G,v);
G->visited[v] = 1;
for(int i=0;i<G->vexnum;i++) {
if(!(G->visited[i]) && G->arcs[v][i].adj == 1){
//cout<<G->visited[i];
DFS(G,i);
}
}
}
//深度优先遍历
void DFSTraver(MGraph *G)
{
for (int i = 0; i < G->vexnum; i++)
{
G->visited[i] = 0;
}
printf("DFSTraver:\n");
for (int i = 0; i < G->vexnum; i++)
{
if(!G->visited[i])
DFS(G,i);
}
}
//返回节点v的第一个临接顶点
int FirstAdjVertex(MGraph *G,int v)
{
for (int i = 0; i < G->vexnum; i++)
{
if(G->arcs[v][i].adj==1 && i!=v)
return i;
}
return -1;//假设没有，返回-1
}
//返回v相对于w的下一个临接点
int NextAdjVex(MGraph *G,int v,int w)
{
for (int i = w+1; i < G->vexnum; i++)
{
if(G->arcs[v][i].adj==1 && i!=v)
return i;
}
return -1;
}
void BFS(MGraph *G,int v)
{
int w;
Visit(G,v);
G->visited[v] = 1;
queue<int> q;
q.push(v);
while(!q.empty())
{
w = q.front();
q.pop(); //队头元素出队
while(w!=-1)
{
if(!G->visited[w])
{
Visit(G,w);
G->visited[w] = 1;
q.push(w);
}
w = NextAdjVex(G,v,w);
}
}
}
//广度度优先遍历
void BFSTraver(MGraph *G)
{
printf("\nBFSTraver:\n");
for (int i = 0; i < G->vexnum; i++)
{
G->visited[i] = 0;
}
for (int i = 0; i < G->vexnum; i++)
{
if(!G->visited[i])
BFS(G,i);
}
}
各种图的创建以及广度，深度优先遍历（临接矩阵存储）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。