图的存储结构

邻接矩阵

存储结构

/*邻接矩阵的结构*/
typedef char VertexType;
typedef int EdgeType;
#define MAXSIZE 100
#define INFINTY 65535

typedef struct
{
	VertexType vexs[MAXSIZE]; //顶点
	EdgeType arc[MAXSIZE][MAXSIZE]; //边表
	int numVertexes;          //顶点数
	int numEdges;             //边数
}MGraph;

邻接矩阵的建立

/*建立无向图的邻接矩阵表示*/
void CreateMGraph(MGraph * G)
{
	printf("请输入顶点数和边数: \n");
	scanf("%d %d", &G->numVertexes, &G->numEdges);


	//边的初始化
	for (int i = 0; i < G->numVertexes; i++)
	{
		for (int j = 0; j < G->numVertexes; j++)
		{
			G->arc[i][j] = INFINTY;
		}
	}


	for (int k = 0; k < G->numEdges; k++)
	{
		int i = 0;
		int j = 0;
		int w = 0;
		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];
	}


	printf("读入顶点信息: \n");
	for (int i = 0; i < G->numVertexes; i++)
	{
		scanf("%c", &G->vexs[i]);
	}

}

邻接表

存储结构

typedef char VertexType;
typedef int EdgeType;
#define MAXSIZE 100
#define INFINTY 65535

typedef struct EdgeNode   //边表结点
{
	int adj;         //邻接点域
	EdgeType weight; //权值
	struct EdgeNode * next;
}EdgeNode;

typedef struct VertexNode //顶点表结点  
{
	VertexType data;  
	EdgeNode * firstEdge; //指向第一条边
}VertexNode, AdjList[MAXSIZE];

typedef struct
{
	AdjList adjList;
	int numVertexes;     //顶点数
	int numEdges;        //边数
}GraphAdjList;

邻接表的建立

/*建立图的邻接表*/
void CreateALGraph(GraphAdjList * G)
{
	printf("请输入顶点数和边数: \n");
	scanf("%d %d", &G->numVertexes, &G->numEdges);

	printf("请输入顶点信息: \n");
	for (int i = 0; i < G->numVertexes; i++)
	{
		scanf("%c", &G->adjList[i].data);
		G->adjList[i].firstEdge = NULL;
	}

	int i = 0, j = 0, w = 0;
	for (int k = 0; k < G->numEdges; k++)
	{
		printf("请输入边(vi,vj)上的编号i,j,w\n");
		scanf("%d %d %d", &i, &j, &w);

		EdgeNode *e = (EdgeNode *)malloc(sizeof(EdgeNode));
		e->adj = j;
		e->weight = w;

		//头插法
		e->next = G->adjList[i].firstEdge;
		G->adjList[i].firstEdge = e;

		//无向图 双向的
		e = (EdgeNode *)malloc(sizeof(EdgeNode));
		e->adj = i;
		e->weight = w;

		//头插法
		e->next = G->adjList[j].firstEdge;
		G->adjList[j].firstEdge = e;

	}
}

十字链表

存储结构

/*十字链表结构*/
typedef struct OEdgeNode   //边表结点
{
	EdgeType tailVex;
	EdgeType headVex;
	int weight;               //加权值构成了网
	struct OEdgeNode * tailLink;
	struct OEdgeNode * headLink;
}OEdgeNode;

typedef struct OVertexNode //顶点表结点  
{
	VertexType data;
	OEdgeNode * firstIn;
	OEdgeNode * firstOut;
}OVertexNode, OAdjList[MAXSIZE];

typedef struct
{
	OAdjList adjList;
	int numVertexes;     //顶点数
	int numEdges;        //边数
}OGraphAdjList;

十字链表的建立

