当前位置：首页 » 编程语言 » 图的领接表c语言程序
扩展阅读
提分平台的账号密码是什么 2023-08-31 22:07:10
webinf下怎么引入js 2023-08-31 21:54:13
堡垒机怎么打开web 2023-08-31 21:54:11

图的领接表c语言程序

发布时间: 2023-06-19 17:51:15

‘壹’ 用c语言编程 1创建图的邻接矩阵和邻接表 2验证图的深度优先、广度优先遍历算法 3验证最短路径

这些是c++的代码不知是否满足你的要求。
1、邻接表表示的图中分别用DFS和BFS遍历
#include <cstdio>
#include <cstring>
#include <queue>
using namespace std;
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
// Description: 图的邻接表的结点
struct Edge
{
int dest; // 目标结点下标
// int value; // 路径长度
Edge *link; // 下一个结点
};
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
// Description: 为图添加一条边
// Input: edge - 欲加边的结点; dest - 目的结点
// Output: edge - 加边后的结点
// Tags:
void AddEdge(Edge *&edge, int dest)
{
// 简单的链表操作
if (!edge)
{
edge = new Edge;
edge->dest = dest;
edge->link = 0;
}
else
{
Edge *tail = edge;
while (tail->link) tail = tail->link;
tail->link = new Edge;
tail = tail->link;
tail->dest = dest;
tail->link = 0;
}
}
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
// Description: Console下输入图的边
// Input: Graph - 图; n - 图的结点的个数; EdgeNumber - 添加边的个数;
// Output: Graph - 添加边后的图
// Tags: 用户输入点对(a, b), 表示添加a->b的路径
void Input(Edge **&graph, int n, int EdgeNumber)
{
int i = 0, a, b;
for (i = 0; i < EdgeNumber; i++)
{
scanf("%d %d", &a, &b); // 用户输入起点终点
AddEdge(graph[a], b); // 添加a->b的边
}
}
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
// Description: 深度优先搜索并输出
// Input: Graph - 图; n - 图的结点的个数; StartEdge — 开始的结点;
// Output: Console下输出遍历的顺序
// Tags: 递归调用 _dfs过程、回溯算法
void _dfs(Edge **&graph, bool *visited, int n, int index);
void DFS(Edge **&graph, int n, int StartEdge)
{
bool *visited = new bool[n]; // 标记每个结点是否已访问
memset(visited, (int)false, sizeof(bool) * n);
visited[StartEdge] = true;
printf("start edge: %d\n", StartEdge);
_dfs(graph, visited, n, StartEdge);
visited[StartEdge] = false;
}
// _dfs过程：
// Input: Graph - 图; n - 图的结点的个数; index - 当前的下标, visited - 记录结点是否已访问
// Output: Console下输出遍历的顺序
void _dfs(Edge **&graph, bool *visited, int n, int index)
{
int nIndex; // 下一个结点下标
Edge *edge = graph[index]; // 遍历用结点
while (edge) // 遍历所有的邻接结点
{
nIndex = edge->dest;
if (!visited[nIndex])
{
visited[nIndex] = true;
printf("%d\t", nIndex);
_dfs(graph, visited, n, nIndex);
}
edge = edge->link;
}
}

