【文件属性】：
文件名称：c_数据结构_图的相关操作
文件大小：6KB
文件格式：CPP
更新时间：2018-01-29 04:14:49
数据结构
数据结构中图的相关操作 C语言
#include <stdio h>
#include <malloc h>
#include <string h>
#define MAXVEX 100
typedef char VertexType[3]; 定义VertexType为char数组类型
typedef struct vertex
{
int adjvex; 顶点编号
VertexType data; 顶点的信息
} VType; 顶点类型
typedef struct graph
{
int n e; n为实际顶点数 e为实际边数
VType vexs[MAXVEX]; 顶点集合
int edges[MAXVEX][MAXVEX]; 边的集合
} AdjMatix; 图的邻接矩阵类型
typedef struct edgenode
{
int adjvex; 邻接点序号
int value; 边的权值
struct edgenode next; 下一条边的顶点
} ArcNode; 每个顶点建立的单链表中结点的类型
typedef struct vexnode
{
VertexType data; 结点信息
ArcNode firstarc; 指向第一条边结点
} VHeadNode; 单链表的头结点类型
typedef struct
{
int n e; n为实际顶点数 e为实际边数
VHeadNode adjlist[MAXVEX]; 单链表头结点数组
} AdjList; 图的邻接表类型
int visited[MAXVEX];
void DispAdjList AdjList G
{
int i;
int in[G >n] out[G >n];
for i 0;i<G >n;i++
{in[i] 0 out[i] 0;
}
ArcNode p;
printf "图的邻接表表示如下: n" ;
for i 0;i<G >n;i++
{
printf " 结点 [%d %3s] >" i G >adjlist[i] data ;
p G >adjlist[i] firstarc;
while p NULL
{ out[i]++; 对于结点的出度加1
in[p >adjvex] ++; 邻接表中的结点的序号所在的结点的入度 加1
printf " %d >" p >adjvex ;
p p >next;
}
printf "∧ n" ;
} for i 0;i<G >n;i++
{ printf " 结点 [%d %3s]的度 ：%d n" i G >adjlist[i] data in[i]+out[i] ;
}
}
void MatToList AdjMatix g AdjList &G 算法:将邻接矩阵g转换成邻接表G
{
int i j;
ArcNode p;
G AdjList malloc sizeof AdjList ;
for i 0;i<g n;i++ 给邻接表中所有头结点的指针域置初值
{
G >adjlist[i] firstarc NULL;
strcpy G >adjlist[i] data g vexs[i] data ;
}
for i 0;i<g n;i++ 检查邻接矩阵中每个元素
for j g n 1;j> 0;j
if g edges[i][j] 0 邻接矩阵的当前元素不为0
{
p ArcNode malloc sizeof ArcNode ; 创建一个结点 p
p >value g edges[i][j];p >adjvex j;
p >next G >adjlist[i] firstarc; 将 p链到链表后
G >adjlist[i] firstarc p;
}
G >n g n;G >e g e;
}
void DFS AdjList g int vi 对邻接表G从顶点vi开始进行深度优先遍历
{
ArcNode p;
printf "下标%d结点%3s >" vi g >adjlist[vi] data ; 访问vi顶点
visited[vi] 1; 置已访问标识
p g >adjlist[vi] firstarc; 找vi的第一个邻接点
while p NULL 找vi的所有邻接点
{
if visited[p >adjvex] 0
DFS g p >adjvex ; 从vi未访问过的邻接点出发深度优先搜索
p p >next; 找vi的下一个邻接点
}
}
void DFS1 AdjList G int vi 非递归深度优先遍历算法
{
ArcNode p;
ArcNode St[MAXVEX];
int top 1 v;
printf "%d > " vi ; 访问vi顶点
visited[vi] 1; 置已访问标识
top++; 将初始顶点vi的firstarc指针进栈
St[top] G >adjlist[vi] firstarc;
while top> 1 栈不空循环
{
p St[top];top ; 出栈一个顶点为当前顶点
while p NULL 循环搜索其相邻顶点
{
v p >adjvex; 取相邻顶点的编号
if visited[v] 0 若该顶点未访问过
{
printf "%d > " v ; 访问v顶点
visited[v] 1; 置访问标识
top++; 将该顶点的第1个相邻顶点进栈
St[top] G >adjlist[v] firstarc;
break; 退出当前顶点的搜索
}
p p >next; 找下一个相邻顶点
}
}
}
void BFS AdjList G int vi 对邻接表g从顶点vi开始进行广宽优先遍历
{
int i v;
int Qu[MAXVEX] front 0 rear 0; 循环队列
ArcNode p;
printf "%d > " vi ; 访问初始顶点
visited[vi] 1; 置已访问标识
rear rear 1 %MAXVEX; 循环移动队尾指针
Qu[rear] vi; 初始顶点进队
while front rear 队列不为空时循环
{
front front+1 % MAXVEX;
v Qu[front]; 顶点v出队
p G >adjlist[v] firstarc; 找v的第一个邻接点
while p NULL 找v的所有邻接点
{
if visited[p >adjvex] 0 未访问过则访问之
{
visited[p >adjvex] 1; 置已访问标识
printf "%d > " p >adjvex ; 访问该点并使之入队列
rear rear+1 % MAXVEX; 循环移动队尾指针
Qu[rear] p >adjvex; 顶点p >adjvex进队
}
p p >next; 找v的下一个邻接点
}
}
}
int main
{
int i j;
AdjMatix g;
AdjList G;
int a[5][5] {{0 1 0 1 0} {1 0 1 0 0} {0 1 0 1 1} {1 0 1 0 1} {0 0 1 1 0}};
char vname[MAXVEX] {"a" "b" "c" "d" "e"};
g n 5;g e 6; 连通图
int a[5][5] {{0 1 0 1 0} {1 0 1 0 0} {0 1 0 1 0} {1 0 1 0 0} {0 0 0 0 0}};
char vname[MAXVEX] {"a" "b" "c" "d" "e"};
g n 5;g e 4; 非连通图
int a[4][4] {{0 1 1 1} {1 0 1 1} {1 1 0 1} {1 1 1 0}};
char vname[MAXVEX] {"a" "b" "c" "d"};
g n 5;g e 12;
int a[5][5] {{0 1 1 1 0} {1 0 1 1 1} {1 1 0 1 0} {1 1 1 0 1} {0 1 0 1 0}};
char vname[MAXVEX] {"a" "b" "c" "d" "e"};
g n 5;g e 16; 建立图的无向图 每1条无向边算为2条有向边
int a[6][6] { p151 图7 22的代价矩阵改成的邻接矩阵
{0 1 1 0 1 0}
{0 0 1 0 1 0}
{1 0 0 1 0 0}
{0 1 0 0 1 0}
{0 0 0 1 0 0}
{0 0 0 1 0 0}};
char vname[MAXVEX] {"v0" "v1" "v2" "v3" "v4" "v5"};
g n 6;g e 11;
for i 0;i<g n;i++
strcpy g vexs[i] data vname[i] ;
for i 0;i<g n;i++
for j 0;j<g n;j++
g edges[i][j] a[i][j];
MatToList g G ; 生成邻接表
DispAdjList G ; 输出邻接表
for i 0;i<g n;i++ visited[i] 0; 顶点标识置初值
printf "从顶点0的深度优先遍历序列: n" ;
printf " 递归算法:" ;DFS G 0 ;printf " n" ;
for i 0;i<g n;i++ visited[i] 0; 顶点标识置初值
printf " 非递归算法:" ;
DFS1 G 0 ;
printf " n" ;
printf "从顶点0的广度优先遍历序列: n" ;
for i 0;i<g n;i++ visited[i] 0; 顶点标识置初值
printf " t" ;BFS G 0 ;
printf " n" ;
scanf "%d" ;
return 0;
}">数据结构中图的相关操作 C语言
#include <stdio h>
#include <malloc h>
#include <string h>
#define MAXVEX 100
typedef char VertexType[3]; 定义VertexType为char数组类型
typedef struct vertex
{
int adjvex; 顶点编号
VertexType data; 顶 [更多]