一、图的表示：
图分为有向图和无向图，表示方式有邻接表，邻接矩阵，十字链表三种表示方式。
1.1 邻接矩阵
图1.1 图1.1对应的邻接矩阵
无向图的邻接矩阵是对称矩阵。
代码实现：
#include <stdio.h> #include <stdlib.h> /*#include <curses.h>*/ typedef char VertexType; //顶点类型应由用户定义 typedef int EdgeType; //边上的权值类型应由用户定义 #define MAXVEX 100 //最大顶点数，应由用户定义 #define INFINITY 65535 //用65535来代表无穷大 #define DEBUG typedef struct { VertexType vexs[MAXVEX]; //顶点表 EdgeType arc[MAXVEX][MAXVEX]; //邻接矩阵，可看作边 int numVertexes, numEdges; //图中当前的顶点数和边数 }Graph; //定位 int locates(Graph *g, char ch) { int i = 0; for(i = 0; i < g->numVertexes; i++) { if(g->vexs[i] == ch) { break; } } if(i >= g->numVertexes) { return -1; } return i; } //建立一个无向网图的邻接矩阵表示 void CreateGraph(Graph *g) { int i, j, k, w; printf("输入顶点数和边数: "); scanf("%d,%d", &(g->numVertexes), &(g->numEdges)); #ifdef DEBUG printf("%d %d ", g->numVertexes, g->numEdges); #endif for(i = 0; i < g->numVertexes; i++) { g->vexs[i] = getchar(); while(g->vexs[i] == ' ') { g->vexs[i] = getchar(); } } #ifdef DEBUG for(i = 0; i < g->numVertexes; i++) { printf("%c ", g->vexs[i]); } printf(" "); #endif for(i = 0; i < g->numEdges; i++) { for(j = 0; j < g->numEdges; j++) { g->arc[i][j] = INFINITY; //邻接矩阵初始化 } } for(k = 0; k < g->numEdges; k++) { char p, q; printf("输入边(vi,vj)上的下标i，下标j和权值: "); p = getchar(); while(p == ' ') { p = getchar(); } q = getchar(); while(q == ' ') { q = getchar(); } scanf("%d", &w); int m = -1; int n = -1; m = locates(g, p); n = locates(g, q); if(n == -1 || m == -1) { fprintf(stderr, "there is no this vertex. "); return; } //getchar(); 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.numVertexes; i++) { for(j = 0; j < g.numVertexes; j++) { printf("%d ", g.arc[i][j]); } printf(" "); } } int main(int argc, char **argv) { Graph g; //邻接矩阵创建图 CreateGraph(&g); printGraph(g); return 0; }
1.2 邻接表
代码实现：
/* 邻接表表示的图结构 */
#include <stdio.h>
#include<stdlib.h>
#define DEBUG
#define MAXVEX 1000 //最大顶点数
typedef char VertexType; //顶点类型应由用户定义
typedef int EdgeType; //边上的权值类型应由用户定义
typedef struct EdgeNode //边表结点
{
int adjvex; //邻接点域，存储该顶点对应的下标
EdgeType weigth; //用于存储权值，对于非网图可以不需要
struct EdgeNode *next; //链域，指向下一个邻接点
}EdgeNode;
typedef struct VertexNode //顶点表结构
{
VertexType data; //顶点域，存储顶点信息
EdgeNode *firstedge; //边表头指针
}VertexNode, AdjList[MAXVEX];
typedef struct
{
AdjList adjList;
int numVertexes, numEdges; //图中当前顶点数和边数
}GraphList;
int Locate(GraphList *g, char ch)
{
int i;
for(i = 0; i < MAXVEX; i++)
{
if(ch == g->adjList[i].data)
{
break;
}
}
if(i >= MAXVEX)
{
fprintf(stderr,"there is no vertex.
");
return -1;
}
return i;
}
//建立图的邻接表结构
void CreateGraph(GraphList *g)
{
int i, j, k;
EdgeNode *e;
EdgeNode *f;
printf("输入顶点数和边数:
");
scanf("%d,%d", &g->numVertexes, &g->numEdges);
#ifdef DEBUG
printf("%d,%d
", g->numVertexes, g->numEdges);
#endif
for(i = 0; i < g->numVertexes; i++)
{
printf("请输入顶点%d:
", i);
g->adjList[i].data = getchar(); //输入顶点信息
g->adjList[i].firstedge = NULL; //将边表置为空表
while(g->adjList[i].data == '
')
{
g->adjList[i].data = getchar();
}
}
//建立边表
for(k = 0; k < g->numEdges; k++)
{
printf("输入边(vi,vj)上的顶点序号:
");
char p, q;
p = getchar();
while(p == '
')
{
p = getchar();
}
q = getchar();
while(q == '
')
{
q = getchar();
}
int m, n;
m = Locate(g, p);
n = Locate(g, q);
if(m == -1 || n == -1)
{
return;
}
#ifdef DEBUG
printf("p = %c
", p);
printf("q = %c
", q);
printf("m = %d
", m);
printf("n = %d
", n);
#endif
//向内存申请空间，生成边表结点
e = (EdgeNode *)malloc(sizeof(EdgeNode));
if(e == NULL)
{
fprintf(stderr, "malloc() error.
");
return;
}
//邻接序号为j
e->adjvex = n;
//将e指针指向当前顶点指向的结构
e->next = g->adjList[m].firstedge;
//将当前顶点的指针指向e
g->adjList[m].firstedge = e;
f = (EdgeNode *)malloc(sizeof(EdgeNode));
if(f == NULL)
{
fprintf(stderr, "malloc() error.
");
return;
}
f->adjvex = m;
f->next = g->adjList[n].firstedge;
g->adjList[n].firstedge = f;
}
}
void printGraph(GraphList *g)
{
int i = 0;
#ifdef DEBUG
printf("printGraph() start.
");
#endif
while(g->adjList[i].firstedge != NULL && i < MAXVEX)
{
printf("顶点:%c ", g->adjList[i].data);
EdgeNode *e = NULL;
e = g->adjList[i].firstedge;
while(e != NULL)
{
printf("%d ", e->adjvex);
e = e->next;
}
i++;
printf("
");
}
}
int main(int argc, char **argv)
{
GraphList g;
CreateGraph(&g);
printGraph(&g);
return 0;
}
二 图的遍历
2.1深度优先搜索遍历DFS：
2.2广度优先搜索遍历BFS：
参考：