当前位置:首页 » 编程语言 » 怎么构造的无向图c语言
扩展阅读
webinf下怎么引入js 2023-08-31 21:54:13
堡垒机怎么打开web 2023-08-31 21:54:11

怎么构造的无向图c语言

发布时间: 2022-11-02 00:52:55

A. 怎么用c语言生成一个固定顶点数和固定边数的无向图

#defineInfinity1000#defineMaxVertexNum35#defineMAX40#include#include#include#include#includetypedefstructarcell//边的权值信息{intadj;//权值}arcell,adjmatrix[MaxVertexNum][MaxVertexNum];//图的邻接矩阵类型typedefstructvexsinfo//顶点信息{intposition;//景点的编号charname[32];//景点的名称charintroction[256];//景点的介绍}vexsinfo;typedefstructmgraph//图结构信息{vexsinfovexs[MaxVertexNum];//顶点向量(数组)adjmatrixarcs;//邻接矩阵intvexnum,arcnum;//分别指定顶点数和边数}mgraph;//全局变量intvisited[35];//用于标志是否已经访问过intd[35];//用于存放权值或存储路径顶点编号mgraphcampus;//图变量(大学校园)//(1)对图初始化mgraphinitgraph(){inti=0,j=0;mgraphc;c.vexnum=28;//顶点个数c.arcnum=39;//边的个数for(i=0;i",c.vexs[d[s]].name);//输出该路径。s=0时为起点mprintf("%s",c.vexs[d[s]].name);//输出最后一个景点名(即顶点n的名字,此时s==k)printf("\n\n");}else{s=0;while(sc.vexnum){printf("\n你所输入的景点编号不存在\n");printf("请重新输入:");scanf("%d",&v0);}//whilefor(v=0;v%s",c.vexs[w].name);}printf("---->%s",c.vexs[v].name);printf("\n总路线长为%d米\n\n",d[v]);}//for}//shortestpath//(6)-(11)修改图的信息。包括建图、更新信息、删除、增加结点和边//(6)构造图的邻接矩阵intcreatgragh(mgraph&c)//建图。以图的邻接矩阵存储图{inti,j,m,n;intv0,v1;intdistance;printf("请输入图的顶点数和边数:\n");scanf("%d%d",&c.vexnum,&c.arcnum);printf("下面请输入景点的信息:\n");for(i=0;i=0&&n>=0){c.arcs[m][n].adj=distance;c.arcs[n][m].adj=c.arcs[m][n].adj;}}return1;}//creatgragh//(7)更新图的部分信息。返回值:1intnewgraph(mgraph&c){intchangenum;//计数。用于记录要修改的对象的个数inti,m,n,t,distance,v0,v1;printf("\n下面请输入你要修改的景点的个数:\n");scanf("%d",&changenum);while(changenumc.vexnum){printf("\n输入错误!请重新输入");scanf("%d",&changenum);}for(i=0;ic.arcnum){printf("\n输入错误!请重新输入");scanf("%d",&changenum);}printf("\n下面请输入更新边的信息:\n");for(i=1;i=0&&n>=0){c.arcs[m][n].adj=distance;c.arcs[n][m].adj=c.arcs[m][n].adj;}}return1;}//newgraph

B. 数据结构中怎么编写创建一个无向图的程序

#include<stdio.h>
#include<stdlib.h>
#define infinity 100 //权最大值定为100,相当于正无穷
#define max 3 //最大顶点数3个

typedef struct ArcCell{
int weight; //权值
}ArcCell,AdjMatrix[max][max];
typedef struct{ //图
char vexs[max];
AdjMatrix arcx;
int vexnum,arcnum;
}MGrap;

void CreateUDN(MGrap &G);
int main(){
MGrap G;
CreateUDN(G);
return 0;
}
void CreateUDN(MGrap &G)
{
int i,j,k;
printf("Input the number of vex and arc:"); //分别输入顶点和弧的个数
scanf("%d %d",&G.vexnum,&G.arcnum);
for(i=0;i<G.vexnum;i++) //依次输入每个顶点
{
printf("请输入第%d个顶点",i+1);
scanf("%c",&G.vexs[i]);
}
for(i=0;i<G.vexnum;i++)
for(j=0;j<G.vexnum;j++)
G.arcx[i][j].weight = infinity;
for(i=0;i<G.arcnum;i++)
{
printf("请输入弧的两端点:(NO.%d)",i+1); //输入第i+1条弧的两端点,确定弧
scanf("%d %d ",&k,&j );
scanf("%d",&G.arcx[k][j].weight);
G.arcx[j][k]=G.arcx[k][j]; //无向图弧关于对角线对称
}

}

