c语言，请问大神怎么把这个改成有向图？建立一个邻接矩阵形式的图
void MGout(MGraph *mg){ //输出邻接矩阵
int i,j,k;
k=mg-n;
for(i=0;ik;i++){
for(j=0;jk;j++){
if(mg-edges[i][j]==1)
printf(“%-5d”,digit);
else
printf(“%-5d”,zero);
}
printf(“\n”);
}
}
用C语言实现 图的邻接表和邻接矩阵数据结构的定义、创建；图的深度优先遍历、广度优先遍历。
/*
程序1：邻接表的dfs,bfs
其中n是点的个数,m是边的个数,你需要输入m条有向边，如果要无向只需要反过来多加一遍即可。
*/
#include stdio.h
#include string.h
#define MAXM 100000
#define MAXN 10000
int next[MAXM],first[MAXN],en[MAXM],n,m,flag[MAXN],pd,dl[MAXN],head,tail;
void input_data()
{
scanf(“%d%d”,n,m);
int i,x,y;
for (i=1;i=m;i++)
{
int x,y;
scanf(“%d%d”,x,y);
next[i]=first[x];
first[x]=i;
en[i]=y;
}
}
void pre()
{
memset(flag,0,sizeof(flag));
pd=0;
}
void dfs(int x)
{
flag[x]=1;
if (!pd)
{
pd=1;
printf(“%d”,x);
}else
printf(” %d”,x);
int p=first[x];
while (p!=0)
{
int y=en[p];
if (!flag[y]) dfs(y);
p=next[p];
}
}
void bfs(int k)
{
head=0;tail=1;
flag[k]=1;dl[1]=k;
while (headtail)
{
int x=dl[++head];
if (!pd)
{
pd=1;
printf(“%d”,x);
}else printf(” %d”,x);
int p=first[x];
while (p!=0)
{
int y=en[p];
if (!flag[y])
{
flag[y]=1;
dl[++tail]=y;
}
p=next[p];
}
}
}
int main()
{
input_data();//读入图信息。
pre();//初始化
printf(“图的深度优先遍历结果:”);
int i;
for (i=1;i=n;i++)//对整张图进行dfs; 加这个for主要是为了防止不多个子图的情况
if (!flag[i])
dfs(i);
printf(“\n————————————————————-\n”);
pre();//初始化
printf(“图的广度优先遍历结果为:”);
for (i=1;i=n;i++)
if (!flag[i])
bfs(i);
printf(“\n———————-end————————————\n”);
return 0;
}
/*
程序2:邻接矩阵
图的广度优先遍历和深度优先遍历
*/
#include stdio.h
#include string.h
#define MAXN 1000
int n,m,w[MAXN][MAXN],flag[MAXN],pd,dl[MAXN];
void input_data()
{
scanf(“%d%d”,n,m);
int i;
for (i=1;i=m;i++)
{
int x,y;
scanf(“%d%d”,x,y);
w[x][0]++;
w[x][w[x][0]]=y;
}
}
void pre()
{
memset(flag,0,sizeof(flag));
pd=0;
}
void dfs(int x)
{
flag[x]=1;
if (!pd)
{
pd=1;
printf(“%d”,x);
}else printf(” %d”,x);
int i;
for (i=1;i=w[x][0];i++)
{
int y=w[x][i];
if (!flag[y]) dfs(y);
}
}
void bfs(int t)
{
int head=0,tail=1;
dl[1]=t;flag[t]=1;
while (headtail)
{
int x=dl[++head];
if (!pd)
{
pd=1;
printf(“%d”,x);
}else printf(” %d”,x);
int i;
for (i=1;i=w[x][0];i++)
{
int y=w[x][i];
if (!flag[y])
{
flag[y]=1;
dl[++tail]=y;
}
}
}
}
int main()
{
input_data();
printf(“图的深度优先遍历结果:”);
pre();
int i;
for (i=1;i=n;i++)
if (!flag[i])
dfs(i);
printf(“\n—————————————————————\n”);
printf(“图的广度优先遍历结果:”);
pre();
for (i=1;i=n;i++)
if (!flag[i])
bfs(i);
printf(“\n—————————–end——————————–\n”);
return 0;
}
用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);
queueint 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语言
#include cstdio
#include cstring
#include stack
using namespace std;
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
// Description: 表示图的结点的邻接边
struct Edge
{
int dest;
Edge *next;
} **graph;
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
// Description: 添加一个边
// Input: e – 要添加边的结点, p – 目的地
// Output: e – 添加边后的结点
void AddEdge(Edge *e, int p)
{
if(!e)
{
e = new Edge;
e-dest = p;
e-next = 0;
}
else
{
Edge *tail = e;
while (tail-next) tail = tail-next;
tail-next = new Edge;
tail = tail-next;
tail-dest = p;
tail-next = 0;
}
}
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
// Description: 输入结点之间的边
// Input: Console下用户输入,起点和终点; m – 边的个数
// Output: graph – 图;
void Input(int m)
{
int i, a, b;// a-b存在边(有向)
for (i = 0; i m; i++)
{
scanf(“%d %d”, a, b);
AddEdge(graph[a], b);
}
}
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
// Description: 获得每个结点的入度
// Input: n – 结点的个数
// Output: degree – 每个结点的入度
void GetDegree(int *degree, int n)
{
int i = 0;
Edge *edge;
memset(degree, 0, sizeof(int) * n);
for (i = 0; i n; i++)
{
edge = graph[i];
while(edge)
{
degree[edge-dest]++;
edge = edge-next;
}
}
}
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
// Description: 拓扑排序
// Input: n – 结点个数
// Output: console下输出一个正确的拓扑序
void TopoSort(int n)
{
int *degree = new int[n];// 初始化所有结点的入度
GetDegree(degree, n);
stackint s;// 获得入度为0的结点,并入栈
int i = 0;
for (i = 0; i n; i++)
if (degree[i] == 0)
s.push(i);
int index = 0;// 结点的下标
Edge *edge; // 当前结点邻接表
while (!s.empty())
{
index = s.top();
printf(“%d”, index);
s.pop();
edge = graph[index];
while (edge)
{
if (–degree[edge-dest] == 0)
s.push(edge-dest);
edge = edge-next;
}
}
delete []degree;
}
int main()
{
int n, m;// 结点个数、边个数
scanf(“%d %d”, n, m);
int i;
graph = new Edge*[n];
for(i = 0; i n; i++) graph[i] = 0;
Input(m);
TopoSort(n);
return 0;
}
微信扫一扫 
支付宝扫一扫 