///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
// Description: 广度优先搜索并输出
// Input: Graph - 图; n - 图的结点的个数; StartEdge - 开始的结点
// Output: Console下输出遍历的顺序
// Tags: 需要一个队列记录所有的灰色结点
void BFS(Edge **&graph, int n, int StartEdge)
{
bool *visited = new bool[n]; // 记录结点是否已访问
memset(visited, (int)false, sizeof(bool) * n);
queue<int> Q; // 记录准备访问的结点
Edge *edge; // 记录当前遍历的结点
int nIndex; // 记录下标

visited[StartEdge] = true;
printf("start edge:%d\n", StartEdge);
Q.push(StartEdge);
while (!Q.empty())
{
edge = graph[Q.front()];
while (edge)
{
nIndex = edge->dest;
if (!visited[nIndex])
{
visited[nIndex] = true;
printf("%d\t", nIndex);
Q.push(nIndex);
}
edge = edge->link;
}
Q.pop();
}
}
int main()
{
const int NODE_NUMBER = 7; // 10结点
const int EDGE_NUMBER = 11; // 10边
Edge **graph = new Edge *[NODE_NUMBER]; // 图
memset(graph, 0, sizeof(Edge *) * NODE_NUMBER); // 一开始没边
Input(graph, NODE_NUMBER, EDGE_NUMBER); // 输入边
printf("DFS:\n");
DFS(graph, NODE_NUMBER, 0); // 深度优先
printf("\n");
printf("BFS:\n");
BFS(graph, NODE_NUMBER, 0); // 广度优先
printf("\n");
return 0;
}

2、邻接矩阵表示的图中利用bellman-ford算法获得单点最短路
#include <cstdio>
#include <cstring>
using namespace std;
#define INTEGER_INF 0xffff // 表示无穷大路径
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
// Description: 邻接矩阵表示的图
struct Graph
{
int **value; // 权值
int number; // 结点个数
};
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
// Description: 初始化图
// Input: number - 结点个数
// Output: graph - 图
void InitGraph(Graph &graph, int number)
{
int i, j;
graph.value = new int *[number];
for (i = 0; i < number; i++)
graph.value[i] = new int[number];
for (i = 0; i < number; i++)
{
for (j = 0; j < number; j++)
{
if (i == j)
graph.value[i][j] = 0;
else
graph.value[i][j] = INTEGER_INF;
}
}
graph.number = number;
}
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
// Description: 析构图
// Input: graph - 图
// Output: graph - 析构后的图的壳子
void FreeGraph(Graph &graph)
{
int i;
for (i = 0; i < graph.number; i++)
delete []graph.value[i];
delete []graph.value;
graph.number = 0;
}
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
// Description: 用户在Console下输入图的边
// Input: n - 边的数量
// Output: graph - 加边后的图
void AddEdge(Graph &graph, int n)
{
int i, a, b, v;
for (i = 0; i < n; i++)
{
scanf("%d%d%d", &a, &b, &v);
graph.value[a][b] = v;
}
}
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
// Description: BellmanFord 算法计算单源最短路
// Input: graph - 图, index - 起点
// Output: true - 存在最短路 且 Console 下输出起点到各个顶点的最短路
// false - 不存在最短路(存在边权和为负的环路)
bool BellmanFord(Graph &graph, int index)
{
int num = graph.number; // 结点个数
int *v = new int[num]; // 记录最短路
int i, j, t;
// 设定初值
for (t = 1; t < num; t++)
v[t] = INTEGER_INF;
v[index] = 0;
// 松弛
for (t = 0; t < num - 1; t++) // 循环i-1次
for (i = 0; i < num; i++)
for(j = 0; j < num; j++)
if (i != j && graph.value[i][j] != INTEGER_INF) // 如果两顶点间有路
if (v[j] > v[i] + graph.value[i][j]) // 松弛
v[j] = v[i] + graph.value[i][j];
// 判断是否存在边权和为负的环路
for (i = 0; i < num; i++)
for (j = 0; j < num; j++)
if (graph.value[i][j] != INTEGER_INF &&
v[j] > v[i] + graph.value[i][j])
return false;
// 输出
for (t = 1; t < num; t++)
printf("%d\t", v[t]);
return true;
}
int main()
{
Graph graph;
InitGraph(graph, 5);
AddEdge(graph, 10);
if (!BellmanFord(graph, 0))
printf("该图中存在边权和为负的环路!\n");
FreeGraph(graph);
return 0;
}

‘贰’ 怎么用c语言画邻接表

1、先把要讲解的巧码图在下面展示一下，先看一下；