C. 数据结构无向图的建立

您好,这是我们数据结构一个作业程序,希望能帮到你。
#include <stdio.h>
#include<stdlib.h>
#define int_max 10000
#define inf 9999
#define max 20
//邻接矩阵定义
typedef struct ArcCell
{
int adj;
char *info;
}ArcCell,AdjMatrix[20][20];
typedef struct
{
char vexs[20];
AdjMatrix arcs;
int vexnum,arcnum;
}MGraph_L;

int LocateVex(MGraph_L G,char v)//查找顶点v的序号
{
int i=0;
while(G.vexs[i]!=v)
{
++i;
}
return i;
}

int createMGraph_L(MGraph_L &G)//创建图用邻接矩阵表示
{
char v1,v2;
int i,j,w;
printf("创建无向图\n");
printf("请输入无向图G的顶点数和弧数:");
scanf("%d%d",G.vexnum,G.arcnum);
for(i=0;i!=G.vexnum;++i)
{
printf("输入顶点%d\n",i);
scanf("%c",G.vexs[i]);
}
for(i=0;i!=G.vexnum;++i)
for(j=0;j!=G.vexnum;++j)
{
G.arcs[i][j].adj=int_max;
G.arcs[i][j].info=NULL;
}
printf("输入一条边依附的顶点和权:\n");
for(int k=0;k!=G.arcnum;++k)
{

scanf("%c%c%d",&v1,&v2,&w); //输入一条边依附的两点及权值
i=LocateVex(G,v1); //确定顶点V1和V2在图中的位置
j=LocateVex(G,v2);
G.arcs[i][j].adj=w;
G.arcs[j][i].adj=w;
}
return G.vexnum;
}

typedef struct ArcNode //弧结点
{
int adjvex; //该弧所指向的顶点的位置
struct ArcNode *nextarc; //指向下一条弧的指针
//char *info; //该弧相关信息的指针
}ArcNode;
typedef struct vnode //邻接链表顶点头接点
{
char data; //顶点信息
ArcNode *firstarc; //指向第一条依附该顶点的弧的指针
}vnode,adjlist;
typedef struct //图的定义
{
adjlist vertices[max];
int vexnum,arcnum; //图的当前顶点数和弧数
}ALGraph;

int CreateUDG(ALGraph &gra,MGraph_L G)//用邻接表存储图
{

int i=0,j=0;
ArcNode *arc,*tem,*p;
for(i=0;i!=G.vexnum;++i)
{
gra.vertices[i].data=G.vexs[i];
gra.vertices[i].firstarc=NULL;
}
for(i=0;i!=G.vexnum;++i)
{
for(j=0;j!=G.vexnum;++j)
{
if(gra.vertices[i].firstarc==NULL)
{
if(G.arcs[i][j].adj!=int_max&&j!=G.vexnum)
{
arc=(ArcNode *)malloc(sizeof(ArcNode));
arc->adjvex=j;
gra.vertices[i].firstarc=arc;
arc->nextarc=NULL;
p=arc;
++j;
while(G.arcs[i][j].adj!=int_max&&j!=G.vexnum)
{
tem=(ArcNode *)malloc(sizeof(ArcNode));
tem->adjvex=j;
gra.vertices[i].firstarc=tem;
tem->nextarc=arc;
arc=tem;
++j;
}
--j;
}
}
else
{
if(G.arcs[i][j].adj!=int_max&&j!=G.vexnum)
{
arc=(ArcNode *)malloc(sizeof(ArcNode));
arc->adjvex=j;
p->nextarc=arc;
arc->nextarc=NULL;
p=arc;
}

}

}
}
gra.vexnum=G.vexnum;
gra.arcnum=G.arcnum;
printf("图G的邻接表创建成功!\n");
return 1;
}

typedef struct
{
int adjvex;
int lowcost;
}closedge;

