本文主要是介绍Graph representation and definition，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
representation:
- adjacency matrix
好处是对边或者权重的queries 都是O(1), remove or add an edge也是O(1). 坏处是对点不友好，增加一个点的操作是O(V^2). 而且本身存储太space consuming，同样是点的平方复杂度。导致在sparse matrix里不适用。
Adjacency Matrix is a 2D array of size V x V where V is the number of vertices in a graph. Let the 2D array be adj[][], a slot adj[i][j] = 1 indicates that there is an edge from vertex i to vertex j. Adjacency matrix for undirected graph is always symmetric. Adjacency Matrix is also used to represent weighted graphs. If adj[i][j] = w, then there is an edge from vertex i to vertex j with weight w.
- adjacency list
好处是省空间，O(V+E), 增加一个点方便。考虑增加一个在中间的点，矩阵表示需要重新update所有的点之间的关系，而这里只需要对新加的点进行操作即可。坏处就是queries一条边是否存在的时候需要O(V).
An array of lists is used. Size of the array is equal to the number of vertices. Let the array be array[]. An entry array[i] represents the list of vertices adjacent to the ith vertex. This representation can also be used to represent a weighted graph. The weights of edges can be represented as lists of pairs.
definition
利用二维数组定义的矩阵比较straightforward。
对于list，我们给出c/c++的基本定义风格如下。
C++:
// A simple representation of graph using STL
#include<bits/stdc++.h>
using namespace std; // A utility function to add an edge in an
// undirected graph.
void addEdge(vector<int> adj[], int u, int v)
{ adj[u].push_back(v); adj[v].push_back(u);
} // A utility function to print the adjacency list
// representation of graph
void printGraph(vector<int> adj[], int V)
{ for (int v = 0; v < V; ++v) { cout << "\n Adjacency list of vertex "<< v << "\n head "; for (auto x : adj[v]) cout << "-> " << x; printf("\n"); }
} // Driver code
int main()
{ int V = 5; vector<int> adj[V]; addEdge(adj, 0, 1); addEdge(adj, 0, 4); addEdge(adj, 1, 2); addEdge(adj, 1, 3); addEdge(adj, 1, 4); addEdge(adj, 2, 3); addEdge(adj, 3, 4); printGraph(adj, V); return 0;
} C语言：
// A C Program to demonstrate adjacency list
// representation of graphs
#include <stdio.h>
#include <stdlib.h> // A structure to represent an adjacency list node
struct AdjListNode
{ int dest; struct AdjListNode* next;
}; // A structure to represent an adjacency list
struct AdjList
{ struct AdjListNode *head;
}; // A structure to represent a graph. A graph
// is an array of adjacency lists.
// Size of array will be V (number of vertices
// in graph)
struct Graph
{ int V; struct AdjList* array;
}; // A utility function to create a new adjacency list node
struct AdjListNode* newAdjListNode(int dest)
{ struct AdjListNode* newNode = (struct AdjListNode*) malloc(sizeof(struct AdjListNode)); newNode->dest = dest; newNode->next = NULL; return newNode;
} // A utility function that creates a graph of V vertices
struct Graph* createGraph(int V)
{ struct Graph* graph = (struct Graph*) malloc(sizeof(struct Graph)); graph->V = V; // Create an array of adjacency lists. Size of // array will be V graph->array = (struct AdjList*) malloc(V * sizeof(struct AdjList)); // Initialize each adjacency list as empty by // making head as NULL int i; for (i = 0; i < V; ++i) graph->array[i].head = NULL; return graph;
} // Adds an edge to an undirected graph
void addEdge(struct Graph* graph, int src, int dest)
{ // Add an edge from src to dest. A new node is // added to the adjacency list of src. The node // is added at the begining struct AdjListNode* newNode = newAdjListNode(dest); newNode->next = graph->array[src].head; graph->array[src].head = newNode; // Since graph is undirected, add an edge from // dest to src also newNode = newAdjListNode(src); newNode->next = graph->array[dest].head; graph->array[dest].head = newNode;
} // A utility function to print the adjacency list
// representation of graph
void printGraph(struct Graph* graph)
{ int v; for (v = 0; v < graph->V; ++v) { struct AdjListNode* pCrawl = graph->array[v].head; printf("\n Adjacency list of vertex %d\n head ", v); while (pCrawl) { printf("-> %d", pCrawl->dest); pCrawl = pCrawl->next; } printf("\n"); }
} // Driver program to test above functions
int main()
{ // create the graph given in above fugure int V = 5; struct Graph* graph = createGraph(V); addEdge(graph, 0, 1); addEdge(graph, 0, 4); addEdge(graph, 1, 2); addEdge(graph, 1, 3); addEdge(graph, 1, 4); addEdge(graph, 2, 3); addEdge(graph, 3, 4); // print the adjacency list representation of the above graph printGraph(graph); return 0;
} 这篇关于Graph representation and definition的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