邻接表是图的常用储存结构之一。邻接表由表头结点和表结点两部分组成，其中图中每个顶点均对应一个存储在数组中的表头结点。

‘叁’ 数据结构-图的邻接表表示（C语言）

//grap_theory.cpp:定义控制台应用程序的入口点。

//


//#include"stdafx.h"//VS2010头文件

#include<stdio.h>

#defineNTOTAL(26*4)//最大路径数目

#defineMAX_DISTANCE10000.0

structpiont{

intline_adjacency_list;

intnum_piont;

inttest_num[2];

charfrom[NTOTAL];

charto[NTOTAL];

charall_piont[NTOTAL];

intall_piont_num[NTOTAL];

floatdistance[NTOTAL];

floatdistance_all[NTOTAL][NTOTAL];

};//结构体定义

voidread(piont*test){

inti;

chartemp[100];

scanf("%d",&test->line_adjacency_list);//读取行数

gets(temp);//读取回车字符

for(i=0;i<test->line_adjacency_list;i++){//读取列表

scanf("%c%c%f",&test->from[i],&test->to[i],&test->distance[i]);

gets(temp);//读取回车字符

}

scanf("%c%c",&test->from[i],&test->to[i]);//读取短短路径名称

}

voidcal_num_piont(piont*test){

inti,j;

intfrom_num,to_num;

test->num_piont=0;

for(i=0;i<NTOTAL;i++){

test->all_piont_num[i]=0;//点的度数清零

test->distance_all[i][i]=0.0;

for(j=i+1;j<NTOTAL;j++){

test->distance_all[i][j]=MAX_DISTANCE;

test->distance_all[j][i]=MAX_DISTANCE;

}

}

for(i=0;i<test->line_adjacency_list;i++){

//判断from

for(j=0;j<test->num_piont;j++){

if(test->from[i]==test->all_piont[j]){

from_num=j;

test->all_piont_num[j]++;

break;

}

}

if(j==test->num_piont){

test->all_piont[j]=test->from[i];

from_num=j;

test->all_piont_num[j]++;

test->num_piont++;

}

//判断end

for(j=0;j<test->num_piont;j++){

if(test->to[i]==test->all_piont[j]){

to_num=j;

test->all_piont_num[j]++;

break;

}

}

if(j==test->num_piont){

test->all_piont[j]=test->to[i];

to_num=j;

test->all_piont_num[j]++;

test->num_piont++;


}

test->distance_all[from_num][to_num]=test->distance[i];

test->distance_all[to_num][from_num]=test->distance[i];

}

//判断所求点的位置

for(i=0;i<test->num_piont;i++){

if(test->from[test->line_adjacency_list]==test->all_piont[i])

test->test_num[0]=i;

if(test->to[test->line_adjacency_list]==test->all_piont[i])

test->test_num[1]=i;

}

}

floatmin_distance(piont*test){

inti,j,k,n;

floatmin_dis;

floatdis_i_k_add_k_j;

n=test->num_piont;

//Floyd-Warshall算法

for(k=0;k<n;k++){

for(i=0;i<n;i++){

for(j=0;j<n;j++){

dis_i_k_add_k_j=(test->distance_all[i][k]+test->distance_all[k][j]);

if(test->distance_all[i][j]>dis_i_k_add_k_j)

test->distance_all[i][j]=dis_i_k_add_k_j;

}

}

}

min_dis=test->distance_all[test->test_num[0]][test->test_num[1]];

returnmin_dis;

}

voidtest_printf(piont*test,floatmin_dis){

inti;

printf("%d ",test->num_piont);

for(i=0;i<test->num_piont;i++){

printf("%d ",test->all_piont_num[i]);

}

printf("%-8.0f ",min_dis);

}

voidmain()

{

floatmin_dis;

pionttest1;//结构体声明

read(&test1);

cal_num_piont(&test1);

min_dis=min_distance(&test1);

test_printf(&test1,min_dis);


}



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

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