int prim(int g[][max],int n) //最小生成树PRIM算法
{
int lowcost[max],prevex[max]; //LOWCOST[]存储当前集合U分别到剩余结点的最短路径
//prevex[]存储最短路径在U中的结点
int i,j,k,min;
for(i=2;i<=n;i++) //n个顶点,n-1条边
{
lowcost[i]=g[1][i]; //初始化
prevex[i]=1; //顶点未加入到最小生成树中
}
lowcost[1]=0; //标志顶点1加入U集合
for(i=2;i<=n;i++) //形成n-1条边的生成树
{
min=inf;
k=0;
for(j=2;j<=n;j++) //寻找满足边的一个顶点在U,另一个顶点在V的最小边
if((lowcost[j]<min)&&(lowcost[j]!=0))
{
min=lowcost[j];
k=j;
}
printf("(%d,%d)%d\t",prevex[k]-1,k-1,min);
lowcost[k]=0; //顶点k加入U
for(j=2;j<=n;j++) //修改由顶点k到其他顶点边的权值
if(g[k][j]<lowcost[j])
{
lowcost[j]=g[k][j];
prevex[j]=k;
}
printf("\n");
}
return 0;
}

void list()
{
printf("……………………菜单……………………\n\n");
printf("0、创建无向图并用邻接表存储边信息…..\n");

printf("1、使用prim算法求最小生成树……………\n");
printf("2、退出系统…………………………………\n\n");
}

void main()
{
ALGraph G1;
MGraph_L G;
int i,d,g[20][20];
char y='y';
int k;
while(y=='y')
{
list();
printf("请选择菜单:\n");
scanf("%d",&k);
switch(k)
{
case 0:
d=createMGraph_L(G);
CreateUDG(G1,G);
break;

case 1:
for(i=0;i!=G.vexnum;++i)
for(int j=0;j!=G.vexnum;++j)
g[i+1][j+1]=G.arcs[i][j].adj;
printf("prim:\n");
prim(g,d);
break;
case 2:break;
//exit(1);
}
printf("\n是否继续操作?y/n:");
scanf("%c",&y);
}

}

D. 无向图的建立(邻接矩阵)与深度遍历程序(C语言)

(1) 图的建立,按采用邻接表作为存储结构,

(2) 从指定顶点出发进行深度优先搜索遍历。
(3) 从指定顶点出发进行广度优先搜索遍历。

#include"stdio.h"
#include"string.h"
#include"stdlib.h"
#include"math.h"

#define MAX_INT 1000
#define MAX_VERTEX_NUM 20
#define MAX_QUEUE_NUMBER 20

typedef struct ArcNode
{
int adjvex;
double adj;
struct ArcNode *nextarc;
}ArcNode;
typedef struct VexNode
{
char szName[40];
ArcNode *firstarc;
}VexNode,AdjList[MAX_VERTEX_NUM];
typedef struct
{
AdjList vexs;
int vexnum,arcnum;
}Net;
//定义队列
typedef struct{
int *elem;
int front, rear;
}Queue;
void InitQueue(Queue &Q)
{
Q.elem = new int[MAX_QUEUE_NUMBER];
Q.front = Q.rear = 0;
}
int EmptyQueue(Queue Q)
{
if(Q.front==Q.rear)
return 0;
else
return 1;
}
void DestroyQueue(Queue &Q){
delete []Q.elem;
Q.front = Q.rear = 0;
}

void EnterQueue(Queue &Q, int e)
{
if((Q.rear + 1)%MAX_QUEUE_NUMBER != Q.front)
Q.elem[Q.rear ] = e;
else
printf("队列满!\n");
Q.rear = (Q.rear + 1)%MAX_QUEUE_NUMBER;
}
void LeaveQueue(Queue &Q, int &e)
{
if(Q.rear != Q.front)
e = Q.elem[Q.front];
else
printf("队列空!\n");
Q.front = (Q.front+1)%MAX_QUEUE_NUMBER;
}
int LocateVex(Net ga,char *name)
{
int i;
for(i=0;i<ga.vexnum;i++)
if(strcmp(name,ga.vexs[i].szName)==0)
return i;
return -1;

}
void crt_net(Net &ga)
{
ArcNode *p;
char name1[40],name2[40];
int i,j,k;
double w;
printf("请输入顶点数和弧数:");
scanf("%d%d",&ga.vexnum,&ga.arcnum);
printf("请依次输入顶点名:\n");
for(i=0;i<ga.vexnum;i++)
{
scanf("%s",ga.vexs[i].szName);
ga.vexs[i].firstarc=NULL;
}
for(k=0;k<ga.arcnum;k++)
{
printf("请输入相邻的两个定点和权值:");
scanf("%s%s%lf",name1,name2,&w);
i=LocateVex(ga,name1);
j=LocateVex(ga,name2);
p=new ArcNode;
p->adjvex=j;
p->adj=w;
p->nextarc=ga.vexs[i].firstarc;
ga.vexs[i].firstarc=p;
}
}

