图（Graph）是一种较线性表和树更复杂的数据结构。在图形结构中，结点之间的关系可以是任一的，图中任意两个数据元素之间都可能相关。
图的存储结构
邻接矩阵
邻接矩阵是表示顶点之间相邻关系的矩阵。设G=(V,E)是一个图，其中V={v1,v2,…,vn} 。G的邻接矩阵是一个具有下列性质的n阶方阵：
- 对无向图而言，邻接矩阵一定是对称的，而且主对角线一定为零（在此仅讨论无向简单图），副对角线不一定为0，有向图则不一定如此。
- 在无向图中，任一顶点i的度为第i列（或第i行）所有非零元素的个数，在有向图中顶点i的出度为第i行所有非零元素的个数，而入度为第i列所有非零元素的个数。
- 用邻接矩阵法表示图共需要n^2个空间，由于无向图的邻接矩阵一定具有对称关系，所以扣除对角线为零外，仅需要存储上三角形或下三角形的数据即可，因此仅需要n（n-1）/2个空间。
#define INFINITYC 0
#define MAX_VERTEX_NUM 50
typedef int Status;
typedef char VertexType;
typedef int EdgeType;
typedef struct MGraph {
VertexType vexs[MAX_VERTEX_NUM];
EdgeType arc[MAX_VERTEX_NUM][MAX_VERTEX_NUM];
int numNodes, numEdges;
} MGraph;
void CreateMGraph(MGraph *G) {
printf("输入顶点数和边数:\n");
scanf("%d,%d", &G->numNodes, &G->numEdges);
printf("顶点数:%d,边数:%d\n", G->numNodes, G->numEdges);
int i, j, w;
for (i = 0; i < G->numNodes; i++) {
scanf("%c", &G->vexs[i]);
getchar();
}
for (i = 0; i < G->numNodes; i++) {
for (j = 0; j < G->numNodes; i++) {
G->arc[i][j] = INFINITYC;
}
}
for (int k = 0; k < G->numEdges; k++) {
printf("输入边(vi, vj)上的下标i, 下标j, 权w\n");
scanf("%d,%d,%d", &i, &j, &w);
G->arc[i][j] = w;
G->arc[j][i] = G->arc[i][j];
}
for (int i = 0; i < G->numNodes; i++) {
printf("\n");
for (int j = 0; j < G->numNodes; j++) {
printf("%d ",G->arc[i][j]);
}
}
printf("\n");
}
邻接表
邻接表（Adjacency List）是图的一种链式存储结构。在连接表中，对图中的每个顶点建立一个单链表，第i个单链表中的结点表示依附于顶点v1的边。每个结点由3个域组成，其中邻接点域（adjvex）指示与顶点v1邻接的点在图中的位置，链域（nextarc）指示下一条边或弧的结点。数据域存储和边或弧相关的信息。每个链表附设一个表头结点。
#define MAX_VERTEX_NUM 50
#define true 1
#define false 0
typedef char Element;
typedef int BOOL;
typedef struct ArcNode {
int adjvex;
Element data;
struct ArcNode *nextArc;
} ArcNode;
typedef struct VNode {
Element data;
ArcNode * firstedge;
} VertexNode, Adjlist[MAX_VERTEX_NUM];
typedef struct ALGraph {
Adjlist adjlist;
int arc_num;
int node_num;
BOOL is_directed;
} ALGraph, *GraphLink;
void CreateGraph(GraphLink *G) {
printf("输入顶点数目, 边数和方向？：\n");
scanf("%d %d %d", &(*G)->node_num, &(*G)->arc_num, &(*G)->is_directed);
printf("输入顶点信息：\n");
int i, j;
for (i = 0; i < (*G)->node_num; i++) {
getchar();
scanf("%c", &(*G)->adjlist[i].data);
(*G)->adjlist[i].firstedge = NULL;
}
ArcNode *p;
printf("输入边信息：\n");
for (int k = 0; k < (*G)->arc_num; k++) {
getchar();
scanf("%d %d", &i, &j);
p = (ArcNode *)malloc(sizeof(ArcNode));
p->adjvex = j;
p->nextArc = (*G)->adjlist[i].firstedge;
(*G)->adjlist[i].firstedge = p;
if (!(*G)->is_directed) {
p = (ArcNode *)malloc(sizeof(ArcNode));
p->adjvex = i;
p->nextArc = (*G)->adjlist[j].firstedge;
(*G)->adjlist[j].firstedge = p;
}
}
}
void putGraph(GraphLink G){
printf("邻接表中存储信息:\n");
for (int i = 0; i < G->node_num; i++) {
ArcNode *p = G->adjlist[i].firstedge;
while (p) {
printf("%c->%c ", G->adjlist[i].data, G->adjlist[p->adjvex].data);
p = p->nextArc;
}
printf("\n");
}
}
int main(int argc, const char * argv[]) {
// insert code here...
printf("Hello, World!\n");
GraphLink g = (ALGraph *)malloc(sizeof(ALGraph));
CreateGraph(&g);
putGraph(g);
return 0;
}
图的遍历
和树的遍历类似，从图中某一个顶点出发访遍图中其余顶点，且使每一个顶点紧被访问一次，这一过程叫图的遍历。
深度优先搜索
邻接矩阵深度优先搜索
/*
邻接矩阵深度优先搜索
*/
Boolean visited[MAX_VERTEX_NUM];
void DFS(MGraph G, int v) {
visited[v] = TRUE;
printf("%c ", G.vexs[v]);
for (int i = 0; i < G.numNodes; i++) {
if (!visited[i] && G.arc[v][i] == 1) {
DFS(G, i);
}
}
}
void DFSTraverse(MGraph G) {
for (int i = 0; i < G.numNodes; i++) {
visited[i] = FALSE;
}
for (int i = 0; i < G.numNodes; i++) {
if (!visited[i]) {
DFS(G, i);
}
}
printf("\n");
}
邻接表深度优先搜索
/*
邻接表深度优先搜索
*/
BOOL visited[MAX_VERTEX_NUM];
void DFS(ALGraph G, int v) {
visited[v] = true;
printf("%c", G.adjlist[v].data);
ArcNode *p;
p = G.adjlist[v].firstedge;
while (p) {
if (!visited[p->adjvex]) {
DFS(G, p->adjvex);
}
p = p->nextArc;
}
}
void DFSTraverse(ALGraph G) {
for (int i = 0; i < G.node_num; i++) {
visited[i] = false;
}
for (int i = 0; i < G.node_num; i++) {
if (!visited[i]) {
DFS(G, i);
}
}
printf("\n");
}
分析上述算法，在遍历图时，对图中每个顶点至多调用一次DFS函数，因为一旦某个顶点被标志成已被访问，就不再从它出发进行搜索。因此，遍历图的过程实质上是对每个顶点查找其邻接点的过程。其耗费的时间则取决于所采用的存储结构。
- 当用二维数组表示邻接矩阵图的存储结构时，查找每个顶点的邻接点所需要的时间为O(n^2),其中n为图中顶点数。
- 当用邻接表作图的存储结构时，找邻接点所需要的时间为O(e)，其中e为无向图中边的数或有向图中弧的数，因此，当以邻接表作为存储结构时，深度优化搜索遍历图的时间浮渣度为O(n + e)。
广度优先搜索
邻接矩阵的广度优先搜索
/*
邻接矩阵广度优先搜索
*/
void BFSTraverse(MGraph G) {
for (int i = 0; i < G.numNodes; i++) {
visited[i] = FALSE;
}
SqQueue Q;
InitQueue(&Q);
for (int i = 0; i < G.numNodes; i++) {
if (!visited[i]) {
visited[i] = TRUE;
printf("%c ", G.vexs[i]);
EnQueue(&Q, i);
while (!QueueEmpty(Q)) {
DeQueue(&Q, &i);
for (int j = 0; j < G.numNodes; j++) {
if (G.arc[i][j] == 1 && !visited[j]) {
visited[j] = TRUE;
printf("%c ", G.vexs[j]);
EnQueue(&Q, j);
}
}
}
}
}
}
邻接表的广度优先搜索
/*
邻接表广度优先搜索
*/
void BFSTraverse(ALGraph G) {
for (int i = 0; i < G.node_num; i++) {
visited[i] = FALSE;
}
SqQueue Q;
InitQueue(&Q);
ArcNode *p;
for (int i = 0; i < G.node_num; i++) {
if (!visited[i]) {
visited[i] = TRUE;
printf("%c ", G.adjlist[i].data);
EnQueue(&Q, i);
while (!QueueEmpty(Q)) {
DeQueue(&Q, &i);
p = G.adjlist[i].firstedge;
while (p) {
if (!visited[p->adjvex]) {
visited[p->adjvex] = TRUE;
printf("%c ", G.adjlist[p->adjvex].data);
EnQueue(&Q, p->adjvex);
}
p = p->nextArc;
}
}
}
}
}
分析上述算法，每个顶点至多进一次队列。遍历图的过程实质上是通过边和弧找邻接点的过程。因此广度优先搜索遍历图的时间复杂度和深度优先搜索遍历相同，两者不同之处仅仅在于对顶点访问的顺序不同。
Demo：https://github.com/ShoukaiWang/DataStructuresAndAlgorithms
网友评论