‘壹’ c语言 图 邻接矩阵 深度优先遍历 DFS搜索
DFS(g,j);
DFSL(ga,p->adjvex);
除了上面两句话，其他没什么问题，首先如果图不连通，当你用从某一点遍历的方法，本身就没办法遍历整个图
‘贰’ 用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语言)
#include<stdio.h>
int min(int a,int b)
{
return a>b?b:a;
}
int fun(int **a,int n,int begin,int end)
{
int m=~(1<<31),i;
if(begin==end)
return 0;
else
{
for(i=0;i<n;i++)
if(a[begin][i]!=-1&&a[begin][i]!=0)
m=min(fun(a,n,i,end),m);
return m;
}
}
int main()
{
int n,i,js=0;
char begin,end;
int a[26][26],b[26]={0};
scanf("%d",&n);
for(i=0;i<n;i++)
for(j=0;j<n;j++)
{
scanf("%d,&a[i][j]");
if(i>j&&a[i][j]!=-1)
b[i]++;
}
getchar();
scanf("%c %c",&begin,&end);
for(i=0;i<n;i++)
s=s+b[i];
printf("%d\n",s);
for(i=0;i<n;i++)
printf("%d\n",b[i]);
fun(a,n,begin-'A',end-'A');
return 0;
}
‘肆’ C语言 邻接矩阵和邻接表
/**********************邻接矩阵*****************/
#include<bits/stdc++.h>//邻接矩阵
using namespace std;
const int N=300;
int Map[N][N]={0};//邻接矩阵
int book[N]={0};//结点标记数组(1表示该点访问过了;0未访问过)
int n,m;
void dfs(int x)//深度遍历
{
for(int i=1;i<=n;i++)
{//book[i]==0:i未被访问过
// Map[x][i]==1：x到i有边连接
if(book[i]==0&&Map[x][i]==1)
{
book[i]=1;//访问标记
printf("->[%d]",i);
dfs(i);//前往下一个结点i
}
}
}
void bfs(int x)
{
int q[N]={0};
int fornt=0;
int rear=0;
q[rear++]=x;//源点入队
while(fornt<rear)
{
int k=q[fornt++];//出队
for(int i=1;i<=n;i++)
{//扩展一个点周围可以访问的点
if(book[i]==0&&Map[k][i]==1)
{
printf("->[%d]",i);
book[i]=1;//访问标记
q[rear++]=i;//入队
}
}
}
}
int main()
{
scanf("%d%d",&n,&m);//n个结点，m条边
for(int i=0;i<m;i++)
{//构造无向图
int x,y;//输入2个结点;x->y;y->x;
scanf("%d%d",&x,&y);
Map[x][y]=1;//1代表x，y邻接
Map[y][x]=1;
}
book[1]=1;//标记结点1
printf("深度遍历路径 [%d]",1);
dfs(1);//从结点1深度遍历 (起始点可以随便选,1~n)
printf(" ");
memset(book,0,sizeof(book));//标记数组置0，用于广度遍历标记
printf("广度遍历路径 [%d]",1);
book[1]=1;//标记结点1
bfs(1);//从结点1广度遍历 (起始点可以随便选,1~n)
return 0;
}
/*5个结点,7条边
5 7
1 3
1 2
1 4
2 4
2 5
3 5
4 5
*/
/*************************邻接表*************************************/
#include<bits/stdc++.h>//万能头文件，C/C++都能用,包含了所有的头文件
using namespace std;//邻接表
const int N=300;
typedef struct st{
int v;//表头能到达的结点
struct st *next;//指向下一个结点的指针域
}*link,AK;//定义结点类型
struct sx{
AK *next;//表头指针域
}s[N];//n个结点,n个表头
int book[N]={0};//结点标记数组(1表示该点访问过了;0未访问过)
int n,m;
void create(int x,int y)
{//前插法构建邻接表
link p;
p=new AK;//开辟新结点
p->v=y;
p->next=s[x].next;
s[x].next=p;
}
void fun()
{//表头指针赋空(这一步至关重要,没有这一步无法建表)
for(int i=1;i<=n;i++)
s[i].next=NULL;
}
void dfs(int x)//深度遍历邻接表
{
link p=s[x].next;
while(p)
{
if(book[p->v]==0)
{
printf("->[%d]",p->v);
book[p->v]=1;
dfs(p->v);
}
p=p->next;
}
}
void bfs(int x)//广度遍历邻接表
{
int q[N]={0};//队列
int fornt=0;
int rear=0;
q[rear++]=x;
while(fornt<rear)
{
int k=q[fornt++];
link p=s[k].next;
while(p)
{
if(book[p->v]==0)
{
printf("->[%d]",p->v);
book[p->v]=1;
q[rear++]=p->v;
}
p=p->next;
}
}
}
void input()//打印邻接表
{//首列是表头(其后尾随的是与其邻接的结点)
//n个表头
link p;
for(int i=1;i<=n;i++)
{
p=s[i].next;
printf("[%d]",i);
while(p)
{
printf("->[%d]",p->v);
p=p->next;
}
cout<<endl;
}
}
int main()
{
fun();//调用表头置空
scanf("%d%d",&n,&m);//n个结点，m条边
for(int i=0;i<m;i++)
{//构造无向邻接表
int x,y;//输入2个结点;x->y;y->x;
scanf("%d%d",&x,&y);
create(x,y);//构建有向邻接表，只调用一个;
create(y,x);//构建无向邻接表，只调用两个;
}
book[1]=1;//标记结点1
printf("深度遍历路径 [%d]",1);
dfs(1);//从结点1深度遍历 (起始点可以随便选,1~n)
printf(" ");
memset(book,0,sizeof(book));//标记数组置0，用于广度遍历标记
printf("广度遍历路径 [%d]",1);
book[1]=1;//标记结点1
bfs(1);//从结点1广度遍历 (起始点可以随便选,1~n)
printf(" ");
printf("打印邻接表结构 ");
input();//打印邻接表
return 0;
}
/*5个结点,7条边
5 7
1 3
1 2
1 4
2 4
2 5
3 5
4 5
*/
‘伍’ 数据结构c语言版 邻接矩阵
#include<stdio.h>
#include<stdlib.h>
typedefintVertexType;
typedefintEdgetype;
#defineMaxVertexNum30
typedefstructGraph{
VertexTypevertexs[MaxVertexNum];
Edgetypearcs[MaxVertexNum][MaxVertexNum];
intvextexNum,edgeNum;
}MGraph;
voidCreatGraph(MGraph*G)
{
inti,j,k;
scanf("%d,%d",&(G->vextexNum),&(G->edgeNum));//vertexNum是顶点数edgeNum是边数
for(i=0;i<G->vextexNum;i++)//输入顶点信息，建立顶点表
scanf("%c",&(G->vertexs[i]));
for(i=0;i<G->vextexNum;i++)
{
for(j=0;j<G->vextexNum;j++)
G->arcs[i][j]=0;
}
for(k=0;k<G->edgeNum;k++)
{
scanf("%d,%d",&i,&j);
G->arcs[i][j]=1;//若加入G->arcs[j][i]=1;则为无向图
}
}
voidPrintGraph(MGraph*G)
{
inti,j;
for(i=0;i<G->vextexNum;i++)
{
printf("%c",G->vertexs[i]);
}
for(i=0;i<G->vextexNum;i++)
{
for(j=0;j<G->vextexNum;j++)
printf("%d",G->arcs[i][j]);
printf(" ");
}
}
voidmain()
{
MGraph*G;
G=(MGraph*)malloc(sizeof(MGraph));
CreatGraph(G);
PrintGraph(G);
}
‘陆’ c语言运用邻接矩阵求最短路径中的最长路径问题
同问、
‘柒’ 计算机C语言题目，已知赋权无向图，画邻接矩阵和邻接表。还有最小支撑树
所要求赋权无向图的邻接矩阵和邻接表，还有最小支撑树见下图：
‘捌’ 怎么用C语言将邻接矩阵转化为可达矩阵 （急）
第一步，二重循环：邻接矩阵+单位矩阵
for i=0 to shangxian (i++)
for j=0 to shangxian (j++)
if i=j then a[i,j]=a[i,j]+1(单位矩阵对角线上的值为1)
nextj,i
第二步，所得矩阵和自身相乘（二重循环）。矩阵乘法需要些好多字，就不写了，相信你知道，至少也应该能查到。
第三步，相乘后得到的矩阵和为相乘前的矩阵比较，（也是二重循环）。如相等则完事，否则重复执行第二、三步。
如果自动执行二、三的相乘和比较过程，则需要在外面加一层条件循环。
‘玖’ 谁给我解释一下 C语言中图邻接矩阵0 和1 是咋弄的 我没看懂
1表示想通，0表示不相通。
这里是让你理解。无向图有对称性。有向图则没有。
以后你做题题目会直接给你矩阵不是给你图让你生成。
后面你会学到>1的 ，那种要求最短路的就是有权值的了。