void DFS(Net ga,char *name,int *visited)
{
int v,w;
ArcNode *p;
v=LocateVex(ga,name);
visited[v]=1;
printf("%s ",ga.vexs[v].szName);
p=ga.vexs[v].firstarc;
while(p!=NULL)
{
w=p->adjvex;
if(visited[w]==0)
DFS(ga,ga.vexs[w].szName,visited);
p=p->nextarc;
}

}
void DFSTravel(Net ga,char *name)
{
int v,k=0;
int visited[20];
for(v=0;v<ga.vexnum;v++)
visited[v]=0;
for(v=LocateVex(ga,name);k!=2;v=(v+1)%(ga.vexnum-1))
{
if(v+1==LocateVex(ga,name))
k++;
if(visited[v]==0)
DFS(ga,ga.vexs[v].szName,visited);

}
}

void BFSTravel(Net ga,char *name)
{
ArcNode *p;
int v,w,u,k=0;
Queue Q;
int visited[20];
for(v=0;v<ga.vexnum;v++)
visited[v]=0;
InitQueue(Q);
for(v=LocateVex(ga,name);k!=2;v=(v+1)%(ga.vexnum-1))
{
if(v+1==LocateVex(ga,name))
k++;
if(visited[v]==0)
{
visited[v]=1;
printf("%s ",ga.vexs[v].szName);
EnterQueue(Q,v);
while(EmptyQueue(Q)!=0)
{
LeaveQueue(Q,u);
p=ga.vexs[u].firstarc;
while(p!=NULL)
{
w=p->adjvex;
if(visited[w]==0)
{
printf("%s ",ga.vexs[w].szName);
visited[w]=1;
EnterQueue(Q,w);
}
p=p->nextarc;
}
}
}

}
}

void main()
{
char name[40];
Net ga;
crt_net(ga);
printf("请输入深度优先遍历开始点的名:");
scanf("%s",name);
printf("深度优先遍历:");
DFSTravel(ga,name);
printf("\n");
printf("请输入广度优先遍历开始点的名:");
scanf("%s",name);
printf("广度优先遍历:");
BFSTravel(ga,name);
printf("\n");

}

E. 在C语言中编程实现建立无向图的邻接表,输出某个点的邻接点~!

用矩阵表示无向图的,设有M个节点,则建立一个MXM矩阵,对每个顶点添加它的邻接点,即每行中对于有标记的列为该行顶点的邻接点。

F. C语言实现无向图

可以用邻接矩阵表示法:

#define max 100
typedef struct
{
int vex[max];//存储顶点值,类型可以变
int edge[max][max];//存储顶点之间的关系,以1或者0表示,1为有边,0为无
int e,v;//vertex存储顶点数,edge存储边的条数,所以无向图1的个数是边的个数的两倍,谢谢。
}m;

G. c语言邻接矩阵建造一个无向图并深度优先遍历 请问我写的程序为啥只能输出部分节点。。高手帮帮忙

你的DFS函数,就是深度优先的递归函数貌似没有递归好
struct MGraph
{
int vertex[maxvertex]; //存顶点
int arc[maxvertex][maxvertex]; //存边(邻接矩阵)
int vertexnum,arcnum; //顶点数和边数
};

其次是对图的初始化:

void CreatMGraph(MGraph *&G)
{
int i,j;
cin1>>G->vertexnum>>G->arcnum; //输入顶点数和边数

for(i=0;i<G->vertexnum;i++) //输入每个顶点的值
cin1>>G->vertex[i];

for(i=0;i<G->vertexnum;i++) //初始化邻接矩阵
for(j=0;j<G->vertexnum;j++)
G->arc[i][j]=0;

for(i=0;i<G->arcnum;i++)
{
int n,m,w;
cin1>>n>>m>>w; //修改邻接矩阵中的值
G->arc[n][m]=w;
G->arc[m][n]=w;
}
}