‘伍’ 用C语言实现 图的邻接表和邻接矩阵数据结构的定义、创建；图的深度优先遍历、广度优先遍历。

/*
程序1：邻接表的dfs,bfs
其中n是点的个数,m是边的个数,你需要输入m条有向边，如果要无向只需要反过来多加一遍即可。
*/
#include<stdio.h>
#include<string.h>
#defineMAXM100000
#defineMAXN10000
intnext[MAXM],first[MAXN],en[MAXM],n,m,flag[MAXN],pd,dl[MAXN],head,tail;

voidinput_data()
{
scanf("%d%d",&n,&m);
inti,x,y;
for(i=1;i<=m;i++)
{
intx,y;
scanf("%d%d",&x,&y);
next[i]=first[x];
first[x]=i;
en[i]=y;
}
}

voidpre()
{
memset(flag,0,sizeof(flag));
pd=0;
}

voiddfs(intx)
{
flag[x]=1;
if(!pd)
{
pd=1;
printf("%d",x);
}else
printf("%d",x);
intp=first[x];
while(p!=0)
{
inty=en[p];
if(!flag[y])dfs(y);
p=next[p];
}
}

voidbfs(intk)
{
head=0;tail=1;
flag[k]=1;dl[1]=k;
while(head<tail)
{
intx=dl[++head];
if(!pd)
{
pd=1;
printf("%d",x);
}elseprintf("%d",x);
intp=first[x];
while(p!=0)
{
inty=en[p];
if(!flag[y])
{
flag[y]=1;
dl[++tail]=y;
}
p=next[p];
}
}
}

intmain()
{
input_data();//读入图信息。
pre();//初始化
printf("图的深度优先遍历结果:");
inti;
for(i=1;i<=n;i++)//对整张图进行dfs;加这个for主要是为了防止不多个子图的情况
if(!flag[i])
dfs(i);
printf("
-------------------------------------------------------------
");
pre();//初始化
printf("图的广度优先遍历结果为:");
for(i=1;i<=n;i++)
if(!flag[i])
bfs(i);
printf("
----------------------end------------------------------------
");
return0;
}
/*
程序2:邻接矩阵
图的广度优先遍历和深度优先遍历
*/
#include<stdio.h>
#include<string.h>
#defineMAXN1000

intn,m,w[MAXN][MAXN],flag[MAXN],pd,dl[MAXN];

voidinput_data()
{
scanf("%d%d",&n,&m);
inti;
for(i=1;i<=m;i++)
{
intx,y;
scanf("%d%d",&x,&y);
w[x][0]++;
w[x][w[x][0]]=y;
}
}

voidpre()
{
memset(flag,0,sizeof(flag));
pd=0;
}

voiddfs(intx)
{
flag[x]=1;
if(!pd)
{
pd=1;
printf("%d",x);
}elseprintf("%d",x);
inti;
for(i=1;i<=w[x][0];i++)
{
inty=w[x][i];
if(!flag[y])dfs(y);
}
}

voidbfs(intt)
{
inthead=0,tail=1;
dl[1]=t;flag[t]=1;
while(head<tail)
{
intx=dl[++head];
if(!pd)
{
pd=1;
printf("%d",x);
}elseprintf("%d",x);
inti;
for(i=1;i<=w[x][0];i++)
{
inty=w[x][i];
if(!flag[y])
{
flag[y]=1;
dl[++tail]=y;
}
}
}
}

intmain()
{
input_data();
printf("图的深度优先遍历结果:");
pre();
inti;
for(i=1;i<=n;i++)
if(!flag[i])
dfs(i);
printf("
---------------------------------------------------------------
");
printf("图的广度优先遍历结果:");
pre();
for(i=1;i<=n;i++)
if(!flag[i])
bfs(i);
printf("
-----------------------------end--------------------------------
");
return0;
}

阅读全文

与图的领接表c语言程序相关的内容

本站内容整理源于互联网，如有问题请联系解决。
Copyright design: www.gotrillian.com since 2022