/*建立图的十字链表*/
void CreateOALGraph(OGraphAdjList * OG)
{
	printf("请输入顶点数和边数: \n");
	scanf("%d %d", &OG->numVertexes, &OG->numEdges);

	printf("请输入顶点信息: \n");
	for (int i = 0; i < OG->numVertexes; i++)
	{
		scanf("%c", &OG->adjList[i].data);
		OG->adjList[i].firstIn = NULL;
		OG->adjList[i].firstOut = NULL;
	}

	int i = 0, j = 0, w = 0;
	for (int k = 0; k < OG->numEdges; k++)
	{
		printf("请输入边(vi,vj)上的编号i,j,w\n");
		scanf("%d %d %d", &i, &j, &w);

		OEdgeNode *e = (OEdgeNode *)malloc(sizeof(OEdgeNode));
		e->tailVex = i;
		e->headVex = j;
		e->weight = w;

		//头插法
		e->tailLink = OG->adjList[i].firstOut;
		OG->adjList[i].firstOut = e;

		//有向图
		e->headLink = OG->adjList[j].firstIn;
		OG->adjList[j].firstIn = e;
	}
}

图的遍历

深度优先遍历

邻接矩阵

//邻接矩阵
bool visited[MAXSIZE];

void dfs(MGraph G, int i)
{
	visited[i] = true;
	printf("%c ", G.vexs[i]);

	for (int j = 0; j < G.numVertexes; j++)
	{
		if (G.arc[i][j] == 1 && !visited[j])
		{
			dfs(G, j);
		}
	}
}


void dfsTraverse(MGraph G)
{
	for (int i = 0; i < G.numVertexes; i++)
	{
		visited[i] = false;  //初始所有顶点状态为未访问
	}
	for (int i = 0; i < G.numVertexes; i++)
	{
		if (!visited[i])
		{
			dfs(G, i);
		}
	}
}

邻接表

/*邻接表的深度优先递归*/

void dfsList(GraphAdjList G, int i)
{
	visited[i] = true;

	printf("%c ", G.adjList[i].data);

	EdgeNode * p = G.adjList[i].firstEdge;
	while (p)
	{
		if (!visited[p->adj])
		{
			dfsList(G, p->adj);
		}
		p = p->next;
	}
}

void dfsTraverseList(GraphAdjList G)
{
	for (int i = 0; i < G.numVertexes; i++)
	{
		if (!visited[i])
		{
			dfsList(G, i);
		}
	}
}

广度优先遍历

邻接矩阵

//邻接矩阵
void BfsTraverse(MGraph G)
{

	int k = 0;
	for (int i = 0; i < G.numVertexes; i++)
		visited[i] = false;     //全部初始化为未访问

	SqQueue q;
	InitQueue(&q);   //初始化队列
	
	for (int i = 0; i < G.numVertexes; i++)//遍历每一个顶点
	{
		if (!visited[i])
		{
			visited[i] = true;
			printf("%c ", G.vexs[i]);
			EnQueue(&q, i);
			while (!QueueEmpty(q))
			{
				DeQueue(&q, &k);

				for (int j = 0; j < G.numVertexes; i++) //判断每一个邻接点
				{
					if (G.arc[k][j] == 1 && !visited[j])
					{
						visited[j] = true;
						printf("%c ", G.vexs[j]);

						EnQueue(&q, j);
					}
				}
			}
		}
	}

}

邻接表


```c

//邻接表
void BfsAdfTraverse(GraphAdjList G)
{
	int k = 0;
	EdgeNode * p;

	for (int i = 0; i < G.numVertexes; i++)
		visited[i] = false;  //初始化未未访问

	SqQueue q;
	InitQueue(&q);

	for (int i = 0; i < G.numVertexes; i++)//遍历每个顶点
	{
		if (!visited[i])
		{
			visited[i] = true;
			printf("%c ", G.adjList[i].data);
			EnQueue(&q, i);

			while (!QueueEmpty(q))
			{

				DeQueue(&q, &k);
				p = G.adjList[k].firstEdge;
				while (p)
				{
					if (!visited[p->adj])
					{
						visited[p->adj] = true;
						printf("%c ", G.adjList[p->adj].data);
						EnQueue(&q, p->adj);
					}
					p = p->next;
				}
			}
		}
	}
}