在此之前需要定义一个全局变量的visited数组:

int visited[maxvertex]; //标记已被访问过的顶点(全局变量)

//广度优先遍历

void BFS(MGraph *&G,int v)

{
queue<int> q;
int x,j;
if(!visited[v]) //即为visited[v]==0,也就是未被访问过
{
cout<<G->vertex[v]<<" ";
visited[v]=1;
q.push(v); //被访问的顶点入队
}

while(!q.empty()) //队不空进循环
{
x=q.front(); //取队头元素
q.pop(); //队头出队
for(j=0;j<G->vertexnum;j++)
if (G->arc[x][j]&&!visited[j])
{
cout<<G->vertex[j]<<" ";
visited[j]=1; //标记为访问过
q.push(j); //被访问的顶点继续入队
}
}
}

//深度优先遍历
void DFS(MGraph *&G,int v)

{
nt j;
if(!visited[v])

{
cout<<G->vertex[v]<<" ";
visited[v]=1; //标记为访问过
}

for(j=0;j<G->vertexnum;j++)
if (G->arc[v][j]&&!visited[j])//邻接矩阵的第(v,j)元素不为0
{ //且未被访问过则递归
DFS(G,j);
}
}

此为图的邻接矩阵的输出函数:

void Print(MGraph *G)
{
int i,j;
for(i=0;i<G->vertexnum;i++)
{
for(j=0;j<G->vertexnum;j++)
cout<<G->arc[i][j]<<" ";
cout<<endl;
}
}

main函数调用上面函数:

int main()
{
MGraph *G=new MGraph;
CreatMGraph(G);

cout<<"输出邻接矩阵:"<<endl;
Print(G);

cout<<"深度优先搜索:";
DFS(G,0);
cout<<endl;

memset(visited,0,sizeof(visited));//非常重要!!在下一个搜索之前一定要将标志位全部重新赋值为0

cout<<"广度优先搜索:";
BFS(G,0);
cout<<endl;

return 0;
}

H. 怎样用邻接矩阵为存储结构创建一个无向图

int CreateUDG(AdjMatrix *G){
int i,j,k,weight;
VertexData v1,v2;
printf("输入图的弧数和顶点数\n");
fflush(stdin);
scanf("%d,%d",&G->arcnum,&G->vexnum); /*输入图的顶点数和弧数*/
for(i=0;i<G->vexnum;i++) /*初始化邻接矩阵*/
for(j=0;j<G->vexnum;j++)
G->arcs[i][j].adj=INFINITY;
for(i=0;i<G->vexnum;i++)
{
printf("输入图的顶点\n");
fflush(stdin);
scanf("%c",&G->vexs[i]); /* 输入图的顶点*/
}
for(k=0;k<G->arcnum;k++)
{
printf("输入一条弧的两个顶点及权值\n");
fflush(stdin);
scanf("%c,%c,%d",&v1,&v2,&weight);/*输入一条弧的两个顶点及权值*/
i=LocateVertex(G,v1);
j=LocateVertex(G,v2);
G->arcs[i][j].adj=weight; /*建立弧*/
}
return(Ok);
}

void main()
{
AdjMatrix G;
CreateDN(&G);
}

I. C语言编写一个无向图程序,急用,能用的话高分回报

#include <stdlib.h>
#include <conio.h>
#include <time.h>

void Menu();
void Plus();
void Minus();
void Multiply();
void Dir();

int main()
{
int n, flag = 0;
while(1)
{
Menu();
do
{
flag = 0;
scanf("%d", &n);
switch(n)
{
case 1: Plus(); break;
case 2: Minus(); break;
case 3: Multiply(); break;
case 4: Dir(); break;
case 5: exit(0);
default:
{
printf("输入有误, 请重新输入!");
flag = 1;
}
}
}
while(flag);
}
return 0;
}

void Menu()
{
system("cls");
printf("\t\t欢迎来到小学生算数训练\n");
printf("\t\t\t1.加法训练\n");
printf("\t\t\t2.减法训练\n");
printf("\t\t\t3.乘法训练\n");
printf("\t\t\t4.除法训练\n");
printf("\t\t\t5.退出\n");
printf("\t\t\t请选择: ");
}

