图的定义
图是一种比树更加复杂的非线性数据结构,和树不同的是,每个结点没有严格的层级之分,更加没有前驱和后驱结点严格区分,在很多领域有广泛的用途。
图是由V集合和E集合组成的二元组,记做G=(V,E),其中V是图的顶点集合,V是图边的集合,V和E从逻辑关系上并没有一一对应的说法,可能存在多个顶点对应一条边,反之也成立。
(1) 有向图:图中每条边都带有方向,有向边也叫孤,方向相反,同一条边,则为二条弧。
(2) 无向图:图中每条边都不带方向,在无向图没有弧的概念。
1-1.png
(3) 完全图:如果一个无向图有n顶点,每个顶点和其他n-1个顶点都有边,称为无向完全图;显然n个顶点的无向完全图的边共有n(n-1)/2,类似的在n个顶点的有向完全图中有n(n-1)条弧,及每个顶点都有方向相反的两条弧。
(4) 图的度:该顶点边的数目,比如在1-1图中,无向图4顶点的度为3,在有向图中有出度和入度的概念,入度是终点指向该顶点,出度是起点指向该顶点,比如在1-1中,有向图顶点1的度为2 ,入度1,出度1。
(5) 路径:从1个顶点到某个顶点存在一个顶点序列,使得唯一二元组属于G,则为路径;在有向图中,路径也是有方向的,路径的长度为图的弧或者边的个数;第一个顶点和最后一个顶点相同路径成为环(回路)。
(6) 连通图:在无向图中,如果一个顶点到另外一个顶点有路径,我们就说是顶点之间是连通的,如果图中的任意两个顶点是连通,则为连通图,如1-1的无向图就是连通的。
(7)强连通图:在有向图中,如果一个顶点到另外一个顶点都有路径,则这个有向图是强连通图。 如1-1中的有向图就不是强连通图,1到3有路径 3到1没有,2到4没有。
图的存储
图的存储有链接矩阵和邻接表的两种基本存储结构。
1) 邻接矩阵法:利用一个矩阵表示graph中顶点之间的关系,对于n给顶点的graph,用n阶矩阵,表示满足
image.png
所以图1-1 有向图和无向图的邻接矩阵是(有向图同理):
A[4][4] 有向图= [
0 1 1 1
0 0 0 0
0 0 0 0
1 1 0 0
]
A[5][5] 无向图= [
0 1 1 1 0
1 0 1 0 0
1 1 0 1 1
1 0 1 0 1
0 0 1 1 0
]
可以看出无线图的邻接矩阵是对称的。
类似的网(边或者弧赋权值)临界矩阵:
1-2 网图邻接矩阵定义.png
1-3网图.png
网1-3的邻接矩阵为:
A[6][6] = [
∞ 5 ∞ 7 ∞ ∞
∞ ∞ 4 ∞ ∞ ∞
8 ∞ ∞ ∞ ∞ 9
∞ ∞ 5 ∞ ∞ 6
∞ ∞ ∞ 5 ∞ ∞
3 ∞ ∞ ∞ 1 ∞
]
创建无向网存储结构,并输出邻接矩阵:
#include <stdio.h>
#include<stdlib.h>
#define MaxN 100
// 代表无穷 65535
#define INFINITY 65535
// 顶点的int
// 图的邻接矩阵
typedef int GraphMatrix[MaxN][MaxN];
// 网的邻接矩阵
typedef int Reticular[MaxN][MaxN];
typedef struct{
// 顶点的数目,边/弧的数目
int Vnum,Enum;
Reticular arc;
//顶点列表
char vexs[MaxN];
}Graph;
int locates(Graph *g,char ch){
int i = 0;
for(i = 0; i < g->Vnum; i++)
{
if(g->vexs[i] == ch)
{
break;
}
}
if(i >= g->Vnum)
{
return -1;
}
return i;
}
// 邻接矩阵 无线图的创建
void creatMGraph(Graph *g){
int i,j,k,w;
printf("输入顶点数和边数\n");
scanf("%d,%d",&(g->Vnum),&(g->Enum));
printf("%d %d\n", g->Vnum, g->Enum);
for(int i=0;i < g->Vnum;i++){
// 赋值字符串
g->vexs[i] = getchar();
//printf("执行1\n");
while(g->vexs[i] == '\n'){
g->vexs[i] = getchar();
//printf("执行1.2\n");
}
}
//printf("执行2\n");
// 邻接矩阵的初始化
for(int i = 0; i < g->Vnum;i++){
for(int j = 0; j < g->Vnum;j++){
g->arc[i][j] = INFINITY;
//printf("执行3\n");
}
}
// printf("执行4\n");
for(int k = 0; k< g->Enum;k++){
char p,q;
printf("输入边上(vi,vj)的i,j 和网的权值:\n");
p = getchar();
while(p == '\n'){
p = getchar();
}
q = getchar();
while(q == '\n'){
q = getchar();
}
scanf("%d",&w);
int m = -1;
int n = -1;
// 找到顶点的位置
m = locates(g,p);
n = locates(g,q);
if(n == -1 || m == -1){
// 停止循环
printf("没找到该顶点的位置\n");
return;
}
g->arc[m][n] = w ;
g->arc[n][m] = g->arc[m][n];
}
}
//打印图 顶点
void printGraph(Graph g)
{
int i, j;
for(i = 0; i < g.Vnum; i++)
{
for(j = 0; j < g.Vnum; j++)
{
printf("%d ", g.arc[i][j]);
}
printf("\n");
}
}
int main(int argc, char *argv[]){
Graph p;
creatMGraph(&p);
printGraph(p);
//n个顶点和e条边的无向网图的创建，时间复杂度为O(n + n2 + e)
return 0;
}
运行结果:
image.png
2) 邻接表法
这种方式是为图的每个顶点建立一个单链表,链接表中的结点有表结点和表头结点两种类型。
image.png
image.png
对于n个节点,e条边的无向图,需要n个头结点和2e个表结点。
对于顶点较少,使用邻接表发会造成存储空间的浪费。
创建邻接表,并输出图的邻接表结构:(无向网和有向网)
#include <stdio.h>
#include <stdlib.h>
#define MAXVEX 1000
typedef int EdgeType;
typedef char VertextType;
// 表结点
typedef struct EdgeNode{
// 顶点编号
int adjvex;
// 权值 网
EdgeType weigth;
struct EdgeNode *next;
}EdgeNode;
// 表头结点 存储在一个数组里面
typedef struct VertexNode{
// 存储顶点信息
VertextType data;
EdgeNode *fristedge;
}VertexNode,AdjList[MAXVEX];
//定义邻接表
typedef struct{
AdjList adjList;
int numVertexes,numEdges;
}GraphList;
int Locate(GraphList *g ,VertextType ch){
int i;
for ( i = 0 ; i < g->numVertexes; i++) {
if (ch == g->adjList[i].data) {
break;
}
}
if (i > g->numVertexes) {
printf("不是这个图的顶点");
return -1;
}
return i;
}
void creatGraphList(GraphList *g){
//int i,j,k;
EdgeNode *e;
EdgeNode *f;
printf("输入顶点和边数\n");
scanf("%d,%d",&g->numVertexes,&g->numEdges);
for (int i = 0; i < g->numVertexes; i++) {
printf("请输入顶点:%d\n",i);
g->adjList[i].data = getchar();
g->adjList[i].fristedge = NULL;
while (g->adjList[i].data == '\n') {
g->adjList[i].data = getchar();
}
}
for(int k = 0;k < g->numEdges;k++){
printf("输入边(vi,vj)上的顶点序号 权值:\n");
VertextType p,q;
EdgeType w;
p = getchar();
while (p == '\n') {
p = getchar();
}
q = getchar();
while (q == '\n') {
q = getchar();
}
int m,n;
m = Locate(g,p);
n = Locate(g,q);
scanf("%d",&w);
if (m == -1 || n == -1) {
return;
}
printf("p = %c\n", p);
printf("q = %c\n", q);
printf("m = %d\n", m);
printf("n = %d\n", n);
// 申请顶点内存空间
e = (EdgeNode *)malloc(sizeof(EdgeNode));
if (e == NULL) {
printf("申请空间异常");
return;
}
// 顶点序号
e->adjvex = n;
e->weigth = w;
// 将e指针指向当前顶点指向的结构
e->next = g->adjList[m].fristedge;
// 当前指针指向e
g->adjList[m].fristedge = e;
f = (EdgeNode *)malloc(sizeof(EdgeNode));
if (f == NULL) {
printf("申请空间异常");
return;
}
f->adjvex = m;
f->weigth = w;
f->next = g->adjList[n].fristedge;
g->adjList[n].fristedge = f;
}
}
void printfGraph(GraphList *g){
int i = 0;
while (g->adjList[i].fristedge != NULL && i < MAXVEX) {
printf("顶点:%c\n",g->adjList[i].data);
EdgeNode *e = NULL;
e = g->adjList[i].fristedge;
while (e != NULL) {
printf("—> <%c, %c> %d",g->adjList[i].data,g->adjList[e->adjvex].data,e->weigth);
e = e->next;
}
i++;
printf("\n");
}
}
int main(int argc, char *argv[]){
GraphList g ;
creatGraphList(&g);
printfGraph(&g);
// 时间复杂图 为0(n+e)
return 0;
}
输出结果:
image.png
网友评论