void Plus()
{
system("cls");
printf("\t\t现在是加法训练\n\n");
srand((unsigned)time(NULL));
int plu[10][4];
int m, n, result, input;
for(int i = 0; i < 10; i++)
{
m = rand() % 10;
n = rand() % 10;
printf("请计算: %d + %d = ", m, n);
result = m + n;
scanf("%d", &input);
if(input != result)
printf("真可惜, 回答错误, 请再接再厉!\n");
else
printf("恭喜你, 回答正确, 请继续加油!\n");
plu[i][0] = m;
plu[i][1] = n;
plu[i][2] = input;
plu[i][3] = result;
}
printf("===============十道题目回答如下=================\n\n");
for(int j = 0; j < 10; j++)
{
printf("%d + %d = %d\t", plu[j][0], plu[j][1], plu[j][2]);
if(plu[j][2] != plu[j][3])
printf("(正确答案为%d)", plu[j][3]);
printf("\n");
}
printf("输入任意键返回主菜单\n");
getch();
}

void Minus()
{
system("cls");
printf("\t\t现在是减法训练\n\n");
srand((unsigned)time(NULL));
int plu[10][4];
int m, n, result, input;
for(int i = 0; i < 10; i++)
{
do
{
m = rand() % 10;
n = rand() % 10;
}while(m < n);
printf("请计算: %d - %d = ", m, n);
result = m - n;
scanf("%d", &input);
if(input != result)
printf("真可惜, 回答错误, 请再接再厉!\n");
else
printf("恭喜你, 回答正确, 请继续加油!\n");
plu[i][0] = m;
plu[i][1] = n;
plu[i][2] = input;
plu[i][3] = result;
}
printf("===============十道题目回答如下=================\n\n");
for(int j = 0; j < 10; j++)
{
printf("%d - %d = %d\t", plu[j][0], plu[j][1], plu[j][2]);
if(plu[j][2] != plu[j][3])
printf("(正确答案为%d)", plu[j][3]);
printf("\n");
}
printf("输入任意键返回主菜单\n");
getch();
}

void Multiply()
{
system("cls");
printf("\t\t现在是乘法训练\n\n");
srand((unsigned)time(NULL));
int plu[10][4];
int m, n, result, input;
for(int i = 0; i < 10; i++)
{
m = rand() % 10;
n = rand() % 10;
printf("请计算: %d * %d = ", m, n);
result = m * n;
scanf("%d", &input);
if(input != result)
printf("真可惜, 回答错误, 请再接再厉!\n");
else
printf("恭喜你, 回答正确, 请继续加油!\n");
plu[i][0] = m;
plu[i][1] = n;
plu[i][2] = input;
plu[i][3] = result;
}
printf("===============十道题目回答如下=================\n\n");
for(int j = 0; j < 10; j++)
{
printf("%d * %d = %d\t", plu[j][0], plu[j][1], plu[j][2]);
if(plu[j][2] != plu[j][3])
printf("(正确答案为%d)", plu[j][3]);
printf("\n");
}
printf("输入任意键返回主菜单\n");
getch();
}

void Dir()
{
system("cls");
printf("\t\t现在是除法训练\n\n");
srand((unsigned)time(NULL));
int plu[10][4];
int m, n, result, input;
for(int i = 0; i < 10; i++)
{
do
{
m = rand() % 10;
n = rand() % 10;
}while(m == 0 || n == 0);
result = m * n;
int temp;
temp = m;
m = result;
result = temp;
printf("请计算: %d / %d = ", m, n);
scanf("%d", &input);
if(input != result)
printf("真可惜, 回答错误, 请再接再厉!\n");
else
printf("恭喜你, 回答正确, 请继续加油!\n");
plu[i][0] = m;
plu[i][1] = n;
plu[i][2] = input;
plu[i][3] = result;
}
printf("===============十道题目回答如下=================\n\n");
for(int j = 0; j < 10; j++)
{
printf("%d / %d = %d\t", plu[j][0], plu[j][1], plu[j][2]);
if(plu[j][2] != plu[j][3])
printf("(正确答案为%d)", plu[j][3]);
printf("\n");
}
printf("输入任意键返回主菜单\n");
getch();
}